搜索

数据结构之二叉树

良辰

共 9357字，需浏览 19分钟

 · 2022-03-02

树的基本定义

之前实现符号表中，不难看出，符号表的增删查操作，随着元素个数N的增多，其耗时也是线性增多的，时间复杂度都是O(n)，为解决这个问题，需要学习树这种数据结构。

树是由n个有限结点组成的一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树。

树具有以下特点：

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

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

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

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


树的相关术语

结点的度：

一个结点含有子树的个数称为该结点的度。

叶结点：

度为0的结点称为叶结点。

分支结点:

度不为0的结点为分支结点。

结点的层次：

从根结点开始，根结点的层次为1，根的直接后继为2.

结点的层序编号：

将树中的结点，按照从上到下，从左到右的次序排成一个线性序号。

树的度：

树中所有结点的度的最大值。

树的高度(深度)：

树中结点的最大层次。

森林：

m（m>0）个互不相交的树的集合。将一颗非空树的根结点去掉，树就变成了森林。

孩子结点：

一个结点的之间后继称为该结点的孩子结点。

双亲结点（父结点）：

一个结点的直接前驱称为该结点的双亲结点。

兄弟结点：

同一双亲的孩子结点之间互称为兄弟结点。


二叉树的基本定义

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

满二叉树：

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

完全二叉树:

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

二叉查找树创建

二叉树的结点类

类图：


代码实现：

static class Node<K,V>{
    private Node<K,V> left;
    private Node<K,V> right;
    private K key;
    private V value;

    public Node(K key,V value,Node<K,V> left,Node<K,V> right){
        this.key = key;
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
二叉查找树类图


二叉查找树代码实现
public class BinaryTree<K extends Comparable<K>, V> {
    //记录树中元素个数
    private int size;
    //记录树的根节点
    private Node<K, V> root;

    /**
     * 构造方法
     */
    public BinaryTree() {
        this.size = 0;
        this.root = null;
    }

    /**
     * 向树中插入一个键值对
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        root = put(root, key, value);
    }

    /**
     * 给指定树上添加一个键值对，并返回新树
     *
     * @param node
     * @param key
     * @param value
     * @return
     */
    private Node<K, V> put(Node<K, V> node, K key, V value) {
        //如果是第一个结点，则作为根节点添加到树中
        if (node == null) {
            size++;
            return new Node<>(key, value, null, null);
        }
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            //如果不是第一个结点，从根结点开始查找，如果比根节点的key小，就找根节点的左子树
            node.left = put(node.left, key, value);
        } else if (cmp > 0) {
            // 如果比根节点的key大则找根节点的右子树
            node.right = put(node.right, key, value);
        } else {
            //如果等于其中一个结点的key值，则更新对应的值。
            node.value = value;
        }
        return node;
    }

    /**
     * 根据key从树中查找对应的值
     *
     * @param key
     * @return
     */
    public V get(K key) {
        return get(root, key);
    }

    private V get(Node<K, V> node, K key) {
        if (node == null) {
            return null;
        }
        //从根结点开始
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            //如果要查找的key小于当前结点的key，则继续查找当前节点左子树
            return get(node.left, key);
        } else if (cmp > 0) {
            //如果要查找的key大于当前结点的key，则继续查找当前节点右子树
            return get(node.right, key);
        } else {
            //如果要查找的key等于当前结点的key，则返回当前节点的值
            return node.value;
        }

    }

    /**
     * 删除树中对应key的结点
     *
     * @param key
     */
    public void remove(K key) {
        remove(root, key);
    }

