【数据结构】树和二叉树

朱雀 2024-03-26 10:50 90阅读 0赞

## 树和二叉树的定义 ##

### 树 ###

n个结点的有限集合（n>=0）n为0时为空树。  
树中有一个根结点，它没有直接前驱，有零个或多个直接后继，  
根结点之外的n-1个结点可以划分成m个互不相交的有限集，这些有限集称为根的子树（子树互不相交）。  
![在这里插入图片描述][c6cabf9554db4afd86315891bd3451ee.png]

#### 专业术语 ####

*  结点的度：结点直接后继的个数
 *  树的度：树的所有结点的度的最大值
 *  叶子结点：也称终端结点，即度为0的结点
 *  分支结点：也称非终端结点，即度不为0的结点
 *  孩子结点：结点的直接后继 双亲结点：结点的直接前驱
 *  兄弟结点：同一双亲结点的孩子结点互称兄弟结点
 *  层次： 定义根为第一层，依次类推
 *  有序树和无序树：节点的孩子从左到右是有次序的（即不能互换）称为有序树；否则称为无序树
 *  树的深度：节点的最大层次称为树的深度或高度
 *  结点的高度不同于树的高度和深度，结点的高度指指从该结点到叶子结点的最长简单路径的边的条数，从下往上数（不同教材对结点的高度定义不同，有的从叶结点开始从1计数，有的从叶结点开始从0计数）  
    ![在这里插入图片描述][e2d93ab908c2476182aa9b5485718048.png]

### 二叉树 ###

每个结点至多只有两棵子树  
二叉树的子树有左右之分，其次序不能颠倒

## 二叉树的性质 ##

### 性质 ###

![在这里插入图片描述][56aeabda418a48248d885b828d09c30a.png]

### 满二叉树 ###

每一层的结点数都达到最大值，则这个二叉树就是满二叉树。  
也就是说，如果一个二叉树的层数为K（根节点是第1层），且结点总数是(2^k) -1 ，则它就是满二叉树。  
![在这里插入图片描述][c1de11f8d00d4756857b5b0cca471923.png_pic_center]

### 完全二叉树 ###

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。  
![在这里插入图片描述][710c735d49ae426fa84958bda0f740c0.png]

### 二叉搜索树 ###

又名**二叉排序树**，**二叉查找树**

特点：

*  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 *  它的左、右子树也分别为二叉搜索树

![在这里插入图片描述][06524012bab8441dac215e520ba5ee37.png]

### 平衡二叉搜索树 ###

又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

![在这里插入图片描述][54054352ad97441e92a52655bcd1f19f.png]

## 二叉树的存储方式 ##

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。

### 链式存储 ###

链式存储如图：  
![在这里插入图片描述][98f233324d8d41a788c224a747682958.png]

#### Java实现 ####

public class TreeNode {
        
        int val;
      	TreeNode left;
      	TreeNode right;
      	TreeNode() {
        }
      	TreeNode(int val) {
         this.val = val; }
      	TreeNode(int val, TreeNode left, TreeNode right) {
        
        		this.val = val;
        		this.left = left;
        		this.right = right;
      	}
    }

### 顺序存储 ###

![在这里插入图片描述][187bd57ca66f41bdaa354635108980cd.png]

> 顺序存储一般只适用于完全二叉树，因此树一般用链式存储

## 遍历二叉树 ##

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走。  
广度优先遍历：一层一层的去遍历。

### 深度优先遍历 ###

这里前中后，其实指的就是：遍历左子树，遍历右子树，访问根节点 中访问根节点的顺序

> 规定先访问左子树，后访问右子树

**实现方式：**  
常用递归来实现  
也可以借助栈用非递归的方式实现

#### 前序遍历 ####

前序遍历：中左右

##### 递归 #####

public void traversal(TreeNode node){
        
    		//递归结束的条件
            if(node==null){
        
                return;
            }
            list.add(node.val);//访问根节点，可以是添加到结果序列，也可以是输出等操作
            traversal(node.left);//遍历左子树
            
            traversal(node.right);//遍历右子树
        }

