【算法】二叉树

逃离我推掉我的手 2024-03-26 08:43 41阅读 0赞

## 二叉树的种类 ##

一个根节点下面只有两个子节点，称为二叉树

### 满二叉树 ###

每一层的结点数都达到最大值，则这个二叉树就是满二叉树。  
也就是说，如果一个二叉树的层数为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]

### 顺序存储 ###

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

用数组来存储二叉树如何遍历的呢？

如果父节点的数组下标是 i，那么它的左孩子就是 i \* 2 + 1，右孩子就是 i \* 2 + 2。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

所以大家要了解，用数组依然可以表示二叉树。

## 二叉树的遍历方式 ##

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

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

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

这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式

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

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

前序遍历：中左右

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

public List<Integer> preorderTraversal(TreeNode root) {
        
    
    
                List<Integer> list=new ArrayList<>();
                traverse(root,list);
                return list;
    
            }
            void traverse(TreeNode node,List<Integer> list){
        
                if(node==null){
        
                    return;
                }
                list.add(node.val);
                traverse(node.left,list);
                traverse(node.right,list);
            }

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

public List<Integer> preorderTraversal(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.right)stack.push(node.right);
               if(null!=node.left)stack.push(node.left);
           }
           return list;
        }

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

中序遍历：左中右

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

public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> list=new ArrayList<>();
            traversal(root,list);
            return list;
        }
        public void traversal(TreeNode node,List<Integer> list){
        
            if(node==null){
        
                return;
            }
            traversal(node.left,list);
            list.add(node.val);
            traversal(node.right,list);
        }

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

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 List<Integer> postorderTraversal(TreeNode root) {
        
            List<Integer> list=new ArrayList<>();
            traversal(root,list);
            return list;
    
        }
        public void traversal(TreeNode node,List<Integer> list){
        
            if(node==null){
        
                return;
            }
            traversal(node.left,list);
            traversal(node.right,list);
            list.add(node.val);
        }

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

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;
        }

![在这里插入图片描述][92c77bd9c0634d6c94378db969104c46.png]

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

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

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

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

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;
    
        }

## 二叉树的定义 ##

### 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;
      	}
    }

## 参考资料 ##

*  [代码随想录 (programmercarl.com)][_programmercarl.com]
 *

[c1de11f8d00d4756857b5b0cca471923.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ba86476887934de8b16dd5d30a5f3097.png
[710c735d49ae426fa84958bda0f740c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ff0d61609307443fb2399c0252788542.png
[06524012bab8441dac215e520ba5ee37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/0a61ebdb9e8e4205810cddc27d086c63.png
[54054352ad97441e92a52655bcd1f19f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/09bf4b4483304d8b9a9fbdf7ad2f93c8.png
[98f233324d8d41a788c224a747682958.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7b119ac8ae8f4f0e801c68158f394650.png
[187bd57ca66f41bdaa354635108980cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f14f0837b70d4020994761d29d2090e4.png
[92c77bd9c0634d6c94378db969104c46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/84930f99bdd54b0f932ee6cd8f50a375.png
[_programmercarl.com]: 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