    /**
     * 删除指定树下面对应key的结点
     *
     * @param node
     * @param key
     * @return
     */
    private Node<K, V> remove(Node<K, V> node, K key) {
        //如果树为null
        if (node == null) {
            return null;
        }
        //如果树不为null
        //从根结点开始
        int cmp = key.compareTo(node.key);
        if (cmp < 0) {
            //如果要查找的key小于当前结点的key，则继续查找当前节点左子树
            node.left = remove(node.left, key);
        } else if (cmp > 0) {
            //如果要查找的key大于当前结点的key，则继续查找当前节点右子树
            node.right = remove(node.right, key);
        } else {
            //元素个数-1
            size--;
            //如果要查找的key等于当前结点的key，则删除当前结点
            //如果左子树为null或者是叶子结点
            if (node.left == null) {
                return node.right;
            }
            //如果右子树为null或者是叶子结点
            if (node.right == null) {
                return node.left;
            }
            //如果左子树和有子树都不为空，找到右子树中最小的结点代替需要删除的结点
            Node<K, V> minNode = node.right;
            Node<K, V> minPreNode = node.right;
            while (minNode.left != null) {
                if (minNode.left.left == null) {
                    minPreNode = minNode;
                }
                minNode = minNode.left;
            }
            //删除minNode的父节点的指向
            minPreNode.left = null;
            //让minNode的右子树等于该删除结点的右子树
            minNode.left = node.left;
            //左子树等于该删除结点的左子树
            minNode.right = node.right;
            //让该删除结点的父节点指向x
            node = minNode;
        }
        return node;
    }

    public int size() {
        return size;
    }

    static class Node<K, V> {
        private Node<K, V> left;
        private Node<K, V> right;
        private K key;
        private V value;

        public Node(K key, V value, Node<K, V> left, Node<K, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

}
二叉查找树其他便捷方法

查找二叉树中最小的键

比如我们经常需要查找排名第一的记录。

/**
 * 获取树中最小的键
 * @return
 */
public K min(){
    return min(root).key;
}

/**
 * 获取指定树中最小键所在的结点
 * @param node
 * @return
 */
private Node<K,V> min(Node<K,V> node){
    //树中最小的键是左子树中最左边的结点，可递归查找左子树
    if(node.left == null){
        return node;
    }
    return min(node.left);
}


查找二叉树中最大的键

比如我们经常需要查找最后一名的记录。

/**
 * 获取树中最大的键
 * @return
 */
public K max(){
    return max(root).key;
}

/**
 * 获取指定树中最大键所在的结点
 * @param node
 * @return
 */
private Node<K,V> max(Node<K,V> node){
    //树中最大的键是右子树中最右边的结点，可递归查找右子树
    if(node.right == null){
        return node;
    }
    return max(node.right);
}
二叉树的基础遍历

很多情况下，我们可能需要像遍历数组一样遍历树，但是树状结构和线性结构不一样，它没办法从头开始依此向后遍历，那么应该怎么遍历树。

我们可以把树简单理解成根节点、左子树和右子树组成，按照结点什么时候被访问，可以把二叉树的遍历分为以下三种方式：

  1. 前序遍历

    先访问根节点，再访问左子树，最后访问有右子树

  2. 中序遍历

    先访问左子树，再访问根节点，最后访问右子树

  3. 后续遍历

    先访问左子树，再访问右子树，最后再访问根节点

前序遍历

前序遍历API：

public Queue preErgodic()：使用前序遍历，获取整个树中所有的键

private void preErgodic(Node node,Queue keys)：使用前序遍历，把指定树node中的所有键放入到keys队列中

实现步骤

  1. 把当前结点的key放入到队列中

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

  3. 找到当前节点的右子树，如果不为空，递归遍历右子树

代码：

/**
 * 前序遍历
 * -根左右
 *
 * @return
 */
public Queue<K> preErgodic() {
    Queue<K> keys = new Queue<>();
    preErgodic(root, keys);
    return keys;
}

/**
 * 使用前序遍历，把指定树node中的所有键放入到keys队列中
 * 根左右
 * @param node
 * @param keys
 */
private void preErgodic(Node<K, V> node, Queue<K> keys) {
    if (node == null) {
        return;
    }
    //把node结点的key放入keys中
    keys.enqueue(node.key);
    //递归遍历node结点的左子树
    if (node.left != null) {
        preErgodic(node.left, keys);
    }
    //递归遍历node结点的右子树
    if (node.right != null) {
        preErgodic(node.right, keys);
    }
}
中序遍历

中序遍历API：

public Queue midErgodic()：使用中序遍历，获取整个树中所有的键

private void midErgodic(Node node,Queue keys)：使用中序遍历，把指定树node中的所有键放入到keys队列中

实现步骤

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