##### 非递归 #####

public List<Integer> preorderTraversal(TreeNode root) {
        
    
                List<Integer> result=new ArrayList<>();
                Deque<TreeNode> stack=new LinkedList<>();
                TreeNode cur=root;
    
                while(cur!=null||!stack.isEmpty()){
        
                    if(cur!=null){
        
                        result.add(cur.val);
                        stack.push(cur);
                        cur =cur.left;
                    }else{
        
                        cur=stack.poll();
                        cur=cur.right;
    
                    }
                }
                return result;
            }

非递归的一种特殊写法

public List<Integer> preorderTraversal2(TreeNode root) {
        
            List<Integer> result=new ArrayList<>();
            if(root==null){
        
                return result;//这里返回的不是null,是[]
            }
            Deque<TreeNode> stack=new LinkedList<>();
            stack.push(root);
    
            while (!stack.isEmpty()){
        
                  TreeNode node = stack.pop();
                  result.add(node.val);
                  if(node.right!=null){
        
                      stack.push(node.right);
                  }
                if(node.left!=null){
        
                    stack.push(node.left);
                }
            }
            return result;
    
        }

#### 中序遍历 ####

##### 递归 #####

public void traversal(TreeNode node){
        
    		//递归结束的条件
            if(node==null){
        
                return;
            }
            traversal(node.left);//遍历左子树
            list.add(node.val);//访问根节点，可以是添加到结果序列，也可以是输出等操作
            traversal(node.right);//遍历右子树
        }

##### 非递归 #####

递归的写法比较简单，非递归的写法稍微复杂  
递归就是自动维护了一个隐藏栈，非递归的写法就是要我们自己去创建并维护这个栈

我们创建两个变量，一个指向根结点的指针

*  如果根节点的左子树非空，就把这个根节点入栈，去遍历左子树（即把根节点更新成其左子树的根节点）
 *  如果根节点的左子树为空，说明这个根节点的左子树遍历完毕，可以访问根节点（通过返回栈顶元素同时删除来获取该节点），然后遍历右子树（即把根节点更新为右子树的根节点）
 *  进栈出栈完成，代表所有的节点都已经访问完毕。循环结束的条件是，当前根节点指针不为空或栈不为空

public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> list=new ArrayList<>();
            Deque<TreeNode> stack=new LinkedList<>();
            TreeNode cur=root;
            while(cur!=null || !stack.isEmpty()){
        
                if(cur!=null){
        
                    stack.push(cur);
                    cur=cur.left;
                }else{
        
                    cur=stack.pop();
                    list.add(cur.val);
                    cur=cur.right;
                }
            }
            return list;
        }

#### 后序遍历 ####

##### 递归 #####

public void traversal(TreeNode node){
        
    		//递归结束的条件
            if(node==null){
        
                return;
            }
            traversal(node.left);//遍历左子树
           
            traversal(node.right);//遍历右子树
            list.add(node.val);//访问根节点，可以是添加到结果序列，也可以是输出等操作
        }

##### 非递归 #####

public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> result=new ArrayList<>();
            Deque<TreeNode> stack=new LinkedList<>();
            TreeNode cur=root;
            TreeNode visited=null;
            while(cur!=null||!stack.isEmpty()){
        
                if(cur!=null){
        
                    stack.push(cur);
                    cur =cur.left;
                }else{
        
                    cur=stack.peek();
                    if(cur.right==null||cur.right==visited){
        
                        result.add(cur.val);
                        visited=cur;
                        stack.poll();
                        cur=null;
                    }else{
        
                        cur=cur.right;
                    }
                }
            }
            return result;
        }

非递归的一种特殊写法：把前序倒转

public List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> list= new ArrayList<Integer>();
           Deque<TreeNode> stack=new LinkedList<>();
           if(root==null){
        
               return list;
           }
           stack.push(root);
           while(!stack.isEmpty()){
        
               TreeNode node=stack.pop();
               list.add(node.val);          
               if(null!=node.left)stack.push(node.left);
               if(null!=node.right)stack.push(node.right);
           }
           Collections.reverse(list);
           return list;
        }

