• 【java数据结构】就是你爱的那颗二叉树

    目录

    树的定义

    树的特点

    树的结点分类

    二叉树

    三种特殊的二叉树

     二叉树的性质(非常重要)

     二叉树的存储

    二叉树的基本操作

    二叉树的遍历

    二叉树的前序遍历

    二叉树的中序遍历

    二叉树的后序遍历

    获取树中节点的个数

    获取叶子节点的个数

    获取第K层节点的个数

    获取二叉树的高度

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

    层序遍历

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

    树的定义

    树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

    树的特点

    • 有一个特殊的结点，称为根结点，根结点没有前驱结点(通常叫它root节点)
    • 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合 Ti (1 <= i<= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。(根节点：唯一，有且仅有一个根节点，中间结点：一个双亲可以有多个孩子节点，叶子结点:叶子结点度为0，无孩子可以有多个)。
    • 由于一棵树又可以划分为多个子树，所以二叉树的操作大部分都是由递归来实现的
    • 对于节点数为n，n>0时根节点是唯一的，有且仅有一个
    • 一棵树可以有多个节点，但是节点之间是不能相交的

    树的结点分类

    结点的度：一个结点含有子树的个数称为该结点的度；对于1节点它的度就是2,1节点共有两个子树
    树的度：一棵树中，所有结点度的最大值称为树的度； 这颗树，一个结点最多子树为2个，所以树的度为2
    叶子结点或终端结点：度为0的结点称为叶结点； 叶子结点在树的最后没有子树的节点，例如6,7,8,9,10节点.
    双亲结点或父结点：若一个结点含有子结点这个结点称为其子结点的父结点;比如2的父亲就是1
    孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 对于2节点来说它的父亲是1，对于1节点来说它的孩子是2和3节点
    根结点：一棵树中，没有双亲结点的结点；一般来说除了空树外，其他树有且仅有一个根节点root
    结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
    树的深度：相对于节点来说的，比如1节点深度为1。 2,3节点深度为2。4,5,6,7节点深度为3

    树的高度：树中结点的最大层次；树的最大深度就是这一颗树的高度

    树的祖先：从根到该结点所经分支上的所有结点，对于8节点来说，1,2,4节点都是8的公共祖先。

    二叉树

    二叉树的特点

    • 对于二叉树的每一个节点来说，它的度也就是子树的个数都是小于等于2的
    • 二叉树有左右子树区分。一定要区分它的左树和右树。

    二叉树的五种形态

    • 空树（没有结点的树）
    • 只有左树没有右树
    • 只有右树没有左树
    • 既有左树又有右树
    • 只有一个根节点

    三种特殊的二叉树

    • 斜树：所有树只有左子树的树或者只有右子树的树叫做斜树，只有左子树的树叫做左斜树，只有右子树的树叫做右斜树

    • 满二叉树： 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树

    •  完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。完全二叉树从左往右开始编号，如果不为空是一颗完全二叉树，完全二叉树可以有度为1的情况，如果从左往右开始编号为空，那就证明不是一颗完全二叉树

     二叉树的性质(非常重要)

    • 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^i-1(i>0)个结点

    •  若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^k-1 (k>=0)

    •  对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

    •  具有n个结点的完全二叉树的深度k为 log2(n+1)上取整

    •  . 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
      若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
      若2i+1<n，左孩子序号：2i+1，否则无左孩子
      若2i+2<n，右孩子序号：2i+2，否则无右孩子

    给定子节点下标求父节点下标：(i-1)/2

    给定父节点下标求子节点下标：左孩子2i+1 右孩子：2i+2

    这个结论在堆的学习经常会用到所以务必要记住

    一些习题：

     

     二叉树的存储

    我们在平时刷题时和平常学的一些二叉树基础都是利用链式存储，也就是说一个节点有节点值和它的左孩子和右孩子。

    1. public class TreeNode {
    2.     int val; // 数据域
    3.     TreeNode left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
    4.     TreeNode right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
    5. }

    二叉树的基本操作

    首先我们创建一颗二叉树

    1.  static class TreeNode{
    2.         public int val;
    3.         public TreeNode left;
    4.         public TreeNode right;
    5.         public TreeNode(int val){
    6.             this.val = val;
    7.         }
    8.     }
    9.  
    10.     //根节点
    11.     public TreeNode root;
    12.  
    13.     public TreeNode createTree(){
    14.         TreeNode node1 = new TreeNode(1);
    15.         TreeNode node2 = new TreeNode(2);
    16.         TreeNode node3 = new TreeNode(3);
    17.         TreeNode node4 = new TreeNode(4);
    18.         TreeNode node5 = new TreeNode(5);
    19.         TreeNode node6 = new TreeNode(6);
    20.         TreeNode node7 = new TreeNode(7);
    21.  
    22.         node1.left = node2;
    23.         node1.right = node4;
    24.         node2.left = node3;
    25.         node2.right = node7;
    26.         node4.left = node5;
    27.         node4.right= node6;
    28.         root =node1;
    29.         return root;
    30.  
    31.     }

    二叉树的遍历

    二叉树的前序遍历

    二叉树的前序遍历：先访问根在访问左子树在访问右子树  根-左子树-右子树

     对于这样一颗二叉树它的先序遍历时 A - B - D - E -H - C - F - G

     我们仔细分析一下这个前序遍历：

    对于A这棵树来说要先访问根也就是A,然后去访问A的左子树，而A的左子树又是一棵树,先访问根B,在访问B这棵树的左子树D,对于D这棵树而言又是一棵树，所以先访问根D,再去访问它的左子树，发现D的左子树为null,再去访问D的右子树为null,所以D这棵树访问完了，也证明B的左树访问完了，然后接着访问B的右树E，而E又是一棵树，先访问根节点E,在去访问它的左子树，发现它的左子树为null,再去访问它的右子树H,所以E这棵树访问完了，也说明B的右树访问完了，也说明A的左树访问完了，然后再去访问A的右树C，而C又是一棵树，先访问根C,在去访问她的左树F,而F又是一棵树，访问它的左树为空，右树为空，F这棵树访问完了，所以C的左树访问完，同理再去访问G,好最后返回到A证明A这棵树走完了，这才是真正的结束一个二叉树的前序遍历。

    根据我上面的分析，每一个树的逻辑都是一样的，都是先访问根节点，在访问左子树，在访问右子树，在访问左子树或者右子树，又是同样的道理，所以每一棵树可以用相同的操作，在使用递归操作重复调用，最终这棵树就遍历完成。

    代码实现：

    • 前序遍历-->递归版本无list
    1.  // 前序遍历-->递归版本无list
    2.     void preOrder(TreeNode root){
    3.         if(root==null) return;
    4.         System.out.print(root.val+" ");
    5.         preOrder(root.left);
    6.         preOrder(root.right);
    7.     }
    • 使用list遍历思路去存储-->前序遍历
    1.  //使用list遍历思路去存储-->前序遍历
    2.     List<Integer> list = new ArrayList<>();
    3.     public List<Integer> preorderTraversal(TreeNode root) {
    4.         if(root==null) return list;
    5.         list.add(root.val);
    6.         preorderTraversal(root.left);
    7.         preorderTraversal(root.right);
    8.         return list;
    9.     }

    • 使用list子问题思路进行前序遍历

    1. //使用list子问题思路进行前序遍历
    2.     public List<Integer> preorderTraversal1(TreeNode root) {
    3.         List<Integer> list = new ArrayList<>();
    4.         if(root==null) return list;
    5.         list.add(root.val);
    6.         List<Integer> leftTree = preorderTraversal(root.left);
    7.         if(leftTree!=null){
    8.             list.addAll(leftTree);
    9.         }
    10.         List<Integer> rightTree = preorderTraversal(root.right);
    11.         if(rightTree!=null){
    12.             list.addAll(rightTree);
    13.         }
    14.         return list;
    15.     }

    • 前序遍历-->非递归版本

    1. //前序遍历-->非递归版本
    2.     public List<Integer> preorderTraversal2(TreeNode root) {
    3.         List<Integer> ret = new ArrayList<>();
    4.         if(root==null) return ret;
    5.         Stack<TreeNode> stack = new Stack<>();
    6.         TreeNode cur = root;
    7.         while(cur!=null||(!stack.isEmpty())){
    8.             while(cur!=null){
    9.                 stack.push(cur);
    10.                 ret.add(cur.val);
    11.                 cur = cur.left;
    12.             }
    13.             TreeNode top = stack.pop();
    14.             if(top.right!=null){
    15.                 cur = top.right;
    16.             }
    17.         }
    18.         return ret;
    19.     }

    二叉树的中序遍历

    根据二叉树的前序遍历，中序遍历也是一样的道理，中序遍历是先访问左子树在访问根节点在访问右子树。

    对于上面那棵树而言中序遍历为：D - B - E - H - A - F - C - G

    代码实现：

    1. // 中序遍历
    2.     void inOrder(TreeNode root){
    3.         if(root==null) return;
    4.         inOrder(root.left);
    5.         System.out.print(root.val+" ");
    6.         inOrder(root.right);
    7.     }
    • 使用list-->子问题进行中序遍历
    1. //使用list-->子问题进行中序遍历
    2.     public List<Integer> inorderTraversal(TreeNode root) {
    3.         List<Integer> ret = new ArrayList<>();
    4.         if(root==null) return ret;
    5.         List<Integer> leftTree = inorderTraversal(root.left);
    6.         if(leftTree!=null){
    7.             ret.addAll(leftTree);
    8.         }
    9.         ret.add(root.val);
    10.         List<Integer> rightTree = inorderTraversal(root.right);
    11.         if(rightTree!=null){
    12.             ret.addAll(rightTree);
    13.         }
    14.         return ret;
    15.     }
    • 使用list进行非递归实现--->中序遍历
    1. //使用list进行非递归实现--->中序遍历
    2.     public List<Integer> inorderTraversalNor(TreeNode root) {
    3.         List<Integer> ret = new ArrayList<>();
    4.         if(root==null) return ret;
    5.         Stack<TreeNode> stack = new Stack<>();
    6.         TreeNode cur = root;
    7.         while(cur!=null||!stack.isEmpty()){
    8.             while (cur != null) {
    9.                 stack.push(cur);
    10.                 cur = cur.left;
    11.             }
    12.             TreeNode top = stack.pop();
    13.             ret.add(top.val);
    14.             if (top.right != null) {
    15.                 cur = top.right;
    16.             }
    17.         }
    18.         return ret;
    19.     }

    二叉树的后序遍历

    根据二叉树的前序遍历，中序遍历，后序遍历也是一样的道理，后序遍历是先访问左子树在访问右子树在访问根节点。

    对于上面那棵树而言后序遍历为：D - H - E - B - F - G - C - A

    代码实现：

    1.     // 后序遍历
    2.     void postOrder(TreeNode root){
    3.         if(root==null) return;
    4.         postOrder(root.left);
    5.         postOrder(root.right);
    6.         System.out.print(root.val+" ");
    7.     }
    • 使用非递归来实现二叉树的后序遍历
    1. //使用非递归来实现二叉树的后序遍历
    2.     public List<Integer> postorderTraversal(TreeNode root) {
    3.         List<Integer> ret = new ArrayList<>();
    4.         if(root==null) return ret;
    5.         Stack<TreeNode> stack = new Stack<>();
    6.         TreeNode cur = root;
    7.         TreeNode prev = null;
    8.         while(cur!=null||(!stack.isEmpty())){
    9.             while(cur!=null){
    10.                 stack.push(cur);
    11.                 cur = cur.left;
    12.             }
    13.             TreeNode top = stack.peek();
    14.             if(top.right==null||top.right==prev){
    15.                 stack.pop();
    16.                 ret.add(top.val);
    17.                 prev = top;
    18.             }else {
    19.                 cur = top.right;
    20.             }
    21.         }
    22.         return ret;
    23.     }
    • 最终我们还可以得出一个结论要想有想构建一颗二叉树，要么给出二叉树的递归序(也就是包括null节点也给出)，否则要想得到一颗二叉树，必须知道中序遍历，要么前序遍历和中序遍历，要么后序遍历和中序遍历，如果没有中序遍历，就只能根据前序或者后序确定根节点，不能确定左子树和右子树。

    获取树中节点的个数

    对于获取节点个数：普通遍历思路，就是遍历二叉树中的每一个节点然后计数器++，可以使用前序中序后序都可以。

    这里的代码实现给出的是子问题的思路，我们可以思考一下，对于一颗二叉树来说，就是根节点，左子树和右子树，那一颗二叉树节点的个数是不是等于左子树节点的个数+右子树节点的个数+根节点本身(也就是+1)。

    1. int size(TreeNode root){
    2.     if(root==null) return 0;
    3.     int left = size(root.left);//算出左子树的节点个数
    4.     int right = size(root.right);//算出右子树的节点个数
    5.     return left+right+1;
    6. }

    获取叶子节点的个数

    遍历思路：叶子结点前面我也讲过就是度为0的节点，也就是当我们遍历树的左子树为空并且它的右子树为空，那他就是我们的叶子结点使用计数器++就可以。

    子问题思路：这里我给出的也是子问题思路，一颗二叉树我们只要求出它的左子树叶子结点个数+右子树叶子结点个数就是我们这棵二叉树的叶子结点个数了。

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

    获取第K层节点的个数

    对于一颗二叉树，我们要求第3层结点个数，那相对于根节点我们是不是求它的第二层结点。而相对于第二层结点来说我们是不是在求它的第一层结点，对于第三层，我们是求它的第0层。

    号也就是说，如果我们求第k层结点的个数我们就求相对于每一层的k-1层结点，当k=1时候也就是求它本身结点个数1.

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

    获取二叉树的高度

    对于一颗二叉树来说，树的高度就是这颗二叉树最大深度，我们只要求出左子树和右子树高度的最大值在+1就是这棵二叉树的高度。

    1. int getHeight(TreeNode root){
    2.         if(root==null) return 0;
    3.         int left = getHeight(root.left);
    4.         int right = getHeight(root.right);
    5.         return left>right?left+1:right+1;
    6.     }

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

    还是一样的，对于一颗二叉树我们要判断value是否在这颗二叉树中存在，我们首先会先去根节点看一看是不是这个value,如果不是value，再去左子树看一看有没有，再去看一看右子树有没有，如果在一棵树中找到value立马把这个值返回来。

    1. TreeNode find(TreeNode root, int val){
    2.         if(root==null) return null;
    3.         if(root.val==val) return root;
    4.         TreeNode leftTree = find(root.left,val);
    5.         if(leftTree!=null){
    6.             return leftTree;
    7.         }
    8.         TreeNode rightTree = find(root.right,val);
    9.         if(rightTree!=null){
    10.             return rightTree;
    11.         }
    12.         return null;
    13.     }

    层序遍历

    层序遍历我们利用一个辅助栈来实现。

    • 先将根节点压入栈中
    • 每一次将栈顶元素弹出并打印，在弹出元素时要将弹出元素利用一个临时遍历存起来，然后同时将它的左子树和右子树一并压入栈中，如果为null我们就不压入栈中，反复进行最终就是层序遍历
    1. void levelOrder(TreeNode root){
    2.         Queue<TreeNode> queue = new LinkedList<>();
    3.         queue.offer(root);
    4.         while(!queue.isEmpty()){
    5.             TreeNode cur = queue.poll();
    6.             System.out.print(cur.val+" ");
    7.             if(cur.left!=null){
    8.                 queue.offer(cur.left);
    9.             }
    10.             if(cur.right!=null){
    11.                 queue.offer(cur.right);
    12.             }
    13.         }
    14.     }

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

    根据层序遍历思想

    • 先将根节点压入栈中
    • 每一次将栈顶元素弹出并打印，在弹出元素时要将弹出元素利用一个临时遍历存起来，然后同时将它的左子树和右子树一并压入栈中，此时与层序遍历不同的是如果树为null，我们依然要压入栈中
    • 最后我们将这棵树遍历完之后，栈中还有元素，如果栈中元素全为null,就说明这是一颗完全二叉树，否则不是。
    • 这也依据完全二叉树的定义，如果从左往右开始编号，有一个子树漏掉了并且它的右边还有子树那就不是一颗完全二叉树
    1. boolean isCompleteTree(TreeNode root){
    2.         Queue<TreeNode> queue = new LinkedList<>();
    3.         queue.offer(root);
    4.         while(!queue.isEmpty()){
    5.             TreeNode cur = queue.poll();
    6.             if(cur==null){
    7.                 break;
    8.             }
    9.             queue.offer(cur.left);
    10.             queue.offer(cur.right);
    11.         }
    12.         while(!queue.isEmpty()){
    13.             TreeNode tmp =queue.peek();
    14.             if(tmp!=null){
    15.                 return false;
    16.             }
    17.             queue.poll();
    18.         }
    19.         return true;
    20.     }

  • 相关阅读:
    Android 底部导航栏（四、ViewPager+RadioGroup+Fragment）简单易懂
    第十四届蓝桥杯第一期模拟赛题解[官方模拟赛]
    【Spring】Spring Bean的4种依赖注入方式
    美国NSC大规模数据泄露，涉及壳牌、戴尔、特斯拉等2000多家公司
    1flask安装配置
    〖Python 数据库开发实战 - MySQL篇⑨〗- 什么是 SQL 语言、如何创建数据逻辑库及如何创建数据表
    密码学入门——环游密码世界
    CAD如何绘制六连环图案？CAD使用圆，椭圆，直线综合练习
    一、爬虫基本概念
    四种强大且隐秘的缓存
  • 原文地址：https://blog.csdn.net/m0_61210742/article/details/125551600