数据结构——树结构【二叉树与二分搜索树】

╰+哭是因爲堅強的太久メ 2022-05-09 05:08 238阅读 0赞

## 关于树的一些概念 ##

### 节点的度 ###

> 结点拥有的子树数称为结点的度。度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。除根结点以外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

![70][]

### 层次与深度 ###

![70 1][]

![70 2][]

### 有序与无序树 ###

![70 3][]

### 树林 ###

## ![70 4][] ##

## 二叉树 ##

在我们初学JavaSE时候肯定写过这么一个程序：

猜100以内的整数，注意猜的次数不能超过7个，回答者只回答大了还是小了？本质上就是一个二分查找方法

![70 5][]

![70 6][]

### 斜树【特殊的二叉树】 ###

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

![70 7][]               ![70 8][]

### 完全二叉树 ###

![70 9][]

![70 10][]

### 满二叉树 ###

![70 11][]

![70 12][]

### 二叉树性质 ###

![70 13][]

**性质3证明**

**设n为总结点数，n1为度为1的结点数，n2为度为2的结点数,n0为终端结点数(叶子节点数)**  
![70 14][]

一个节点对应一个分支，分支线数为n-1是因为根节点A没有父节点，也没有分支。

![70 15][]

二叉树特点：

> 1、**二叉树具有唯一的根节点**
> 
> 2、二叉树**每个节点都有两个孩子**，左孩子、右孩子
> 
> 3、叶子节点为13、22、29、42
> 
> 4、二叉树每个节点**最多有一个父亲**，根节点没有父亲节点
> 
> 5、**二叉树具有天然的递归结构，每个节点的左子树是二叉树，每个节点的右子树也是二叉树**
> 
> 6、**二叉树不一定都是"满"的**，二叉树"空"的地方可以看做NULL，即使一个节点也称为二叉树

## 二分搜索树 ##

![70 16][]

二分搜索树的特点

> 1、二分搜索树也是二叉树
> 
> 2、二分搜索树的**每个节点的值大于左子树**的所有节点的值，小于其右子树的所有节点值
> 
> 3、每一棵子树也是二分搜索树
> 
> 4、存储的元素必须具有可比较性，如树中存储学生信息，可以根据学生学号进行比较

### 二分搜索树的代码实现 ###

我们的二分搜索树支持泛型，但树中的元素应该具有可比较性，故需要继承Comparable

主要设计有二分搜索树的add()添加、contains()查找、删除、遍历【前序、中序、后序】(深度优先遍历)   ，【层序遍历】(广度)

/**
             *               5
             *             /   \
             *            3     7
             *           / \   / \
             *          2  4  6   8
             */

前序遍历：  根   左   右

5 3 2 4 7 6 8

private void preOrder(Node root){
            //递归终止条件
            if(root == null)
                return;
            System.out.println(root.e);
            preOrder(root.left);
            preOrder(root.right);
        }

中序遍历：  左   根   右   【实现排序】

2 3 4 5 6 7 8

private void midOrder(Node root){
            if(root == null)
                return;
            midOrder(root.left);
            System.out.println(root.e);
            midOrder(root.right);
        }

后序遍历     左    右    根   【释放内存，释放完孩子，再释放根】

2 4 3 6 8 7 5