### 广度优先遍历 ###

**实现方式：**  
借助队列实现

#### 层序遍历 ####

##### 递归 #####

List<List<Integer>> result=new ArrayList<>();
        public List<List<Integer>> levelOrder(TreeNode root) {
        
    
            traverse(root,0);
            return result;
        }
        void traverse(TreeNode node,int level){
        
            if(node==null) return;
            //初始化长度
            if(result.size()<level+1){
        
                result.add(new ArrayList<>());
            }
            result.get(level).add(node.val);
            traverse(node.left,level+1);
            traverse(node.right,level+1);
    
        }

##### 迭代 #####

public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> result=new ArrayList<>();
            if(root==null){
        
                return result;
            }
    
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while (!queue.isEmpty()){
        
                ArrayList<Integer> lists = new ArrayList<>();
                int size = queue.size();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = queue.poll();
                    lists.add(node.val);
                    if(node.left!=null){
        
                        queue.offer(node.left);
                    }
                    if(node.right!=null){
        
                        queue.offer(node.right);
                    }
                }
                result.add(lists);
            }
            return result;
    
        }

## 二叉树应用 ##

### 根据遍历顺序确定二叉树 ###

> 必须有中序

#### 前序+中序 ####

[题目链接][Link 1]  
**思路**

1.  中序遍历数组的第一个值一定是二叉树的根节点，也就是左子树和右子树的分割点
2.  根据这个值找到其在前序遍历数组的位置，这个位置把前序遍历数组一分为二，第一个是其左子树，第二个是其右子树
3.  利用递归函数，返回子二叉树的根节点
4.  中序遍历数组的第二个值是此时左子树的根节点（因此，root\_index++),以此类推

class Solution {
        
        int[] preOrder;
        int root_index=0;
        HashMap<Integer,Integer> map;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            map=new HashMap<Integer,Integer>();
            for(int i=0;i<inorder.length;i++){
        
                map.put(inorder[i],i);
            }
            preOrder=preorder;
            return traversal(0,inorder.length-1);
        }
        public TreeNode traversal(int start,int end){
        
            if(start>end){
        
                return null;
            }
            int root_val=preOrder[root_index++];
            int index=map.get(root_val);
            TreeNode root=new TreeNode(root_val);
            root.left=traversal(start,index-1);
            root.right=traversal(index+1,end);
            return root;
        }
    }

#### 后序+中序 ####

[题目链接][Link 2]

class Solution {
        
        int post_index;
        int[]inOrder;
        int[]postOrder;
        Map<Integer,Integer> map=new HashMap<>();//方便找到中序遍历的对应值的位置
        public TreeNode buildTree(int[] inorder, int[] postorder) {
        
            //post是后序遍历
            inOrder=inorder;
            postOrder=postorder;
            post_index=postorder.length-1;
            for (int i = 0; i < inorder.length; i++) {
        
                map.put(inorder[i],i);
            }
            return traverse(0,inorder.length-1);
        }
        public TreeNode traverse(int begin,int end){
        
            if(begin>end){
        
                return null;
            }
            int root_val=postOrder[post_index];
            TreeNode root=new TreeNode(root_val);
            int index=map.get(root_val);
            post_index--;
            root.right=traverse(index+1,end);
            root.left=traverse(begin,index-1);
            return root;
        }
    }

### 计算二叉树的深度 ###

1.  方法一

class Solution {
        
       
        int mDepth=0;
        public int maxDepth(TreeNode root) {
        
            
           traversal(root,1);
            return mDepth;
        }
        void traversal(TreeNode node,int depth){
        
            if(node==null){
        
                return;
            }
            mDepth=Math.max(mDepth,depth);
            traversal(node.left,depth+1);
            traversal(node.right,depth+1);
    
        }
    }

