devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构 -- 树

作者：花生_TL007 | 2024-04-29 15:53:36

赞

踩

数据结构 -- 树

1、树的基本概念

1.1 树的定义

（1）树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：

  • 有且仅有一个特定的称为根的结点。
  • 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

（2）树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

  • 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
  • 树中所有结点可以有零个或多个后继。
  • 因此n个结点的树中有n-1条边。

1.2 基本术语

（1）下面结合图示来说明一下树的一些基本术语和概念。

  1. 考虑结点K。根A到结点K的唯一路径上的任意结点，称为结点K的祖先。如结点B是结点K的祖先，而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲，而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟结点，如结点K和结点L有相同的双亲E，即K和L为兄弟。
  2. 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。如结点B的度为2，结点D的度为3，树的度为3。
  3. 度大于0的结点称为分支结点（又称非终端结点）；度为0（没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个结点的分支数就是该结点的度。
  4. 结点的层次从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。双亲在同一层的结点互为堂兄弟，图中结点G与E,F,H,I,J互为堂兄弟。
  5. 结点的深度是从根结点开始自顶向下逐层累加的。
  6. 结点的高度是从叶结点开始自底向上逐层累加的。
  7. 树的高度（或深度）是树中结点的最大层数。图中树的高度为4。
  8. 有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换,称该树为有序树，否则称为无序树。假设图为有序树，若将子结点位置互换，则变成一棵不同的树。
  9. 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
  10. 森林。森林是m (m≥0）棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。

（2）树的性质

  • 树中的结点数等于所有结点的度数加1。
  • 度为 m 的树中第 i 层上至多有m^(i − 1) 个结点（i>=1）。
  • 高度为h 的m 叉树至多有 (m^(h-1))/(m-1)个结点。
  • 具有n 个结点的m 叉树的最小高度为[ log m ( n ( m − 1 ) + 1 ) ]。

2、二叉树

2.1 二叉树的概念

1、二叉树的定义

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树是n (n≥0) 个结点的有限集合：

  • 为空二叉树，即n=0。
  • 由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。二叉树的5种基本形态如图所示。

2、几个特殊的二叉树

（1）斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

（2）满二叉树

一棵高度为h ，且含有 2^h-1个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2。可以对满二叉树按层序编号：约定编号从根结点（根结点编号为1 ）起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为i的结点，若有双亲，则其双亲为i / 2 ，若有左孩子，则左孩子为2i；若有右孩子，则右孩子为 2i+1。

（3）完全二叉树

高度为h 、有n 个结点的二叉树，如图所示。其特点如下：

  • 若i ≤ n / 2 ，则结点i 为分支结点，否则为叶子结点。
  • 叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
  • 若有度为1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子。
  • 按层序编号后，一旦出现某结点（编号为i ）为叶子结点或只有左孩子，则编号大于i 的结点均为叶子结点。
  • 若n 为奇数，则每个分支结点都有左孩子和右孩子；若n 偶数，则编号最大的分支结点（编号为n / 2 ）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

（4）二叉排序树

二叉排序树，又称二叉查找树。或者是一颗空树，或者是满足以下性质的二叉树：

  • 若其左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若其右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 其左、右子树也分别为二叉排序树。

（5）构造二叉排序树：

我们对于给定序列，取其第一个点为根结点，然后依次选择后续节点边比较边插入。如果比当前结点小，往该节点左子树移动比较，如果比当前结点大，则往该节点右子树移动比较。直到到一个待比较位置为空的位置，就是该节点的最终位置。

设输入序列为：（30,11,18,4,55,19,15,70,58）

（5）平衡二叉树

平衡二叉树，又称AVL树。 它或者是一颗空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡树，且左子树和右子树的深度之差的绝对值不超过1。

平衡因子：又称BF，定义为该节点的左子树的深度减去它的右子树深度。则平衡二叉树的所有节点的平衡因子只可能是-1、0、1。只要二叉树上有一个结点的平衡因子BF绝对值大于1，那么二叉树就是不平衡的。

案例1：下图不是「平衡二叉树」因为有节点子树高度差大于 1 。

案例2：下图是「平衡二叉树」。

2.2 二叉树的性质

（1）任意一棵树，若结点数量为n，则边的数量为n − 1。

（2）非空二叉树上的叶子结点数等于度为2 的结点数加1，即n0 = n2 + 1。

（3）非空二叉树上第k 层上至多有 2^(k-1) 个结点( k ≥ 1 ) 。

（4）高度为h 的二叉树至多有 2^h-1个结点( h ≥ 1 )。

（5）对完全二叉树按从上到下、从左到右的顺序依次编号1 , 2.. ∗ , n ，则有以下关系：

  1. i > 1 时，结点i 的双亲的编号为i / 2 ，即当i 为偶数时， 它是双亲的左孩子；当i为奇数时，它是双亲的右孩子。
  2. 当 2i≤n 时，结点i 的左孩子编号为 2i，否则无左孩子。
  3. 当2i + 1 ≤ n 时，结点i 的右孩子编号为 2i+1，否则无右孩子。

（6）结点i 所在层次（深度）为 log 2(i) + 1。

（7）具有n 个（n > 0）结点的完全二叉树的高度为 log 2(n)+1。

3、遍历二叉树

3.1 先序遍历

先序遍历（PreOrder）的操作过程如下：

若二叉树为空，则什么也不做，否则，

1）访问根结点；
2）先序遍历左子树；
3）先序遍历右子树。

3.2 中序遍历

中序遍历( InOrder)的操作过程如下：
若二叉树为空，则什么也不做，否则，
1）中序遍历左子树；
2）访问根结点；
3）中序遍历右子树。

3.3 后序遍历

后序遍历(PostOrder) 的操作过程如下：
若二叉树为空，则什么也不做，否则，
1）后序遍历左子树；
2）后序遍历右子树；
3）访问根结点。

3.4 层次遍历

下图为二叉树的层次遍历，即按照箭头所指方向，按照1,2,3, 4的层次顺序，对二叉树中的各个结点进行访问。

要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，访问出队结…如此反复，直至队列为空。

4、二叉树的遍历实现

（1）TreeNode类

  1. public class TreeNode {
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  5.     TreeNode(){}
  6.     TreeNode(int val,TreeNode left,TreeNode right){
  7.         this.val = val;
  8.         this.left = left;
  9.         this.right = right;
  10.     }
  11. }

（2）递归遍历方式

  1. public List<Integer> inorderTraversal(TreeNode root) {
  2.     List<Integer> res = new ArrayList<Integer>();
  3.     preorder(root, res);
  4.     return res;
  5. }
  6.  
  7. public void inorder(TreeNode root, List<Integer> res) {
  8.     if (root == null)
  9.         return;
  10.     inorder(root.left, res);
  11.     res.add(root.val);
  12.     inorder(root.right, res);
  13. }
  14.  
  15. public void preorder(TreeNode root, List<Integer> res) {
  16.     if (root == null) {
  17.         return;
  18.     }
  19.     res.add(root.val);
  20.     preorder(root.left, res);
  21.     preorder(root.right, res);
  22. }
  23.  
  24. public void postorder(TreeNode root, List<Integer> res) {
  25.     if (root == null)
  26.         return;
  27.     postorder(root.left, res);
  28.     postorder(root.right, res);
  29.     res.add(root.val);
  30. }

（3）非递归遍历方式

  1. public List<Integer> inorderTraversal(TreeNode root){
  2.     List<Integer> res = new ArrayList<Integer>();
  3.     Stack<TreeNode>stk = new Stack<>();
  4.     while(root!=null || !stk.isEmpty()){
  5.         while (root!=null){
  6.             stk.push(root);
  7.             root = root.left;
  8.         }
  9.         root = stk.pop();
  10.         res.add(root.val);
  11.         root = root.right;
  12.     }
  13.     return res;
  14. }
  15. // 根左右
  16. public List<Integer> preorderTraversal(TreeNode root){
  17.     List<Integer> res = new ArrayList<Integer>();
  18.     Stack<TreeNode>stk = new Stack<>();
  19.     while (root != null || !stk.isEmpty()){
  20.         while (root != null){
  21.             res.add(root.val);
  22.             stk.push(root);
  23.             root = root.left;
  24.         }
  25.         TreeNode cur = stk.pop();
  26.         root = cur.right;
  27.     }
  28.     return res;
  29. }
  30. /**
  31.  *左右根 --> 根右左（翻转）
  32.  * 对照前序遍历，为根左右，只需要把前序 left的地方改为 right
  33.  * 即根左右(前序) ---将左右位置变换---> 根右左 ---再翻转---> 左右跟
  34.  * */
  35. public List<Integer>postorderTraversal(TreeNode root) {
  36.     List<Integer> res = new ArrayList<Integer>();
  37.     Stack<TreeNode> stk = new Stack<>();
  38.     while (root != null || !stk.isEmpty()) {
  39.         while (root != null) {
  40.             res.add(root.val);
  41.             stk.push(root);
  42.             root = root.right;
  43.         }
  44.         TreeNode cur = stk.pop();
  45.         root = cur.left;
  46.     }
  47.     Collections.reverse(res);
  48.     return res;
  49. }
  50. public List<List<Integer>> levelOrder(TreeNode root){
  51.     List<List<Integer>>ret = new ArrayList<List<Integer>>();
  52.     if(root == null)
  53.         return ret;
  54.  
  55.     Queue<TreeNode>queue = new LinkedList<TreeNode>();
  56.     queue.offer(root);
  57.     while (!queue.isEmpty()){
  58.         List<Integer>level = new ArrayList<Integer>();
  59.         int curLevelSize = queue.size();
  60.         for(int i=0;i<curLevelSize;i++){
  61.             TreeNode node = queue.poll();
  62.             level.add(node.val);
  63.             if(node.left != null)
  64.                 queue.offer(node.left);
  65.             if(node.right != null)
  66.                 queue.offer(node.right);
  67.         }
  68.         ret.add(level);
  69.     }
  70.     return ret;
  71. }
  72. public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  73.     List<List<Integer>>ret = new ArrayList<List<Integer>>();
  74.     if(root == null)
  75.         return ret;
  76.     int curLevel = 0;
  77.     Queue<TreeNode>queue = new LinkedList<TreeNode>();
  78.     queue.offer(root);
  79.     while (!queue.isEmpty()){
  80.         List<Integer>level = new ArrayList<Integer>();
  81.         int curLevelSize = queue.size();
  82.         for(int i=0;i<curLevelSize;i++){
  83.             TreeNode node = queue.poll();
  84.             level.add(node.val);
  85.             if(node.left != null)
  86.                 queue.offer(node.left);
  87.             if(node.right != null)
  88.                 queue.offer(node.right);
  89.         }
  90.         curLevel ++;
  91.         if(curLevel % 2 != 0)
  92.             Collections.reverse(level);
  93.         ret.add(level);
  94.     }
  95.     return ret;
  96. }

参考链接1：数据结构：树(Tree)【详解】_数据结构 树-CSDN博客

参考链接2：动态查找表之二叉排序树和平衡二叉树（图解+代码详解）-CSDN博客

参考链接3：二叉树三种遍历（递归+迭代）Java_java二叉树迭代遍历-CSDN博客


 

本文为学习笔记，所参考文章均已附上链接，若有疑问请私信！

创作不易，如果对你有点帮助的话麻烦点个赞支持一下！

新手小白，欢迎留言指正！

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号