树---二叉树、顺序存储二叉树、线索化二叉树、二叉搜索树（BST）、平衡二叉树（AVL）

妖狐艹你老母 2023-07-06 14:53 22阅读 0赞

### 文章目录 ###

*   *  树
     *  二叉树
     *   *   *  二叉树的遍历和查找
             *  顺序存储二叉树
             *  线索化二叉树
             *  二叉搜索树BST（二叉排序树、二叉查找树）
             *  平衡二叉树（AVL树）
             *   *   *  红黑树

## 树 ##

树形结构：

*  每个结点有零个或多个子结点；
 *  没有父结点的结点称为根结点；
 *  每一个非根结点有且只有一个父结点；
 *  除了根结点外，每个子结点可以分为多个不相交的子树；

关于树形结构中的一些术语：

*  节点的高度=节点到叶子节点的最长路径（边数）
 *  节点的深度=根节点到这个节点所经历的边的个数
 *  节点的层数=节点的深度+1
 *  树的高度=根节点的高度  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]

## 二叉树 ##

每个节点最多有两个子节点  
**满二叉树**：一棵二叉树，除叶子节点外，每个节点都有左右两个子节点，总节点个数=2^n - 1，n为层数  
**完全二叉树**：一棵二叉树，所有叶子节点都在最后一层或者倒数第二层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他各层节点个数都要达到最大  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]

#### 二叉树的遍历和查找 ####

*  深度优先遍历（DFS）:  
    前序遍历: 先输出父节点，再遍历左子树和右子树  
    中序遍历: 先遍历左子树，再输出父节点，再遍历右子树  
    后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
 *  广度优先遍历（BFS）  
    按照高度顺序，从上往下逐层遍历节点；先遍历上层节点再遍历下层节点

中序+后序、中序+先序可以唯一确定一棵二叉树

public class Node { 
        public int val;
        public Node left;
        public Node right;
    
        public Node(int val) { 
            this.val = val;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "val=" + val +
                    '}';
        }
    }

public class BinaryTreeDemo { 
        public static void main(String[] args) { 
            Node node1 = new Node(1);
            Node node2 = new Node(2);
            Node node3 = new Node(3);
            Node node4 = new Node(4);
            Node node5 = new Node(5);
    
            node1.left = node2;
            node1.right = node3;
            node2.left = node4;
            node2.right = node5;
    
            preOrder(node1);
            System.out.println("-------------");
            midOrder(node1);
            System.out.println("-------------");
            tailOrder(node1);
    
            int target = 5;
            System.out.println(preOrderSearch(node1, target));
            System.out.println(midOrderSearch(node1, target));
            System.out.println(tailOrderSearch(node1, target));
            
        }
    
