当前位置：首页 > news >正文

Java之二叉树的基本操作实现

news 2025/4/25 9:10:00

1. 模拟实现二叉树前，我们要先表示树，首先定义一个内部类，当作二叉树节点

static class TreeNOde{char val;//存放二叉树的值TreeNOde left;//指向左子树的引用TreeNOde right;//指向右子树的引用//构造方法，用于实例化树的节点public TreeNOde(char val) {this.val = val;}}

2. 简单构建一个树

public TreeNOde  easycreat(){TreeNOde A=new TreeNOde('A');TreeNOde B=new TreeNOde('B');TreeNOde C=new TreeNOde('C');TreeNOde D=new TreeNOde('D');TreeNOde E=new TreeNOde('E');TreeNOde F=new TreeNOde('F');A.left=B;A.right=C;B.left=D;C.left=E;C.right=F;return A;}

最后简单构造的树如下图所示：
在这里插入图片描述

3. 获取树中节点的个数

3.1 利用递归实现

    public int getNodesize1(TreeNOde root){if(root==null) return 0;return getNodesize1(root.left)+getNodesize1(root.right)+1;}

3.2 利用遍历树实现

int nodeSize=0;public int getNodesize2(TreeNOde root){if(root==null) return 0;nodeSize++;getNodesize2(root.left);getNodesize2(root.right);return nodeSize;}

4. 获取叶子节点的个数

4.1 利用递归实现

    int getLeafNodeCount1(TreeNOde root){if(root==null) return 0;if(root.left==null &&root.right==null){return 1;}return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);}

4.2 利用遍历树实现

    int leafnode=0;int getLeafNodeCount2(TreeNOde root){if(root==null)return 0;if(root!=null&&root.left==null&&root.right==null){leafnode++;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);return leafnode;}

5. 检测值为value的元素是否存在

TreeNOde find(TreeNOde root, char val){if(root==null) return null;if(root.val==val) return root;TreeNOde leftval=find(root.left,val);if(leftval!=null){return leftval;}TreeNOde rightval=find(root.right,val);if(rightval!=null){return rightval;}return null;}

6. 获取第K层节点的个数

 int getKLevelNodeCount(TreeNOde root,int k){if(root==null) return 0;if(k==1) return 1;return getKLevelNodeCount(root.left,k-1) +getKLevelNodeCount(root.right,k-1);}

7. 获取二叉树的高度

 int getHeight(TreeNOde root){if(root==null) return 0;int leftHeight=getHeight(root.left);int rightHeight=getHeight(root.right);return Math.max(leftHeight,rightHeight) + 1;}

8. 打印找数据的方法

public void displayfind(TreeNOde root){if(root==null){System.out.println("二叉树中不存在该数据");return;}System.out.println("找到了数据为"+root.val);}

9. 实现类代码

public class Test {public static void main(String[] args) {BinaryTree binaryTree=new BinaryTree();BinaryTree.TreeNOde root=binaryTree.easycreat();System.out.println("找相关数据：");BinaryTree.TreeNOde findnode1= binaryTree.find(root, 'j');binaryTree.displayfind(findnode1);BinaryTree.TreeNOde findnode2=binaryTree.find(root, 'B');binaryTree.displayfind(findnode2);System.out.println("树中节点个数：");System.out.println(binaryTree.getNodesize1(binaryTree.easycreat()));System.out.println(binaryTree.getNodesize2(binaryTree.easycreat()));System.out.println("叶子节点个数:");System.out.println(binaryTree.getLeafNodeCount1(binaryTree.easycreat()));System.out.println(binaryTree.getLeafNodeCount2(binaryTree.easycreat()));System.out.println("第k层有多少个节点;");System.out.println(binaryTree.getKLevelNodeCount(binaryTree.easycreat(),2));System.out.println(binaryTree.getKLevelNodeCount(binaryTree.easycreat(),3));System.out.println("树的高度");System.out.println(binaryTree.getHeight(binaryTree.easycreat()));}
}