  2. 把当前结点的key放入到队列中

  3. 找到当前节点的右子树，如果不为空，递归遍历右子树

代码：

/**
 * 中序遍历
 * - 左根右
 * @return
 */
public Queue<K> midErgodic() {
    Queue<K> keys = new Queue<>();
    midErgodic(root, keys);
    return keys;
}

/**
 * 使用中序遍历，把指定树node中的所有键放入到keys队列中
 * 左根右
 * @param node
 * @param keys
 */
private void midErgodic(Node<K, V> node, Queue<K> keys) {
    if (node == null) {
        return;
    }
    //递归遍历node结点的左子树
    if (node.left != null) {
        midErgodic(node.left, keys);
    }
    //把node结点的key放入keys中
    keys.enqueue(node.key);
    //递归遍历node结点的右子树
    if (node.right != null) {
        midErgodic(node.right, keys);
    }
}
后续遍历

后序遍历API：

public Queue afterErgodic()：使用后序遍历，获取整个树中所有的键

private void afterErgodic(Node node,Queue keys)：使用后序遍历，把指定树node中的所有键放入到keys队列中

实现步骤

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

  2. 找到当前节点的右子树，如果不为空，递归遍历右子树

  3. 把当前结点的key放入到队列中

代码：

/**
 * 后序遍历
 * - 左右根
 *
 * @return
 */
public Queue<K> afterErgodic() {
    Queue<K> keys = new Queue<>();
    afterErgodic(root, keys);
    return keys;
}

/**
 * 使用后序遍历，把指定树node中的所有键放入到keys队列中
 * 左右根
 *
 * @param node
 * @param keys
 */
private void afterErgodic(Node<K, V> node, Queue<K> keys) {
    if (node == null) {
        return;
    }
    //递归遍历node结点的左子树
    if (node.left != null) {
        afterErgodic(node.left, keys);
    }
    //递归遍历node结点的右子树
    if (node.right != null) {
        afterErgodic(node.right, keys);
    }
    //把node结点的key放入keys中
    keys.enqueue(node.key);
}
二叉树的层序遍历

从根结点（第一层）开始，依此向下，获取每一层所有结点的值。有二叉树如下：

那么层序遍历的结果是：EBGADFHC

层序遍历API：

public Queue layerErgodic()：使用层序遍历，获取整个树的键

实现步骤：

  1. 创建队列存储每一层的结点

  2. 使用循环从队列中弹出一个结点

    1. 获取当前结点的key

    2. 如果当前节点的左子节点不为空，则把左子节点放入队列

    3. 如果当前节点的右子节点不为空，则把右子节点放入队列

代码：

/**
 * 使用层序遍历，把指定树node中的所有键放入到keys队列中
 *
 * @return
 */
public Queue<K> layerErgodic() {
    //定义两个队列，一个用来存放key，一个用来存放结点
    Queue<K> keys = new Queue<>();
    Queue<Node<K, V>> nodes = new Queue<>();
    //默认，在队列中放入根结点
    nodes.enqueue(root);
    while (!nodes.isEmpty()) {
        //从队列中弹出结点，把key放入keys中
        Node<K, V> node = nodes.dequeue();
        keys.enqueue(node.key);
        //判断当前结点是否还有左子树，如果有则放入nodes中
        if (node.left != null) {
            nodes.enqueue(node.left);
        }
        //判断当前结点是否还有右子树，如果有则放入nodes中
        if (node.right != null) {
            nodes.enqueue(node.right);
        }
    }
    return keys;
}
二叉树的最大深度问题

需求：

给定一棵树，请计算树的最大深度。(树的根结点到最远叶子结点的最长路径上的结点数)

上面这棵树的最大深度为4

实现：

最大深度API:

public int maxDepth()：计算整个树的最大深度

private int maxDepth(Node node)：计算指定树node的最大深度

实现步骤：

