二叉树入门

矫情吗；* 2023-10-03 18:01 22阅读 0赞

## 树的基本定义 ##

树是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就 是说它是根朝上，而叶朝下的。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_17_color_FFFFFF_t_70_g_se_x_16][]

**树具有以下特点：**

1.每个结点有零个或多个子结点；

2.没有父结点的结点为根结点；

3.每一个非根结点只有一个父结点；

4.每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树；

## 树的相关术语 ##

**结点的度：** 一个结点含有的子树的个数称为该结点的度；

**叶结点：** 度为0的结点称为叶结点，也可以叫做终端结点

**分支结点：** 度不为0的结点称为分支结点，也可以叫做非终端结点

**结点的层次：** 从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推

**结点的层序编**号：将树中的结点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数。

**树的度：**树中所有结点的度的最大值

**树的高度(深度)：**树中结点的最大层次

**森林：**m（m>=0）个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根 结点，森林就变成一棵树

**孩子结点：**一个结点的直接后继结点称为该结点的孩子结点

**双亲结点(父结点)：**一个结点的直接前驱称为该结点的双亲结点

**兄弟结点：**同一双亲结点的孩子结点间互称兄弟结点

## 二叉树的基本定义 ##

二叉树就是度不超过2的树(每个结点最多有两个子结点)

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16][]

**满二叉树：**一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

**完全二叉树：**叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

## ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 2][]二叉查找树的创建 ##

### 二叉树的结点类 ###

#### 结点类API设计： ####

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

结点类代码实现：

//结点类
        private class Node {
            //存储键
            private Key key;
            //存储值
            private Value value;
            //记录左子结点
            private Node left;
            //记录右子结点
            private Node right;
    
            //构造方法
            public Node(Key key, Value value, Node left, Node right) {
                this.key = key;
                this.value = value;
                this.left = left;
                this.right = right;
            }
        }

### 二叉查找树API设计 ###

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

### 二叉查找树实现 ###

**插入方法put实现思想：**

1.如果当前树中没有任何一个结点，则直接把新结点当做根结点使用

2.如果当前树不为空，则从根结点开始：

2.1如果新结点的key小于当前结点的key，则继续找当前结点的左子结点；

2.2如果新结点的key大于当前结点的key，则继续找当前结点的右子结点；

2.3如果新结点的key等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值即可。

**查询方法get实现思想：**

从根节点开始：

1.如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；

2.如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；

3.如果要查询的key等于当前结点的key，则树中返回当前结点的value。

**删除方法delete实现思想：**

1.找到被删除结点；

2.找到被删除结点右子树中的最小结点minNode

3.删除右子树中的最小结点

4.让被删除结点的左子树称为最小结点minNode的左子树，让被删除结点的右子树称为最小结点minNode的右子树

5.让被删除结点的父节点指向最小结点minNode

### 二叉树的基础遍历 ###

**1、前序遍历：**先访问根结点，再访问左子结点，最后访问右子结点

**前序遍历实现步骤：**

①、把当前结点的key放入队列中

②、找到当前结点的左子树，如果不为空，则递归遍历左子树

③、找到当前结点的右子树，如果不为空，则递归遍历右子树

**2、中序遍历：**先访问左子结点，再访问根结点，最后访问右子结点

**中序遍历实现步骤：**

①、找到当前结点的左子树，如果不为空，则递归遍历左子树

②、把当前结点的key放入队列中

③、找到当前结点的右子树，如果不为空，则递归遍历右子树

**3、后序遍历：**先访问左子结点，再访问右子结点，最后访问根结点

**后序遍历实现步骤：**

①、找到当前结点的左子树，如果不为空，则递归遍历左子树

②、找到当前结点的右子树，如果不为空，则递归遍历右子树

③、把当前结点的key放入队列中

三种遍历结果，如下图所示：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

### 代码实现： ###