        //前序遍历
        public static void preOrder(Node root) { 
            if(null == root) return;
    
            System.out.println(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    
        //中序遍历
        public static void midOrder(Node root) { 
            if(null == root) return;
    
            midOrder(root.left);
            System.out.println(root.val);
            midOrder(root.right);
        }
    
        //后序遍历
        public static void tailOrder(Node root) { 
            if(null == root) return;
    
            tailOrder(root.left);
            tailOrder(root.right);
            System.out.println(root.val);
        }
    
        //前序遍历-查找
        public static Node preOrderSearch(Node root, int target) { 
            if(null == root) return null;
    
            //如果在当前节点找到目标值，则返回
            if(root.val == target) { 
                return root;
            }
    
            Node result = null;
    
            //当前节点没找到，继续到左子节点查找
            result = preOrderSearch(root.left, target);
            //如果在左子节点找到，则返回
            if(result != null) { 
                return result;
            }
    
            //左子节点没找到，返回右子节点的查找结果
            return preOrderSearch(root.right, target);
        }
    
        //中序遍历-查找
        public static Node midOrderSearch(Node root, int target) { 
            if(null == root) return null;
            Node result = null;
    
            //先在左子节点中找，找到则返回
            result = midOrderSearch(root.left, target);
            if(result != null) { 
                return result;
            }
    
            //左子节点没找到，继续在当前节点中找
            if(root.val == target) { 
                return root;
            }
    
            //左子节点没找到，返回右子节点查找结果
            return midOrderSearch(root.right, target);
        }
        
        //后序遍历-查找
        public static Node tailOrderSearch(Node root, int target) { 
            if(null == root) return null;
            
            Node result = null;
            result = tailOrderSearch(root.left, target);
            
            if(result != null) { 
                return result;
            }
            
            result = tailOrderSearch(root.right, target);
            if(result != null) { 
                return result;
            }
            
            return (root.val == target) ? root : null;
        }
    }

#### 顺序存储二叉树 ####

从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组。  
数组\{1,2,3,4,5,6,7\}和下面的二叉树可以相互转换：  
![在这里插入图片描述][20200220130738132.png]  
顺序存储二叉树的特点:

*  顺序存储二叉树通常只考虑完全二叉树
 *  第n个元素的左子节点为 2 \* n + 1
 *  第n个元素的右子节点为 2 \* n + 2
 *  第n个元素的父节点为 (n-1) / 2
 *  n : 表示二叉树中的第几个元素（从0计数）

顺序存储二叉树的前序遍历：

public class ArrBinaryTreeDemo { 
        public static void main(String[] args) { 
            int[] arr = { 1,2,3,4,5,6,7};
            ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
            arrBinaryTree.preOrder(1);
        }
    }
    
    class ArrBinaryTree{ 
        private int[] arr;
    
        public ArrBinaryTree(int[] arr) { 
            this.arr = arr;
        }
    
        public void preOrder() { 
            this.preOrder(0);
        }
    
        /** * 前序遍历 * @param index 数组下标 */
        public void preOrder(int index) { 
            if(null == arr || 0 == arr.length) return;
    
            System.out.println(arr[index]);
    
            //向左遍历
            if(index * 2 + 1 < arr.length) { 
                preOrder(index * 2 + 1);
            }
    
            //向右遍历
            if(index * 2 + 2 < arr.length) { 
                preOrder(index * 2 + 2);
            }
        }
    }

#### 线索化二叉树 ####

线索化二叉树是为了充分利用各个节点的左右指针，含有n个节点的二叉树有n+1个空指针域，利用这些空指针域存放指向该节点在某种遍历次序下的前驱和后继节点的指针，这种附加的指针称为“线索”。  
加上了线索的二叉链表称为线索链表，相应的，二叉树称为**线索二叉树（Thread BinaryTree）**。根据线索性质的不同，线索二叉树可分为**前序线索二叉树**、**中序线索二叉树**、**后序线索二叉树**。  
此外，一个节点的前一个节点称为前驱节点，后一个节点称为后继节点，这里的前后指的是遍历过程中的前后。

比如下图中左边这颗二叉树的中序遍历序列为\{8, 3, 10, 1, 14, 6\}，加上中序遍历线索之后如右图所示：  
![在这里插入图片描述][20200220152712392.png]

public class ThreadedBinaryTreeDemo { 
        public static void main(String[] args) { 
            ThreadedNode node1 = new ThreadedNode(1);
            ThreadedNode node3 = new ThreadedNode(3);
            ThreadedNode node6 = new ThreadedNode(6);
            ThreadedNode node8 = new ThreadedNode(8);
            ThreadedNode node10 = new ThreadedNode(10);
            ThreadedNode node14 = new ThreadedNode(14);
    
            node1.left = node3;
            node1.right = node6;
            node3.left = node8;
            node3.right = node10;
            node6.left = node14;
    
            ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
            threadedBinaryTree.midThreadedTree(node1);
    
            threadedBinaryTree.midThreadedTreeList(node1);
        }
    }
    
    class ThreadedBinaryTree{ 
        private ThreadedNode preNode; //存储当前节点的前驱节点
    
        //中序线索化二叉树
        public void midThreadedTree(ThreadedNode node) { 
            if(null == node) return;
            //1. 线索化左子树
            midThreadedTree(node.left);
            //2. 线索化当前节点
            //2.1 线索化左指针
            if(null == node.left) { 
                node.left = preNode; //左指针指向前驱节点
                node.leftType = 1;
            }
            //这里还不能线索化当前节点的右指针，因为还不知道当前节点的后继节点
            //2.2 因为当前节点是前驱节点的后继节点，所以要在这里线索化前驱节点的右指针
            //从这里可以看出，一个节点的后继节点是当遍历到它的后继节点的时候才去处理的
            if(preNode != null && null == preNode.right) { 
                preNode.right = node;
                preNode.rightType = 1;
            }
    
            //当前节点设置为前驱节点
            preNode = node;
            //3. 线索化右子树
            midThreadedTree(node.right);
        }
    
        //遍历中序线索化二叉树
        public void midThreadedTreeList(ThreadedNode root) { 
            ThreadedNode node = root;
    
            while(node != null) { 
                //从左子树中找到第一个leftType=1的节点
                while(0 == node.leftType) { 
                    node = node.left;
                }
    
                System.out.println(node.val);
    
                //遍历输出当前节点的后继节点
                while(1 == node.rightType) { 
                    node = node.right;
                    System.out.println(node.val);
                }
    
                //当前节点的右指针不再指向后继节点，因此再从当前节点的右节点开始下一次循环
                node = node.right;
            }
        }
    }

#### 二叉搜索树BST（二叉排序树、二叉查找树） ####

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

/** * 二叉搜索树（二叉查找树、二叉排序树） */
    public class BinarysearchtreeDemo { 
        public static void main(String[] args) { 
            Node root = new Node(10);
            Node n9 = new Node(9);
            Node n14 = new Node(14);
            Node n13 = new Node(13);
            Node n16 = new Node(16);
            Node n11 = new Node(11);
    
            root.left = n9;
            root.right = n14;
            n14.left = n13;
            n14.right = n16;
            n13.left = n11;
    
            BinarySearchTree binarySearchTree = new BinarySearchTree();
            //递归查找
            Node result1 = binarySearchTree.searchRecursion(root, 14);
            System.out.println(result1);
            //非递归查找
            Node result2 = binarySearchTree.search(root, 14);
            System.out.println(result2);
    
            //插入
            binarySearchTree.insert(root, 8);
    
            //删除
            Node result3 = binarySearchTree.delete(root, 10);
            if(result3 != null) {  //删除的是根节点
                root = result3;
            }
        }
    }
    
    class BinarySearchTree{ 
        //递归查找
        public Node searchRecursion(Node node, int target) { 
            if(null == node) return null;
            
            if(target < node.val) { 
                return searchRecursion(node.left, target);
            }else if(target > node.val) { 
                return searchRecursion(node.right, target);
            }else{ 
                return node;
            }
        }
    
        //非递归查找
        public Node search(Node node, int target) { 
            Node currentNode = node;
    
            while(currentNode != null) { 
                if(target < currentNode.val) { 
                    currentNode = currentNode.left;
                }else if(target > currentNode.val) { 
                    currentNode = currentNode.right;
                }else{ 
                    return currentNode;
                }
            }
    
            return null;
        }
    
        //插入元素（如果存在值相等的元素，则向右子树查找）
        public void insert(Node root, int val) { 
            if(null == root) { 
                root = new Node(val);
            }
            Node currentNode = root;
    
            //设置为true，因为循环内部一定会达到退出条件
            while(true) { 
                if(val < currentNode.val) { 
                    if(null == currentNode.left) { 
                        currentNode.left = new Node(val);
                        return;
                    }
    
                    currentNode = currentNode.left;
                }else{ 
                    if(null == currentNode.right) { 
                        currentNode.right = new Node(val);
                        return;
                    }
    
                    currentNode = currentNode.right;
                }
            }
        }
    
        /** * 删除元素（设节点为D），分为如下几种情况： * 1. D是叶子节点，则直接删除 * 2. D只有一个子节点，则让D节点的父节点指向该子节点 * 3. D有左右两个子节点，这种情况可以转换为第1种或者第2种情况： * 3.1 遍历D的右子节点，从中找到最小的节点记为T（找到的这个节点肯定是叶子结点或者只有一个子节点） * 3.2 将T节点值赋值给D节点 * 3.3 转换为删除T节点 */
        public Node delete(Node root, int target) { 
            Node deleteNode = root;
            Node deleteNParent = null;
            //找到要删除的节点和其父节点
            while(deleteNode != null && deleteNode.val != target) { 
                deleteNParent = deleteNode;
                if(target < deleteNode.val) { 
                    deleteNode = deleteNode.left;
                }else{ 
                    deleteNode = deleteNode.right;
                }
            }
    
            //没有找到要删除的节点
            if(null == deleteNode) return null;
    
            //删除节点有左右两个子节点
            if(deleteNode.left != null && deleteNode.right != null) { 
                deleteNParent = deleteNode;
                Node minNode = deleteNode.right;  //minNode指向右子树中最小节点
                while(minNode.left != null) { 
                    deleteNParent = minNode;
                    minNode = minNode.left;
                }
    
                deleteNode.val = minNode.val;
                deleteNode = minNode;
            }
    
            Node child;  //要删除节点的子节点
            if(null == deleteNode.left && null == deleteNode.right) { 
                child = null;
            }else{ 
                child = deleteNode.left != null ? deleteNode.left : deleteNode.right;
            }
    
            if(null == deleteNParent) {   //删除的是根节点
                return child;
            }else if(deleteNParent.left == deleteNode) { 
                deleteNParent.left = child;
            }else{ 
                deleteNParent.right = child;
            }
    
            return null;
        }
    }

二叉搜索树是常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度和树的高度成正比，理想情况下，时间复杂度是O(logn)。但是，二叉搜索树在频繁动态更新过程中，可能会出现树的高度远大于logn的情况，极端情况下二叉树还会退化成链表一样的结构。  
数列\{1,2,3,4,5,6\}，要求创建一颗二叉排序树(BST)：  
![在这里插入图片描述][20200302110808834.png]  
这颗BST树存在的问题分析:

*  左子树全部为空，从形式上看，更像一个单链表.
 *  插入速度没有影响，但是查询速度明显降低(因为需要依次比较), 不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢

解决方案-平衡二叉树(AVL)

#### 平衡二叉树（AVL树） ####

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。具有以下特点：

*  它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1
 *  左右两个子树都是一棵平衡二叉树

平衡二叉树的常用实现方法有AVL、红黑树、替罪羊树、Treap、伸展树等。在工程中，一般会使用红黑树实现平衡二叉树。但是很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于1），比如红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。如果我们现在设计一个新的平衡二叉查找树，只要树的高度不比log2n大很多（以2为底n的对数，一棵极其平衡的满二叉树或完全二叉树的高度大约是log2n），尽管它不符合我们前面讲的严格的平衡二叉查找树的定义，但我们仍然可以说，这是一个合格的平衡二叉查找树。比如红黑树，它的高度接近2log2n。

###### 红黑树 ######

红黑树的英文是“Red-Black Tree”，简称R-B Tree。它是一种不严格的平衡二叉查找树。红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

*  根节点是黑色的；
 *  每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
 *  任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
 *  每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

为什么使用红黑树而不是AVL树呢？  
AVL树严格平衡，虽然查找效率高，但是插入和删除节点效率低，因为要维持平衡而大量调整节点。红黑树只满足近似平衡，要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近log2n就好了。红黑树的查找效率只比AVL树低一点，但是插入和删除的效率比AVL高很多。  
红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，而实际上红黑树的总体性能更好。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200220092500725.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200220094627861.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw,size_16,color_FFFFFF,t_70
[20200220130738132.png]: https://img-blog.csdnimg.cn/20200220130738132.png
[20200220152712392.png]: https://img-blog.csdnimg.cn/20200220152712392.png
[20200302110808834.png]: https://img-blog.csdnimg.cn/20200302110808834.png