  1. 如果根结点为null，则最大深度为0

  2. 计算左子树的最大深度

  3. 计算右子树的最大深度

  4. 比较左子树和右子树的最大深度，取较大值+1即为整个树的最大深度

代码：

/**
 * 获取整个树的最大深度
 *
 * @return
 */
public int maxDepth() {
    return maxDepth(root);
}

/**
 * 获取指定树的最大深度
 *
 * @param node
 * @return
 */
private int maxDepth(Node<K, V> node) {
    if (node == null) {
        return 0;
    }
    //node左子树的最大深度
    int maxL = 0;
    //node右子树的最大深度
    int maxR = 0;
    //计算node结点左子树的最大深度
    if (node.left != null) {
        maxL = maxDepth(node.left);
    }
    //计算node结点右子树的最大深度
    if (node.right != null) {
        maxR = maxDepth(node.right);
    }
    //比较左子树和右子树的最大深度，取较大值+1，返回
    return maxL > maxR ? maxL + 1 : maxR + 1;
}
折纸问题

需求：

请把一段纸条竖着放在桌子上，然后从纸条的下边向上边对折1次，压出折痕后展开，此时折痕是凹下去的，即折痕突起方向为纸条的背面。如果连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕，下折痕，上折痕。

分析：

我们把对折后的纸张翻过来，让粉色朝下，这时把第一次对折产生的折痕为根节点，第二次对折产生的下折痕就是该节点的左子节点，上折痕为右子节点，这样就可以使用树形结构来描述对折后产生的折痕。

这颗树的特点是：

  1. 根结点为下折痕

  2. 左子结点为下折痕

  3. 右子结点为上折痕

代码实现：

public class PageFoldingTest {

    public static void main(String[] args) {
        //模拟折纸过程，产生树
        Node<String> tree = createTree(2);
        //遍历树，打印每个结点
        printTree(tree);
    }

    //通过模拟对折N次，产生树
    public static Node<String> createTree(int n){
        Node<String> root = null;
        if(n<=0){
            return null;
        }
        //第一次对折
        root = new Node<>("down",null,null);
        //不是第一次对折
        for (int i = 1; i < n; i++) {
            //定义一个辅助队列，通过层序遍历的思想，找到叶子结点，给叶子结点添加子结点
            Queue<Node<String>> queue = new Queue<>();
            queue.enqueue(root);
            //循环遍历队列
            while (!queue.isEmpty()) {
                //从队列中弹出一个结点
                Node<String> temp = queue.dequeue();
                //如果有左子结点，则把右子结点放入队列中
                if (temp.left != null){
                    queue.enqueue(temp.left);
                }
                //如果有右子结点，则把右子结点放入队列中
                if (temp.right != null){
                    queue.enqueue(temp.right);
                }
                //如果同时没有右子结点和左子结点，则证明该结点是叶子结点，只需要给该结点添加左子结点和右子结点即可
                if(temp.left == null && temp.right == null){
                    temp.left = new Node<>("down",null,null);
                    temp.right = new Node<>("up",null,null);
                }
            }
        }
        return root;
    }

    //打印树中每个结点，中序遍历。
    public static void printTree(Node<String> tree){
        if(tree == null){
            return;
        }
        Queue<Node<String>> queue = new Queue<>();
        //打印左子树的每个结点
        if(tree.left != null){
            printTree(tree.left);
        }
        //打印当前结点
        System.out.print(tree.item+"\t");
        //打印右子树的每个结点
        if(tree.right != null){
            printTree(tree.right);
        }
    }

    //结点类
   private static class Node<T>{
        //存储元素
        private T item;
        private Node<T> left;
        private Node<T> right;