/**
     * @author: xuzhilei
     * @create: 2021-12-08 
     * @description: 二叉查找树
     **/
    public class BinaryTree<Key extends Comparable<Key>, Value> {
        //结点类
        private class Node {
            //存储键
            private Key key;
            //存储值
            private Value value;
            //记录左子结点
            private Node left;
            //记录右子结点
            private Node right;
    
            //构造方法
            public Node(Key key, Value value, Node left, Node right) {
                this.key = key;
                this.value = value;
                this.left = left;
                this.right = right;
            }
        }
    
        //记录根结点
        private Node root;
        //记录二叉树中元素个数
        private int number;
    
        //初始化构造方法
        public BinaryTree() {
            this.root = null;
            this.number = 0;
        }
    
        //获取树中元素个数
        public int size() {
            return number;
        }
    
        //向树中添加元素key-value
        public void put(Key key, Value value) {
            root = put(root, key, value);
        }
    
    
        //向指定的子树x中添加key-value,并返回添加元素后新的子树
        private Node put(Node x, Key key, Value value) {
            //如果x子树为空
            if (x == null) {
                //元素个数加1
                number++;
                return new Node(key, value, null, null);
            }
            //如果x子树不为空
            //比较x结点的键和key的大小
            int comp = key.compareTo(x.key);
            if (comp > 0) {
                //如果key大于x结点的键，则继续找x结点的右子树
                x.right = put(x.right, key, value);
            } else if (comp < 0) {
                //如果key小于x结点的键，则继续找x结点的左子树
                x.left = put(x.left, key, value);
            } else {
                //如果key等于x结点的键，则替换x结点的值为value
                x.value = value;
            }
            return x;
        }
    
        //查找树中指定key对应的value
        public Value get(Key key) {
            return get(root, key);
        }
    
        //从指定的树x中查找key对应的值
        private Value get(Node x, Key key) {
            //如果子树x为空
            if (x == null) {
                return null;
            }
            //如果子树x不为空
            //比较key和x结点的键的大小
            int comp = key.compareTo(x.key);
            if (comp > 0) {
                //如果key大于x结点的键，则继续查找x结点的右子树
                return get(x.right, key);
            } else if (comp < 0) {
                //如果key小于x结点的键，则继续查找x结点的左子树
                return get(x.left, key);
            } else {
                //如果key等于x结点的键，则返回x结点的值
                return x.value;
            }
        }
    
        //删除树中key对应的value，即删除此key对应的结点
        public void delete(Key key) {
            delete(root, key);
        }
    
        //删除子树x中key对应的value,并返回删除后的新树
        private Node delete(Node x, Key key) {
            //x子树为空
            if (x == null) {
                return null;
            }
            //x子树不为空
            //比较x结点的键与key的大小
            int comp = key.compareTo(x.key);
            if (comp > 0) {
                //如果key大于x结点的键，则继续查找x结点的右子树
                x.right = delete(x.right, key);
            } else if (comp < 0) {
                //如果key小于x结点的键，则继续查找x结点的左子树
                x.left = delete(x.left, key);
            } else {
                //如果key等于x结点的键,此时找到了要删除的结点
    
                //让元素个数-1
                number--;
                //如果x的左子结点为空，则直接返回右子结点即可
                if (x.left == null) {
                    return x.right;
                }
                //如果x的右子结点为空，则直接返回左子结点即可
                if (x.right == null) {
                    return x.left;
                }
                //找到右子树中的最小结点
                //先让x的右子结点为最小的结点
                Node minNode = x.right;
                while (minNode.left != null) {
                    minNode = minNode.left;
                }
                //删除x的右子树的最小的结点
                Node n = x.right;
                while (n.left != null) {
                    if (n.left.left == null) {
                        //将最小的结点置为null
                        n.left = null;
                    } else {
                        n = n.left;
                    }
                }
    
                //让x结点的左子结点成为minNode的左子结点
                minNode.left = x.left;
                //让x结点的右子结点成为minNode的右子结点
                minNode.right = x.right;
                //让x记录minNode结点（即让x结点的父结点指向minNode）
                x = minNode;
            }
            //将当前结点返回
            return x;
        }
    
    
        //查找整个树中最小的键
        public Key min() {
            return min(root).key;
        }
    
        //查找指定树x中最小的键所在的结点
        private Node min(Node x) {
            //判断x是否有左子结点，如果有，则继续向左找，如果没有，则直接返回x结点
            if (x.left != null) {
                return min(x.left);
            } else {
                return x;
            }
        }
    
        //在整个树中查找最大的键
        public Key max() {
            return max(root).key;
        }
    
        //在指定树x中查找最大的键所在的结点
        private Node max(Node x) {
            //判断x是否有右子结点，如果有，则继续向右找，如果没有，则直接返回x结点
            if (x.right != null) {
                return max(x.right);
            } else {
                return x;
            }
        }
    
        //使用前序遍历获取整个树中的所有键
        public Queue<Key> preErgodic() {
            Queue<Key> keys = new Queue<>();
            preErgodic(root, keys);
            return keys;
        }
    
        //使用前序遍历获取指定树x中所有的键
        private void preErgodic(Node x, Queue<Key> keys) {
            if (x == null) {
                return;
            }
    
            //把x结点的key放入keys中
            keys.enqueue(x.key);
            //递归遍历x的左子树
            if (x.left != null) {
                preErgodic(x.left, keys);
            }
            //递归遍历x的右子树
            if (x.right != null) {
                preErgodic(x.right, keys);
            }
        }
    
    
        //使用中序遍历获取整个树中的所有键
        public Queue<Key> midErgodic() {
            //声明一个队列
            Queue<Key> keys = new Queue<>();
            midErgodic(root, keys);
            return keys;
        }
    
        //使用中序遍历获取指定树x中所有的键
        private void midErgodic(Node x, Queue<Key> keys) {
            if (x == null) {
                return;
            }
            //如果x的左子结点不为空，递归遍历左子结点
            if (x.left != null) {
                midErgodic(x.left, keys);
            }
            //将x的key放入队列中
            keys.enqueue(x.key);
            //如果x的右子结点不为空，递归遍历右子结点
            if (x.right != null) {
                midErgodic(x.right, keys);
            }
        }
    
        //使用后序遍历获取整个树中的所有键
        public Queue<Key> afterErgodic(){
            //声明一个队列
            Queue<Key> keys = new Queue<>();
            afterErgodic(root,keys);
            return keys;
        }
        //使用后序遍历获取指定树x中所有的键
        private void afterErgodic(Node x,Queue<Key> keys){
            if (x == null){
                return;
            }
            //如果x的左子结点不为空，递归遍历左子树
            if (x.left != null){
                afterErgodic(x.left,keys);
            }
            //如果x的右子结点不为空，递归遍历右子树
            if (x.right != null){
                afterErgodic(x.right,keys);
            }
            //将x结点的key放入队列中
            keys.enqueue(x.key);
        }
    
        //使用层序遍历获取整个树中的所有键
        public Queue<Key> layerErgodic(){
            //创建一个队列，用来存放所有的键
            Queue<Key> keys = new Queue<>();
            //再创建一个队列，用来存放结点
            Queue<Node> nodes = new Queue<>();
    
            //首先将根结点放入队列中
            nodes.enqueue(root);
    
            while (!nodes.isEmpty()){
                //从队列中弹出一个结点
                Node node = nodes.dequeue();
                //将此结点的key放入队列中
                keys.enqueue(node.key);
                //如果此结点还有左结点，则将左结点放入队列中
                if (node.left != null){
                    nodes.enqueue(node.left);
                }
                //如果此结点还有右结点，则将右结点放入队列中
                if (node.right != null){
                    nodes.enqueue(node.right);
                }
            }
            return keys;
        }
    
        //计算整个树的最大深度
        public int maxDepth(){
            return maxDepth(root);
        }
        //计算指定树x的最大深度
        private int maxDepth(Node x){
            if (x == null){
                return 0;
            }
    
            //初始化树x的最大深度
            int max = 0;
            //初始化x的左子树的最大深度
            int maxL = 0;
            //初始化x的右子树的最大深度
            int maxR = 0;
    
            //如果x还有左子树，则继续递归获取左子树的最大深度
            if (x.left != null){
                maxL = maxDepth(x.left);
            }
            //如果x还有右子树，则继续递归获取右子树的最大深度
            if (x.right != null){
                maxR = maxDepth(x.right);
            }
    
            //比较左子树的最大深度和右子树的最大深度，取较大值+1即为当前x的最大深度
            max = maxL > maxR ? maxL+1:maxR+1;
    
            return max;
        }
    
    }