private void postOrder(Node root){
            if(root == null){
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.println(root.e);
        }

具体代码实现二分搜索树

package cn.itcats.tree.searchTree;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * 我们的二分搜索树支持泛型，但树中的元素应该具有可比较性，故需要继承Comparable
     *
     * @param <E>
     */
    public class BinarySearchTree<E extends Comparable<E>> {
    
        private class Node {
            public E e;
            //左孩子
            public Node left;
            //右孩子
            public Node right;
    
            public Node(E e) {
                this.e = e;
                this.left = null;
                this.right = null;
            }
        }
    
        private Node root;
        //二分搜索树的节点个数
        private int size;
    
        public BinarySearchTree() {
            root = null;
            size = 0;
        }
    
        //获取二分搜索树的节点个数
        public int getSize() {
            return size;
        }
    
        //判断二分搜索树节点是否为空
        public boolean isEmpty() {
            return size == 0;
        }
    
        //向二分搜索树中添加元素
        public void add(E e) {
            root = add(root, e);
        }
    
        /**
         * 以Node为根的二分搜索树中插入元素E，递归算法
         * 返回插入新节点后二分搜索树的根
         * 对compareTo()方法的补充
         * 如果指定的数与参数相等返回0。
         * 如果指定的数小于参数返回 -1。
         * 如果指定的数大于参数返回 1。
         *
         * @param root 根节点 --- 递归时为每层的根节点
         * @param e    需要添加的元素
         */
        private Node add(Node root, E e) {
            if (root == null) {
                size++;
                return new Node(e);
            }
    
            //向左深入递归
            if (e.compareTo(root.e) < 0)
                root.left = add(root.left, e);
                //向右深入递归
            else if (e.compareTo(root.e) > 0)
                //else if 不用else 是因为没有判断e和root.e相等情况,相等则不处理
                root.right = add(root.right, e);
            //将添加成功后的node返回
            return root;
        }
    
        //查询二分搜索树是否包含某个元素
        public boolean contains(E e) {
            return contains(root, e);
        }
    
        //构建私有的递归查找方法
        private boolean contains(Node root, E e) {
            if (root == null)
                return false;
            if (root.e.compareTo(e) == 0)
                return true;
            else if (root.e.compareTo(e) < 0)
                //向左搜索
                return contains(root.left, e);
            else
                //root.e.compareTo(e) > 0 向右搜索
                return contains(root.right, e);
        }
    
        //二分搜索树的前序遍历
        public void preOrder() {
            preOrder(root);
        }
    
        //私有方法,传递root为根的二分搜索树,递归算法
        private void preOrder(Node root) {
            //递归终止条件
            if (root == null)
                return;
            System.out.println(root.e);
            preOrder(root.left);
            preOrder(root.right);
        }
    
    
        //非递归实现前序遍历
        public void preOrderNR() {
            //使用Stack模拟系统栈
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                //让栈顶元素出栈
                Node top = stack.pop();
                System.out.println(top.e);
    
                //先压入右孩子
                if (top.right != null)
                    stack.push(top.right);
                //再压入左孩子
                if (top.left != null)
                    stack.push(top.left);
            }
        }
    
        //层序遍历————借助队列
        public void levelOrder() {
            //借助队列模拟层序遍历
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                Node poll = queue.poll();
                System.out.println(poll.e);
    
                //左节点入队
                if(poll.left != null)
                    queue.offer(poll.left);
                //右节点入队
                if(poll.right != null)
                    queue.offer(poll.right);
            }
        }
    
        //寻找二分搜索树的最小元素,最左节点一定是最小值
        public E mininum(){
            if(isEmpty()){
                throw new IllegalArgumentException("树为空");
            }
            return mininum(root).e;
        }
    
        //查找最小节点值
        private Node mininum(Node root){
            //一直递归至root.left == null，返回最小节点
            if(root.left == null)
                return root;
            return mininum(root.left);
        }
    
        //寻找二分搜索树的最大元素,最右节点一定是最大值
        public E maxnum(){
            if(isEmpty()){
                throw new IllegalArgumentException("树为空");
            }
            return maxnum(root).e;
        }
    
        //查找最大节点值
        private Node maxnum(Node root){
            if(root.right == null)
                return root;
            return maxnum(root.right);
        }
    
        //从二分搜索树中删除最小值所在节点,返回最小值
        public E removeMin(){
            E ret = mininum();
            root = removeMin(root);
            return ret;
        }
    
        //删除以node为根的二分搜索树中最小节点
        //返回删除后新的二分搜索树的根
        private Node removeMin(Node root){
            if(root.left == null){
                Node rightNode = root.right;
                root.right = null;
                size--;
                return rightNode;
            }
            root.left = removeMin(root.left);
            return root;
        }
    
    
        //从二分搜索树中删除最大值所在节点,返回最大值
        public E removeMax(){
            E ret = mininum();
            root = removeMax(root);
            return ret;
        }
    
        //删除以node为根的二分搜索树中最大节点
        //返回删除后新的二分搜索树的根
        private Node removeMax(Node root){
            if(root.right == null){
                Node leftNode = root.left;
                root.left = null;
                size--;
                return leftNode;
            }
            root.right = removeMin(root.right);
            return root;
        }
    
        //从二分搜索树中删除元素为e的节点
        public void remove(E e){
            root = remove(root,e);
        }
    
        //删除以node为根的二分搜索树中值为e的节点,递归算法
        //返回删除节点后新的二分搜索树的根
        private Node remove(Node node , E e){
            if(node == null)
                return null;
            //e小于根节点,向左深入
            if(e.compareTo(node.e) < 0){
                node.left = remove(node.left,e);
                return node;
            }
            //e大于根节点,向右深入
            else if(e.compareTo(node.e) > 0){
                node.right = remove(node.right,e);
                return node;
            }else{  //e == node.e 找到要删除的元素
                //待删除节点左子树为空
                if(node.left == null){
                    Node rightNode = node.right;
                    node.right = null;
                    size -- ;
                    return rightNode;
                }
                //待删除节点右子树为空
                if(node.right == null){
                    Node leftNode = node.left;
                    node.left = null;
                    size -- ;
                    return leftNode;
                }
                //待删除节点左右子树均不为空
                //找到比待删除节点大的最小节点(或找到比待删除节点小的最大元素),即待删除节点右子树的最小节点
                //用这个节点顶替待删除节点的位置
                Node successor = mininum(node.right);
                successor.right = removeMin(node.right);
                successor.left = node.left;
                node.left = node.right = null;
                return successor;
            }
    
    
        }
    
    
    
    
        //中序遍历
        public void midOrder() {
            midOrder(root);
        }
    
        private void midOrder(Node root) {
            if (root == null)
                return;
            midOrder(root.left);
            System.out.println(root.e);
            midOrder(root.right);
        }
    
        //后续遍历
        public void postOrder() {
            postOrder(root);
        }
    
        private void postOrder(Node root) {
            if (root == null) {
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.println(root.e);
        }
    
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            generateBSTString(root, 0, sb);
            return sb.toString();
        }
    
        //生成以node为根节点,深度为depth的描述二叉树的字符串
        private void generateBSTString(Node root, int depth, StringBuilder sb) {
            if (root == null) {
                sb.append(generateDepthString(depth) + "null\n");
                return;
            }
            sb.append(generateDepthString(depth) + root.e + "\n");
            generateBSTString(root.left, depth + 1, sb);
            generateBSTString(root.right, depth + 1, sb);
        }
    
        private String generateDepthString(int depth) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < depth; i++) {
                sb.append("--");
            }
            return sb.toString();
        }
    }