        public Node(T item, Node<T> left, Node<T> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }
}




浏览 13
点赞
评论
收藏
分享

手机扫一扫分享

举报
评论
图片
表情
推荐
Java版【数据结构与算法】的天花板，收藏好，慢慢看
Java 版数据结构与算法来了，堪称 java 版数据结构与算法的天花板，需要学数据结构与算法的，刷这套就可以了，目录如下，文末附教程地址。基础数据结构-001-二分查找-算法描述基础数据结构-002-二分查找-算法实现基础数据结构-003-二分查找-问题1-循环条件基础数据结构-004-二分查找-
路人甲Java
0
带你玩转Linux系统之lscpu命令
链接：https://bbs.huaweicloud.com/blogs/422603一、lscpu命令介绍lscpu 是一个 Linux 命令，用于显示CPU架构的详细信息。它可以用来查看 CPU 的型号、主频、架构、虚拟化支持等。二、lscpu命令的使用帮助2.1 命令格式lscpu [选项]2
良许Linux
0
C语言基础之动态内存操作汇总
来源：机器之心1、堆区空间申请#include <stdlib.h> //头文件void *malloc(size_t size);//函数size表示申请的空间字节数函数的返回值：成功：返回值空间起始地址失败：NULL特点：分配指定大小的内存空间；分配的内存空间是连续的；需要手动释放
良许Linux
0
大模型并行训练指南：通俗理解Megatron-DeepSpeed之模型并行与数据并行（下）
文末《大模型项目开发线上营》秒杀倒计时↓↓↓接前文：（上）篇>>>大模型并行训练指南：通俗理解Megatron-DeepSpeed之模型并行与数据并行（上）（中）篇>>>大模型并行训练指南：通俗理解Megatron-DeepSpeed之模型并行与数据并行（中）06
七月在线实验室
10
以环境之“优”谋发展之“势”
好的营商环境是生产力、竞争力，更是吸引力。近年来，我县始终坚持“项目为王、环境是金”工作导向，践行101%服务理念，大力优化营商环境，厚植高质量发展沃土，为县域经济发展提供强大支撑。 紧盯重大项目，推动企业投产增效  江苏伟复能源有限公司主要生产铅酸动力蓄电池，产品直供
盱眙老妹
0
100种分析思维模型之：本质思维
你好，我是林骥。北京有个出租车司机，原来住在四合院，房改之后，他就把四合院卖了，买了一辆桑塔纳，当时感觉风光无限，现如今则是后悔不已。假如这个出租车司机当时具有本质思维，也许就不会做出卖房买车的决定。下面介绍 100 种分析思维模型的第 97 种：本质思维，它能帮助我们更好地看清事物的本质，进而做出
林骥
18
职业之思|设计师产品交付的 4 个阶段
点击"设计微日记"关注，和我一起成长 本文故事皆为个人职业发展经验之谈 如有雷同纯属巧合 大家好，我是益达，很高兴能够再次见到你，今天和大家聊一聊关于产品设计师的交付，通俗的说，就是设计师如何通过专业能力...
设计微日记
0
亲测极其适合广大考研学子的数据结构编程网站
今日推荐 Hello Algo  - go.com/  本项目旨在创建一本开源、免费、对新手友好的数据结构与算法入门教程。 全书采用 动画图解 ，结构化地讲解数据结构与算法知识，内容清晰易懂，学习曲线平滑。 算法源代码皆可一键运...
PHP在线
0
东方之美：71岁傅莹身着旗袍，展现独特魅力，堪称“最美外交官”
傅莹，这位被誉为“最美外交官”的杰出女性，凭借其卓越的外交才华和专业能力在国际舞台上熠熠生辉。她的自信与从容不仅体现在专业领域内的出色表现，更在言谈举止间自然流露，令人由衷敬佩。如今71岁的她，依旧保持着...
全栈架构社区
0
从0开始学RAG之RAG-Fusion
作者：lucas大叔原文地址：https://zhuanlan.zhihu.com/p/684994205类型: 技术分享本文为 @lucas大叔 投稿原创转载！如有侵权，麻烦告知删除！ 基本原理RAG-Fusion可以认为是MultiQueryRetriever的进化版，如下...
DayNightStudy
0
点赞
评论
收藏
分享

手机扫一扫分享

举报