2.1前序遍历2.2中序遍历2.3后序遍历 三、求二叉树节点个数
3.1遍历思路3.2子问题思路 四、求叶子节点个数
4.1遍历思路4.2子问题思路 五、求第k层节点个数六、获取二叉树高度七、检测值为value的节点是否存在八、判断一个树是不是完全二叉树
前言
二叉树是我们数据结构非常重要的知识,平时的考试和面视也经常有所涉及,今天笔者给大家整理了常见的java二叉树基础 *** 作代码,希望读者学有所成
提示:以下是本篇文章正文内容,下面案例可供参考
一、二叉树的节点和类定义我们这里简单创建一棵如下的树:
代码如下(示例):
class BTNode{//节点 public char val; public BTNode left;//左孩子的引用 public BTNode right;//右孩子的引用 public BTNode(char val){ this.val=val; } } public class BinaryTree {//二叉树类 public BTNode root;//二叉树根节点 public BTNode createTree(){ BTNode A=new BTNode('A'); BTNode B=new BTNode('B'); BTNode C=new BTNode('C'); BTNode D=new BTNode('D'); BTNode E=new BTNode('E'); BTNode F=new BTNode('F'); BTNode G=new BTNode('G'); BTNode H=new BTNode('H'); A.left=B; A.right=C; B.left=D; B.right=E; C.left=F; C.right=G; E.right=H; return A; }二、前、中、后序遍历 2.1前序遍历
代码如下(示例):
//前序遍历——根左右 void preOrder(BTNode root){ if(root==null){ return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); }2.2中序遍历
代码如下(示例):
//中序遍历——左根右 void inOrder(BTNode root){ if(root==null){ return; } inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right); }2.3后序遍历
代码如下(示例):
//后序遍历——左右根 void postOrder(BTNode root){ if(root==null){ return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val+" "); }
小技巧:不用刻意记住顺序,左永远在右前面,然后“根”随着前中后改变,比如前序遍历,就是根最前面,然后左右——根左右。同样的中序:根在中间,左根右;后序以此类推。
测试用例如下:
public static void main(String[] args) { BinaryTree binaryTree=new BinaryTree(); BTNode root=binaryTree.createTree(); binaryTree.preOrder(root);//A B D E H C F G System.out.println(); binaryTree.inOrder(root);//D B E H A F C G System.out.println(); binaryTree.postOrder(root);//D H E B F G C A }
打印结果如下:
三、求二叉树节点个数 3.1遍历思路
//遍历思路:定义一个计数器count,遍历二叉树,如果是节点,则count++,遍历方法前中后序都可以 int count=0;//count不能放到函数里面,因为你放到函数里面,每次递归都会变成0 int size(BTNode root){ if(root==null){ return 0; } count++; size(root.left); size(root.right); return count; }3.2子问题思路
//子问题思路:左树节点+右树节点=整棵树节点 int size(BTNode root){ if(root==null){ return 0; }else{ return size(root.left)+size(root.right)+1;//加1是算上自己 } }
测试用例如下:
public static void main(String[] args) { BinaryTree binaryTree=new BinaryTree(); BTNode root=binaryTree.createTree(); int size=binaryTree.size(root); System.out.println(size);//打印8 }四、求叶子节点个数 4.1遍历思路
//遍历思路:遍历到叶子节点,count++ int count=0;//count同样不能放到方法里面,原因同题三 int getLeafNodeCount(BTNode root){ if(root==null){ return 0; }else if(root.left==null&&root.right==null){ count++; return count; } getLeafNodeCount(root.left); getLeafNodeCount(root.right); return count; }4.2子问题思路
//子问题思路:左树的叶子+右树的叶子=整棵树叶子 int getLeafNodeCount(BTNode root){ if(root==null){ return 0; }else if(root.left==null&&root.left==null){ return 1; } return getLeafNodeCount(root.left)+getLeafNodeCount(root.right); }
测试用例如下:
public static void main(String[] args) { BinaryTree binaryTree=new BinaryTree(); BTNode root=binaryTree.createTree(); int LeafNodeCount= binaryTree.getLeafNodeCount(root); System.out.println(LeafNodeCount);//4 }五、求第k层节点个数
//获取第k层节点个数 //思路:求第K层节点个数,就是求左子树第k-1层和右子树第k-1层个数和 int getKLevelNodeCount(BTNode root,int k){ if(root==null){ return 0; } if(k==1){ return 1; } return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1); }
测试用例如下:
public static void main(String[] args) { BinaryTree binaryTree=new BinaryTree(); BTNode root=binaryTree.createTree(); int get1LevelCount= binaryTree.getKLevelNodeCount(root, 1); System.out.println(get1LevelCount);//1 int get2LevelCount= binaryTree.getKLevelNodeCount(root, 2); System.out.println(get2LevelCount);//2 int get3LevelCount= binaryTree.getKLevelNodeCount(root, 3); System.out.println(get3LevelCount);//4 int get4LevelCount= binaryTree.getKLevelNodeCount(root, 4); System.out.println(get4LevelCount);//1 }六、获取二叉树高度
//获取二叉树的高度 //思路:左数高度和右树高度比较,取最大值,最后+1(最大值是子树高度,还要算上根) int getHeight(BTNode root){ if(root==null){ return 0; }else{ int maxLeft=getHeight(root.left); int maxRight=getHeight(root.right); return maxLeft>maxRight?maxLeft+1:maxRight+1; //法二:上面三行代码换成下面这行 //return getHeight(root.left)>getHeight(root.right)?getHeight(root.left)+1:getHeight(root.right)+1; //三目运算符,左树高度比右树高度大,就返回左数高度,否则就是右树高度,最后+1 //三目运算符这种写法,在树比较大的时候时间复杂度很大(重复递归了左树和右树最大高度),建议还是上面的写法 } }
测试用例如下:
public static void main(String[] args) { BinaryTree binaryTree=new BinaryTree(); BTNode root=binaryTree.createTree(); int height= binaryTree.getHeight(root); System.out.println(height);//4 }七、检测值为value的节点是否存在
//检测值为value的节点是否存在 //思路:遍历二叉树中的节点,判断该节点中有没有我要找到数据,如果没有就去子树找(先左还是先右你自己选) BTNode find(BTNode root,int val){ if(root==null){ return null; }else if(root.val==val){ return root; }else{ BTNode ret1=find(root.left,val); if(ret1!=null){//!=null说明找到了 return ret1; } BTNode ret2=find(root.right,val); if(ret2!=null){ return ret2; } //走到这里还是没有return出去,说明左右子树都没有找到 return null; } }
测试用例如下:
public static void main(String[] args) { BinaryTree binaryTree=new BinaryTree(); BTNode root=binaryTree.createTree(); BTNode ret1= binaryTree.find(root,'c'); System.out.println(ret1);//null BTNode ret2= binaryTree.find(root,'C'); System.out.println(ret2);//BTNode@1b6d3586(C地址) System.out.println(ret2.val);//C }八、判断一个树是不是完全二叉树
我先通过两个简单的树给大家说一下思路:
树1(完全二叉树)
先把A放到队列里面
然后出掉A,把A的左右节点BC放到队列里面
然后出掉B,把B的左右节点DE放到队列里面
出掉C,把C的左节点F和一个null(没有右节点)放到队列里
出掉D,放两个null进队列
出掉E,放两个null进队列
出掉F,放两个null进队列
d出null的时候结束循环
我们发现,完全二叉树最后出的队列里面只剩下null
树2(非完全二叉树):
这里时间有限,举一个简单的非完全二叉树
我们把A放到队列里面
出掉A,放入A左右节点null(没有左节点)和B
d出null的时候循环结束,发现队列里面不全是null,就不是完全二叉树
具体代码实现如下:
boolean isCompleteTree(BTNode root){ if(root==null){ return true; } Queuequeue=new linkedList<>(); queue.offer(root);//offer效果和add一样,向队列里面添加元素 while(!queue.isEmpty()){ BTNode cur= queue.poll();//d出队列首个元素,赋值给cur if(cur!=null){ queue.offer(cur.left); queue.offer(cur.right); }else { break; } } while(!queue.isEmpty()){//判断队列里面的剩余元素是不是全空(全空为完全二叉树,不然就不是) BTNode top= queue.peek();//取队头元素(不删除) if(top!=null){ return false; } queue.poll();//d出队头元素(删除) } return true;//走完while说明原先队列剩余元素都是null,也就是完全二叉树 }
测试用例如下:
public static void main(String[] args) { BinaryTree binaryTree=new BinaryTree(); BTNode root=binaryTree.createTree(); boolean isC=binaryTree.isCompleteTree(root); System.out.println(isC);//false }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)