**测试代码：**

/**
     * @author: xuzhilei
     * @create: 2021-12-08
     * @description: 二叉树测试
     **/
    public class BinaryTreeTest {
        public static void main(String[] args) {
            //创建二叉树
            BinaryTree<String, String> bt = new BinaryTree<>();
            //binaryTree.put(4,"二哈");
            //binaryTree.put(1,"张三");
            //binaryTree.put(3,"李四");
            //binaryTree.put(5,"王五");
            //System.out.println(binaryTree.size());
            //binaryTree.put(1,"老三");
            //System.out.println(binaryTree.get(1));
            //System.out.println(binaryTree.size());
            //
            //binaryTree.delete(1);
            //System.out.println(binaryTree.get(1));
            //System.out.println(binaryTree.size());
    
    
    
            bt.put("E", "5");
            bt.put("B", "2");
            bt.put("G", "7");
            bt.put("A", "1");
            bt.put("D", "4");
            bt.put("F", "6");
            bt.put("H", "8");
            bt.put("C", "3");
            //测试前序遍历
            //Queue<String> keys = bt.preErgodic();
            //for (String key : keys) {
            //    System.out.println(key + "="+ bt.get(key));
            //}
    
            //测试中序遍历
            //Queue<String> keys = bt.midErgodic();
            //for (String key : keys) {
            //    System.out.println(key + "="+ bt.get(key));
            //}
        //测试后序遍历
        //    Queue<String> keys = bt.afterErgodic();
        //    for (String key : keys) {
        //        System.out.println(key + "=" + bt.get(key));
        //    }
    
            //测试层序遍历
            Queue<String> keys = bt.layerErgodic();
            for (String key : keys) {
                System.out.println(key + "=" + bt.get(key));
            }
    
            //测试树的最大深度
            int maxDepth = bt.maxDepth();
            System.out.println("树的最大深度为："+maxDepth);
        }
    }

**测试部分结果：**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 6][]

以上是个人随手敲的demo，如有不正确的地方，可以在下方留言指正，谢谢。与各位CSDN的伙伴们共勉，每天记录一点点，每天进步一点点

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_17_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1f33cc60e3664281aea2571c8b2ad905.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_17,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/4c3e0075441746f095f97296b3f4dcaa.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/dc99468887b249949e8fb91f2030aa7c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/9f3ffc6f492842d4a4503906e6446c57.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/91df0df7ddae46ea8b8204944db59f8d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/fccbdfbf2c23403f8106acebd7f78335.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/4bccbe71b27c4c65a7c4b0a403f9368b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5rW35rex5LiN6KeB6bK4_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/1bc7381ca7bf437cb61f0512ffce87c3.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5rW35rex5LiN6KeB6bK4,size_20,color_FFFFFF,t_70,g_se,x_16