测试类

package cn.itcats.tree.searchTree;
    
    public class BSTTest {
        public static void main(String[] args) {
            BinarySearchTree<Integer> bst = new BinarySearchTree<>();
            /**
             *               5
             *             /   \
             *            3     7
             *           / \   / \
             *          2  4  6   8
             */
            int[] num = {5,3,7,6,8,4,2};
              for(Integer n : num)
                  bst.add(n);
            //前序遍历  5 3 2 4 7 6 8
            bst.preOrder();
            System.out.println();
            //中序遍历  2 3 4 5 6 7 8
            bst.midOrder();
            System.out.println();
            //后序遍历  2 4 3 6 8 7 5
            bst.postOrder();
    //        System.out.println();
    //        System.out.println(bst);
        }
    }

### 前序遍历的非递归形式【使用栈模拟系统栈】 ###

//非递归实现前序遍历
        public void preOrderNR(){
            //使用Stack模拟系统栈
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()){
                //让栈顶元素出栈
                Node top = stack.pop();
                System.out.println(top.e);
    
                //先压入右孩子
                if(top.right != null)
                    stack.push(top.right);
                //再压入左孩子
                if(top.left != null)
                    stack.push(top.left);
            }
        }

### 层序遍历【借助队列】——广度优先遍历 ###

//层序遍历————借助队列
        public void levelOrder() {
            //借助队列模拟层序遍历
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                Node poll = queue.poll();
                System.out.println(poll.e);
    
                //左节点入队
                if(poll.left != null)
                    queue.offer(poll.left);
                //右节点入队
                if(poll.right != null)
                    queue.offer(poll.right);
            }
        }

[70]: /images/20220509/4df54588891b452e85114ad4160463d0.png
[70 1]: /images/20220509/4ef71c21d21e47409ff4216a36d532ce.png
[70 2]: /images/20220509/ba5f2439a08845818719962fae13bbfe.png
[70 3]: /images/20220509/09ee6b923ade466eb2fd4887adf83add.png
[70 4]: /images/20220509/aff451033c4a454aa1641eeae714411c.png
[70 5]: /images/20220509/7b282f463a8c446aad0918a0ed4826fc.png
[70 6]: /images/20220509/c8e05d77086242f89fa7e28154a8fa2e.png
[70 7]: https://img-blog.csdn.net/20181001173649968?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 8]: /images/20220509/4ff57eae979647aea43a34e7e91e02df.png
[70 9]: /images/20220509/446f49c064074b97aae04898756e0923.png
[70 10]: /images/20220509/25755cf706084edebf998da8f4df87ef.png
[70 11]: /images/20220509/48b95da528164aceb826b83b7fcdda06.png
[70 12]: /images/20220509/2166f9568d6f478684f390d43b193b3f.png
[70 13]: /images/20220509/fff5434ffa8d4f48b56d854a4482967d.png
[70 14]: /images/20220509/36d8e37401754c878dda5f8956be423d.png
[70 15]: /images/20220509/4bc64682c9604ba2b80fef7afb683623.png
[70 16]: /images/20220509/c5f91d02e5104bd59138b9499ae92acb.png