1.  方法二

class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if(root==null){
        
                return 0;
            }
            return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        }
    }

1.  方法三

class Solution {
        
        public int maxDepth(TreeNode root) {
        
            int depth=0;
            if(root==null)return depth;
            Queue<TreeNode> queue=new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
        
                int size = queue.size();
                depth++;
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = queue.poll();
                    if(node.left!=null) queue.offer(node.left);
                    if(node.right!=null) queue.offer(node.right);
                }
            }
            return depth;
        }
    }

### 树、二叉树、森林之间的转化 ###

![在这里插入图片描述][b08efd7abbd0400aa2dd121298f478dd.png]  
![在这里插入图片描述][707c4a050cd64434bdf58c1dc510bd85.png]  
二叉树还原为树和森林即为上述方法的逆过程

## 哈夫曼树 ##

哈夫曼树又称最优树，是一类带权路径最短的树

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”  
**相关概念：**

*  路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。
 *  路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。
 *  结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。
 *  结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如，图 1 中结点 b 的带权路径长度为 2 \* 5 = 10 。
 *  树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为：  
    `WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3`

![在这里插入图片描述][bc444a0319e64af7a60f67eb56c932a8.png_pic_center]

### 构造算法 ###

**原则：**  
权重越大的结点离树根越近

1.  在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
2.  在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
3.  重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。  
    ![在这里插入图片描述][dee1c96468584f95b52666d66ca3c13d.png]

### 哈夫曼编码 ###

统计数字出现的频率，然后构造哈夫曼树，左子树路径为0，右子树路径为1  
![在这里插入图片描述][f3ad677641de424fa65e846155896f19.png]  
![在这里插入图片描述][a118abb2469f4e09ad07d910bdfc765a.png]

## 参考资料 ##

*  [二叉树-数据结构][-]
 *  [哈夫曼树][Link 3]
 *  [哈夫曼编码][Link 4]
 *  [代码随想录-二叉树][- 1]
 *

[c6cabf9554db4afd86315891bd3451ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/843cd84d7ea942699628b1eb2d90bead.png
[e2d93ab908c2476182aa9b5485718048.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0a7c50073b2b4e61820cbe6d1079122d.png
[56aeabda418a48248d885b828d09c30a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/83053b662ff945868c83b3bf9d09bd5b.png
[c1de11f8d00d4756857b5b0cca471923.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/5a154047f1824b81903bea80efa9b24a.png
[710c735d49ae426fa84958bda0f740c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/895641c7dac145c7957b3e7edbca4c1b.png
[06524012bab8441dac215e520ba5ee37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e39e966acf47470393fa8e5e7e586197.png
[54054352ad97441e92a52655bcd1f19f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e97b12dbabcf45a3b4256fac16a8fdbb.png
[98f233324d8d41a788c224a747682958.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1f16e76ef59d45da909308a718be3332.png
[187bd57ca66f41bdaa354635108980cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a9defe260c19454b94315f302448df75.png
[Link 1]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[Link 2]: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[b08efd7abbd0400aa2dd121298f478dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/829489795ff7400e99be514a2dfa4c44.png
[707c4a050cd64434bdf58c1dc510bd85.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/3d5246e042f843bbb4673d1d9fd19c20.png
[bc444a0319e64af7a60f67eb56c932a8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fffd1524873a4122b74a0465d98b6842.png
[dee1c96468584f95b52666d66ca3c13d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/88e980534c914085b176b4e5726c96cc.png
[f3ad677641de424fa65e846155896f19.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/cc65f0f9d785411d8f8257420f9ad8af.png
[a118abb2469f4e09ad07d910bdfc765a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/09596712664a466d8fe93a31d14e9535.png
[-]: https://blog.csdn.net/bay_Tong/article/details/107048340
[Link 3]: http://c.biancheng.net/view/3398.html
[Link 4]: https://blog.csdn.net/Young_IT/article/details/106730343
[- 1]: https://www.programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%A7%8D%E7%B1%BB