当前位置:   article > 正文

数据结构-二叉树详解(原理+基本操作Java实现)_java设计一个二叉树类结构

java设计一个二叉树类结构

二叉树的概念及特点

二叉树的概念

二叉树(Binary Tree)是n (n>=0)个节点的有限集合,该集合可以为空集(称为空二叉树),或者由一个根节点和两个互不相交的,分别称为根节点的左子树和右子树的二叉树组成。

二叉树的特点:

1、每个节点最多有两棵子树,即不存在超过度为2的节点。

2、二叉树的子树有左右之分,且左右不能颠倒。

如下图所示,下图就是一个二叉树

特殊的二叉树

1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。

如下图所示

2.完全二叉树:完全二叉树是由满二叉树引出的。满二叉树要求每一层的节点数都达到最大值,完全二叉树仅要求除最后一层外的节点数达到最大值,也就是说最后一层可以不满。我们可以把满二叉树看错特殊的完全二叉树。

如下图所示

二叉树的性质

1.若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。

2.若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h- 1。

3.任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0=n2+1

4.若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=Log2(n+1)

5.对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:

(1)若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点

(2)若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子

(3)若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子

二叉树的基本操作

树结点类和构造方法

  1. static class TreeNode {
  2. public char val;
  3. public TreeNode left;//左孩子的引用
  4. public TreeNode right;//右孩子的引用
  5. public TreeNode(char val) {
  6. this.val = val;
  7. }
  8. }

创建一棵二叉树

  1. public TreeNode createTree() {
  2. TreeNode A=new TreeNode('A');
  3. TreeNode B=new TreeNode('B');
  4. TreeNode C=new TreeNode('C');
  5. TreeNode D=new TreeNode('D');
  6. TreeNode E=new TreeNode('E');
  7. TreeNode F=new TreeNode('F');
  8. A.left=B;
  9. A.right=D;
  10. B.left=C;
  11. D.left=E;
  12. D.right=F;
  13. return A;
  14. }

遍历

前序遍历

  1. public void preOrder(TreeNode root) {
  2. if (root==null){
  3. return;
  4. }
  5. System.out.println(root.val);
  6. preOrder(root.left);
  7. preOrder(root.right);
  8. }

中序遍历

  1. public void inOrder(TreeNode root) {
  2. if (root==null){
  3. return;
  4. }
  5. inOrder(root.left);
  6. System.out.println(root.val);
  7. inOrder(root.right);
  8. }

后序遍历

  1. public void postOrder(TreeNode root) {
  2. if (root==null){
  3. return;
  4. }
  5. postOrder(root.left);
  6. postOrder(root.right);
  7. System.out.println(root.val);
  8. }

获取树中节点的个数:遍历思路

  1. public static int nodeSize;//定义一个全局变量方便保存结点个数
  2. public void size(TreeNode root) {
  3. if (root==null){
  4. return;
  5. }
  6. nodeSize++;//不是空就++
  7. size(root.left);
  8. size(root.right);
  9. }

获取节点的个数:子问题的思路

  1. int size2(TreeNode root) {
  2. if (root==null){
  3. return 0;
  4. }
  5. int leftSize=size2(root.left);//先求左子树的结点个数
  6. int rightSize=size2(root.left);//然后求右子树结点的个数
  7. return leftSize+rightSize+1;//返回左子树和右子树加上1
  8. }

也许有的小伙伴不明白为什么要加一,加一就是加上本根结点

获取叶子节点的个数:遍历思路

遍历思路跟上面一样,定义全局变量,满足条件就++,缺点就是只能求一棵树,两棵树就不好求,建议大家用子问题的思路

  1. public static int leafSize = 0;//和上面一样,方便保存叶子结点个数
  2. void getLeafNodeCount1(TreeNode root) {
  3. if (root==null){
  4. return;
  5. }
  6. if (root.left==null&&root.right==null){//满足if里面的条件就说明是叶子结点
  7. leafSize++;
  8. }
  9. getLeafNodeCount1(root.left);
  10. getLeafNodeCount1(root.right);
  11. }

获取叶子节点的个数:子问题

如下代码,满足条件就返回1,否则返回零,通过左子树加右子树累加起来,最后返回总数目

  1. int getLeafNodeCount2(TreeNode root) {
  2. if (root==null){
  3. return 0;
  4. }
  5. if (root.left==null&&root.right==null){
  6. return 1;
  7. }
  8. int l=getLeafNodeCount2(root.left);
  9. int r=getLeafNodeCount2(root.right);
  10. return l+r;
  11. }

获取第K层节点的个数

利用一直递归k-1求得左子树和右子树的本层结点个数,最后返回它们的和

  1. int getKLevelNodeCount(TreeNode root, int k) {
  2. if (root==null){
  3. return 0;
  4. }
  5. if (k==1){
  6. return 1;
  7. }
  8. int l=getKLevelNodeCount(root.left,k-1);
  9. int r=getKLevelNodeCount(root.right,k-1);
  10. return l+r;
  11. }

获取二叉树的高度

利用递归方法返回左右子树最大高度加上根节点本身

  1. int getHeight(TreeNode root) {
  2. if (root==null){
  3. return 0;
  4. }
  5. int leftHigh=getHeight(root.left);
  6. int rightHigh=getHeight(root.right);
  7. return Math.max(leftHigh,rightHigh)+1;
  8. }

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

  1. TreeNode find(TreeNode root, char val) {
  2. if(root == null) {
  3. return null;
  4. }
  5. if(root.val == val) {
  6. return root;
  7. }
  8. TreeNode ret1 = find(root.left,val);
  9. if(ret1 != null) {
  10. return ret1;//如果左子树不为空,就说明找到了,返回
  11. }
  12. TreeNode ret2 = find(root.left,val);
  13. if(ret2 != null) {
  14. return ret2;//如果右子树不为空,就说明找到了,返回
  15. }
  16. return null;
  17. }

判断一棵树是不是完全二叉树

  1. boolean isCompleteTree(TreeNode root) {
  2. if(root == null) {
  3. return true;
  4. }
  5. Queue<TreeNode> qu = new LinkedList<>();
  6. qu.offer(root);
  7. while(!qu.isEmpty()) {
  8. TreeNode node = qu.poll();
  9. if(node != null) {
  10. qu.offer(node.left);
  11. qu.offer(node.right);
  12. } else {
  13. break;
  14. }
  15. }
  16. if(!qu.isEmpty()) {
  17. TreeNode node = qu.poll();
  18. if(node != null) {
  19. return false;
  20. }
  21. }
  22. return true;
  23. }

本期知识点就到这里,关注我,下期会给大家带来关于二叉树的力扣等练习题

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/457148
推荐阅读
相关标签
  

闽ICP备14008679号