开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构与算法】————二叉树全面总结 -> 正文阅读

[数据结构与算法]【数据结构与算法】————二叉树全面总结

😎二叉树

🍉 二叉树定义

n（n ≥ 0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成

二叉树有什么特点？

每个结点最多有两棵子树
二叉树是有序的，其次序不能任意颠倒，即子树有左右之分，顺序不能颠倒

🍑 二叉树的基本术语

左斜树： 所有结点都只有左子树的二叉树

右斜树： 所有结点都只有右子树的二叉树

斜树： 左斜树和右斜树的统称

斜树有什么特点呢？

每一层只有一个结点
结点个数与其深度相同

斜树是树结构的特例，是从树结构退化成了线性结构

🍑 满二叉树

所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上的二叉树

满二叉树有什么特点呢？

叶子只能出现在最下一层
只有度为 0 和度为 2 的结点
在同样深度的二叉树中结点个数最多
在同样深度的二叉树中叶子结点个数最多

满二叉树是树结构的特例，是最丰满的二叉树

🍑 完全二叉树

在满二叉树中，从最后一个结点开始，连续去掉任意个结点得到的二叉树

完全二叉树有什么特点呢？

叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面
完全二叉树中如果有度为 1 的结点，只可能有一个，且该结点只有左孩子
深度为 k 的完全二叉树在 k-1 层上一定是满二叉树
在同样结点个数的二叉树中，完全二叉树的深度最小

在这里插入图片描述

🍉 二叉树的基本性质

性质 1： 在一棵二叉树中，如果叶子结点数为 $n_{0}$ ，度为 2 的结点数为 $n_{2}$ ，则有: $n_{0}$ ＝ $n_{2}$ ＋1

证明：

设 n 为二叉树的结点总数， $n_{1}$ 为二叉树中度为 1 的结点数，则有：n＝ $n_{0}$ ＋ $n_{1}$ ＋ $n_{2}$ ①

在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，一个度为 1 的结点射出一个分枝，一个度为 2 的结点射出两个分枝，所以有：n＝ $n_{1}$ ＋2 $n_{2}$ ＋1 ②

联立①②可得 $n_{0}$ ＝ $n_{2}$ ＋1

性质 2： 二叉树的第 i 层上最多有 $2^{i-1}$ 个结点（i ≥ 1）

证明：

采用归纳法证明。
当 i = 1时，只有一个根结点，而 $2^{i-1}$ = $2^{0}$ =1，结论成立

假设i = k 时结论成立，即第 k 层上最多有 $2^{k-1}$ 个结点。

考虑 i = k+1 时的情形。由于第 k+1 层上的结点是第 k 层上结点的孩子，而二叉树中每个结点最多有两个孩子，故在第 k+1 层上的最多大结点个数有2× $2^{k-1}$ ＝ $2^{k}$ 个结点，则在 i = k+1时结论也成立。

由此，结论成立。

性质 3： 一棵深度为 k 的二叉树中，最多有 $2^{k}-1$ 个结点

证明：

根据性质2可知，第 i 层上最多有 $2^{i-1}$ 个结点，由此可以算出每一层最多有多少个结点，那么深度为k的二叉树，最多有 $2^{i-1}$ 的前k项和个结点，如下

$=\sum_{i=1}^{k}(第i层上结点的最大个数)=\sum_{i=1}^{k}2^{i-1}$

$2^{i-1}$ 是等比数列，因此可以通过等比数列的前n项和公式 $\frac{a_{1}(1-q^{n})}{1-q}$ 来求级数 $\sum_{i=1}^{k}2^{i-1}=2^{k}-1$

显然，具有 $2^{k}-1$ 个结点的二叉树是满二叉树，且满二叉树的深度k= l $og_{2}(n+1)$ ,推导过程如下

$2^{k}=n+1\rightarrow 移位$ $k=log_{2}(n+1)\rightarrow取对数$

性质 4： 具有 n 个结点的完全二叉树的深度为 $\left \lfloor log_{2}n \right \rfloor$ +1

证明：设具有 n 个结点的完全二叉树的深度为 k，则根据性质2可知，最少有 $2^{k-1}$ 结点。根据性质3可知，最多有 $2^{k}-1$ 个结点，为了方便取对数，假设最多的结点不会超过 $2^{k}$ ，如下

$2^{k-1}\leq _{}n< _{}2^{k}$ $k-1\leq _{}log_{2}n< _{}k\rightarrow取对数$ $log_{2}n< _{}k\leq _{}log_{2}n+1\rightarrow移项$ $由于 k 是整数，则必有$ $k=\left \lfloor log_{2}n \right \rfloor+1\rightarrow\left \lfloor log_{2}n \right \rfloor是向下取整，即取不超过log_{2}n的最大整数$

性质 5： 对一棵具有 n 个结点的完全二叉树中从 1 开始按层序编号，对于任意的序号为 i（1 ≤ i ≤ n）的结点（简称结点 i），有：

① 如果i > 1，则结点i的双亲的编号为 $\left \lfloor \frac{i}{2} \right \rfloor$ ,否则结点 i 是根结点，无双亲。

② 如果2i $\leq$ n，则结点i的左孩子的编号为2i，否则结点 i 无左孩子

③ 如果2i+1 $\leq$ n，则该结点i的右孩子的编号为2i+1，否则结点 i 无右孩子

证明:

在证明过程中，可以从② 和③推出① ，所以先证明② 和③，采用归纳法证明

先讨论具体的情形

当 i = 1时，结点 i 就是根结点，因此无双亲。由完全二叉树的定义，其左孩子是结点2，若2>n，即不存在结点2，此时，结点 i 无左孩子，满足②。结点 i 的右孩子是结点3，若结点3不存在，即3>n，此时结点 i 无右孩子，满足③

假设i=k时结论依然成立，下面讨论i=k+1的情形

设第 j ( $1\leq j<\left \lfloor log_{2}n \right \rfloor+1$ ）层上某个结点编号为 i ( $2^{i-1}\leq i< 2^{i}$ ），其左孩子为2i，右孩子为2i+1,如果结点 i 不是第 j 层最后一个结点，则结点i+1是结点 i 的右兄弟或堂兄弟。如果结点 i 是第 j 层最后一个结点，则结点i+1是第j+1层的第一个结点。若结点i+1有左孩子，则左孩子的编号必定为2i+2=2 $\times(i+1)$ ，若结点i+1有右孩子，则右孩子的编号必定为2i+3=2 $\times(i+1)+1$ ,如下图所示，因此②③成立

在这里插入图片描述
当 i > 1时，如果 i 为左孩子，即2 $\times(\frac{i}{2})=i$ ,则 $\frac{i}{2}$ 是 i 的的双亲。如果 i 为右孩子，则 i = 2j+1，即结点i的双亲应为 j ，而 j = ( i - 1 ) / 2= $\left \lfloor \frac{i}{2} \right \rfloor$ ，因此①成立

🍉 二叉树遍历

二叉树的遍历：从根结点出发，按照某种次序访问树中所有结点，并且每个结点仅被访问一次

按照什么次序对二叉树进行遍历呢？

二叉树由根结点(D)，根结点的左子树(L)和根结点的右子树（R)三部分组成，只要依次遍历这三部分，就可以遍历整个二叉树，这三部分共有六种全排列，即第1个位置有3种可能，第2个位置有3-1=2种可能，第3个位置有3-2=1种可能，共有3 x 2 x 1 = 6种可能，如下 $D L R 、 L D R 、 L R D 、 D R L 、 R D L 、 R L D$

不失一般性，约定先左子树后右子树，则有前序(根)遍历，中序(根)遍历和后序(根)遍历。如果按二叉树的层序依次访问各结点，可得到另一种遍历次序，层序遍历

前序遍历

若二叉树为空，则空操作返回；否则：

访问根结点
前序遍历根结点的左子树
前序遍历根结点的右子树

在这里插入图片描述 中序遍历

若二叉树为空，则空操作返回；否则：

中序遍历根结点的左子树
访问根结点
中序遍历根结点的右子树

在这里插入图片描述

后序遍历

若二叉树为空，则空操作返回；否则：

后序遍历根结点的左子树
后序遍历根结点的右子树
访问根结点

在这里插入图片描述

层序遍历

从二叉树的根结点开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问

在这里插入图片描述

🍉 二叉树的存储结构

🍑 顺序存储结构

二叉树的顺序存储结构是用一维数组存储二叉树的结点，结点的存储位置（下标）应能体现结点之间的逻辑关系——父子关系

对于普通的二叉树，如何顺序存储呢？

由二叉树的性质5可知,完全二叉树中结点的层序编号可以唯一地反映结点之间的逻辑关系,对于一般的二叉树,可以按照完全二叉树进行层序编号,然后再用一维数组顺序存储。具体步骤如下:

将二叉树按完全二叉树编号：

根结点的编号为 1
若某结点 i 有左孩子，则其左孩子的编号为 2i
若某结点 i 有右孩子，则其右孩子的编号为 2i+1

在这里插入图片描述
缺点

显然,这种存储方法的缺点是浪费存储空间,最坏情况是右斜树，一棵深度为k的右斜树只有k个结点,由二叉树的性质3可知，需要分配 $2^{k}-1$ 个存储单元。事实上,二叉树的顺序存储结构一般仅适合于存储完全二叉树。

在这里插入图片描述

🌈 代码实现

不同的二叉树的存储结构具有相同的操作，如遍历，建立树等，因此可以建立一种规范接口。如下

public interface  BinaryTreeInterface<T> {

    // 前序遍历二叉树
    void preOrder();

    // 中序遍历二叉树
    void inOrder();

    // 后序遍历二叉树
    void postOrder();

    // 层序遍历二叉树
    void levelOrder();

    // 构建二叉树
    void createBiTree(SequentialList<T> treeElements);
}

🌟 顺序存储结构实现

可在SequentialTree类中,通过定义泛型数组 seqTree(存储数据元素)、整型常量TREE_MAX_SIZE(定义数组容量)，整形变量len(存储数据元素个数),SequentialTree类实现 BinaryTreeInterface接口定义的方法实现二叉树顺序存储。

public class SequentialTree<T> implements BinaryTreeInterface {

    // 二叉树顺序存储数组
    protected T[] seqTree;
    // 结点数量
    private int len;
    // 存储容量
    private final static int TREE_MAX_SIZE = 100;
    
    // 成员函数实现二叉树接口方法算法
}

算法实现如下:

二叉树的初始化

通过二叉树类(SequentialTree)的构造函数实现空二叉树初始化。

public SequentialTree() {
    // 创建一个指定容量的数组
    seqTree = (T[]) new Object[TREE_MAX_SIZE];
}

建立二叉树

函数 creatBiTree的参数为某种遍历序列的顺序表(可为任意数据类型)。依据遍历序列实现二叉树建立，当前仅针对完全二叉树的层序编号序列实现，如下

@Override
public void createBiTree(SequentialList treeElements) {
    for (int i = 0; i < treeElements.getLen(); i++) {
        seqTree[i] = (T) treeElements.getElementsData(i + 1);
        len++;
    }
}

SequentialList.java

public class SequentialList<T> {

    private T[] elementsData;

    public SequentialList(T[] elementsData) {
        this.elementsData = elementsData;
    }

    public T getElementsData(int i) {
        return elementsData[i - 1];
    }

    public int getLen() {
        return elementsData.length;
    }
}

🌟 递归算法实现前序，中序，后序遍历

前序遍历

二叉树对象对其自身的遍历应是无参数的(仅针对自身遍历,不允许通过外部调用遍历其他二叉树),但递归调用过程需要逐级遍历当前结点子树,以参数形式传入当前根结点引用,为此设置preOrder重载私有有参函数。

根据二叉树前序遍历的操作定义,容易写出前序遍历的递归算法,成员函数定义如下。

// 前序遍历入口
@Override
public void preOrder() {
    // 当前二叉树为空，算法结束
    if (seqTree == null || len == 0) {
        return;
    }
    preOrder(0);
}

// 前序遍历递归实现
private void preOrder(int i) {
    if (!seqTree[i].equals("^")) {
        // 访问当前结点的数据
        System.out.print(seqTree[i] + " ");
    }
    // 前序递归遍历左子树
    if (2 * i  + 1 < len) {
        preOrder(2 * i  + 1);
    }
    // 前序递归遍历右子树
    if (2 * i + 2 < len) {
        preOrder(2 * i + 2);
    }
}

中序遍历

根据二叉树中序遍历的操作定义,访问结点的操作发生在该结点的左子树遍历完毕且尚未遍历右子树时,所以中序遍历的递归实现只需要将输出操作System. out. print( seqTree[i] + " ")放到递归遍历左子树之后即可。

// 中序遍历入口
@Override
public void inOrder() {
    // 当前二叉树为空，算法结束
    if (seqTree == null || len == 0) {
        return;
    }
    inOrder(0);
}

// 中序遍历递归实现
private void inOrder(int i) {
    // 中序递归遍历左子树
    if (2 * i  + 1 < len) {
        inOrder(2 * i  + 1);
    }
    if (!seqTree[i].equals("^")) {
        // 访问当前结点的数据
        System.out.print(seqTree[i] + " ");
    }
    // 中序递归遍历右子树
    if (2 * i + 2 < len) {
        inOrder(2 * i + 2);
    }
}

后序遍历

根据二叉树后序遍历的操作定义,访问结点的操作发生在该结点的左子树和右子树均遍历完毕后,所以后序遍历的递归实现只需要将输出操作System. out. print( seqTree[i] + " ")放到递归遍历右子树之后即可。

// 后序遍历入口
@Override
public void postOrder() {
    // 当前二叉树为空，算法结束
    if (seqTree == null || len == 0) {
        return;
    }
    postOrder(0);
}

private void postOrder(int i) {
    // 后序递归遍历左子树
    if (2 * i  + 1 < len) {
        postOrder(2 * i  + 1);
    }
    // 后序递归遍历右子树
    if (2 * i + 2 < len) {
        postOrder(2 * i + 2);
    }
    if (!seqTree[i].equals("^")) {
        // 访问当前根结点的数据
        System.out.print(seqTree[i] + " ");
    }
}

🌟 非递归算法实现前序，中序，后序遍历

递归算法虽然简洁,但一般而言,其执行效率不高。因此,有时需要把递归算法转换为非递归算法。对于二叉树的遍历算法,可以仿照递归执行过程中工作栈的状态变化得到非递归算法。

前序遍历非递归算法

二叉树前序遍历非递归算法(iteratorPreOrder)的关键是:在前序遍历过某结点整个左子树后,如何找到该结点右子树的根引用

可以在访问某结点时，将该结点放进容器中，当访问某结点的左子树时，如果左子树为空时，此时应该访问当前结点的右子树。右子树可以通过当前结点间接访问到(2 * i + 2),因此需要取出容器最后进的结点，即为当前结点，综上此容器满足先进后出规律，可以使用栈作为容器

@Override
public void preOrder() {
    // 当前二叉树为空，算法结束
    if (seqTree == null || len == 0) {
        return;
    }
    // 队列初始化
    Stack<Integer> stack = new Stack<>();
    // 工作结点初始化
    Integer index = 0;
    while ((index < len && !seqTree[index].equals("^")) || !stack.isEmpty()) {
        while (index < len && !"^".equals(seqTree[index])) {
            System.out.print(seqTree[index] + " ");
            stack.push(index); // 结点入栈
            index = index * 2 + 1; // 准备遍历结点的左孩子
        }
        if (!stack.isEmpty()) { // 结点为空，栈非空
            Integer poll = stack.pop(); // 栈顶元素出栈
            index = poll * 2 + 2; // 准备遍历栈顶元素的右孩子
        }
    }
}

中序遍历非递归算法

在二叉树的中序遍历中,访问结点的操作发生在该结点的左子树遍历完毕并准备遍历右子树时,所以在遍历过程中遇到某结点时并不能立即访问它,而是将它入栈,待其左子树遍历完毕,再出栈并访问。中序遍历非递归算法只需要将前序遍历非递归算法中的输出语句System.out.print(seqTree[index] + " ");移到出栈操作之后

// 中序遍历入口
@Override
public void inOrder() {
    // 当前二叉树为空，算法结束
    if (seqTree == null || len == 0) {
        return;
    }
    // 队列初始化
    Stack<Integer> stack = new Stack<>();
    // 工作结点初始化
    Integer index = 0;
    while ((index < len && !seqTree[index].equals("^")) || !stack.isEmpty()) {
        while (index < len && !"^".equals(seqTree[index])) {
            stack.push(index); // 结点入栈
            index = index * 2 + 1; // 准备遍历结点的左孩子
        }
        if (!stack.isEmpty()) { // 结点为空，栈非空
            Integer poll = stack.pop(); // 栈顶元素出栈
            System.out.print(seqTree[poll] + " ");
            index = poll * 2 + 2; // 准备遍历栈顶元素的右孩子
        }
    }
}

后序遍历非递归算法

后序遍历(iteratorPostOrder)与前序遍历和中序遍历不同。在后序遍历过程中,当遍历完左子树时,由于右子树尚未遍历,因此栈顶结点不能出栈,通过栈顶结点找到它的右子树,准备遍历它的右子树;当遍历完右子树时,将栈顶结点出栈,并访问它。

为了区别对栈顶结点的不同处理,可设置标志变量flag: flag=1表示遍历完左子树,栈顶结点不能出栈;flag=2表示遍历完右子树,栈顶结点可以出栈并访问。定义相应结点类。

FlagBiNode.java

public class FlagBiNode {

    private Integer index;
    private Integer flag;

    public FlagBiNode(Integer index, Integer flag) {
        this.index = index;
        this.flag = flag;
    }

    public Integer getIndex() {
        return index;
    }

    public void setIndex(Integer index) {
        this.index = index;
    }

    public Integer getFlag() {
        return flag;
    }

    public void setFlag(Integer flag) {
        this.flag = flag;
    }
}

算法实现

@Override
public void postOrder() {
    // 当前二叉树为空，算法结束
    if (seqTree == null || len == 0) {
        return;
    }
    // 队列初始化
    Stack<FlagBiNode> stack = new Stack<>();
    // 工作结点初始化
    Integer index = 0;
    FlagBiNode flagBiNode;
    while ((index < len && !seqTree[index].equals("^")) || !stack.isEmpty()) {
        while (index < len && !"^".equals(seqTree[index])) { // 当前结点非空
            flagBiNode = new FlagBiNode(index, 1); // 生成新结点，flag赋值为1
            stack.push(flagBiNode); // 新结点入栈
            index = index * 2 + 1; // 准备遍历结点的左孩子
        }
        while (!stack.isEmpty() && (stack.peek().getFlag() == 2)) {
            index = stack.pop().getIndex(); // flag为2，出栈
            System.out.print(seqTree[index] + " ");
            index = len;
        }
        if (!stack.isEmpty()) { // 栈不为空且flag值为1
            flagBiNode = stack.pop(); // 栈顶元素出栈
            flagBiNode.setFlag(2); // 出栈结点flag赋值为2
            stack.push(flagBiNode); // flag赋值后结点入栈
            index = flagBiNode.getIndex() * 2 + 2; // 准备遍历栈顶元素的右孩子
        }
    }
}

🌟 队列实现层序遍历

在进行层序遍历时,结点访问应遵循“从上至下、从左至右”逐层访问的原则,使得先被访问结点的左,右孩子先于后被访问结点的左、右孩子被访问。为保证这种“先先”的特性,可应用队列作为辅助结构。首先根结点入队,队头出队,输出出队结点,出队结点的左、右孩子分别入队,以此类推,直至队列为空。

// 层序遍历
@Override
public void levelOrder() {
    // 当前二叉树为空，算法结束
    if (seqTree == null || len == 0) {
        return;
    }
    Queue<Integer> queue = new LinkedList<>();
    // 根引用入队
    queue.offer(0);
    // 队列非空执行循环
    while (!queue.isEmpty()) {
        // 出队
        Integer index = queue.poll();
        // 输出结点数据域
        if (!seqTree[index].equals("^")) {
            System.out.print(seqTree[index] + " ");
        }
        // 结点左孩子入队
        if (index * 2  + 1 < len) {
            queue.offer(index * 2 + 1);
        }
        // 结点右孩子入队
        if (index * 2 + 2 < len) {
            queue.offer(index * 2  + 2);
        }
    }
}

🌟 测试

public class TestBiTree {

    public static void main(String[] args) {
        SequentialTree<String> biTree = new SequentialTree<>();
        // 据完全二叉树编号构建二叉树
        String initialList[] = {"A", "B", "C", "^", "D", "F", "^", "^", "^", "E", "^", "^", "G"};
        SequentialList<String> treeElements = new SequentialList<>(initialList);
        biTree.createBiTree(treeElements);
        System.out.print("二叉树前序遍历：");
        biTree.preOrder();
        System.out.print("\n二叉树中序遍历：");
        biTree.inOrder();
        System.out.print("\n二叉树后序遍历：");
        biTree.postOrder();
        System.out.print("\n二叉树层序遍历：");
        biTree.levelOrder();
    }
}

在这里插入图片描述

🍑 二叉链表存储结构

如何用链接存储方式存储二叉树呢？

在这里插入图片描述

二叉链表： 二叉树的每个结点对应一个链表结点，链表结点存放结点的数据信息和指示左右孩子的指针

在这里插入图片描述

🌈 代码实现

🌟 二叉链表的实现

在BinaryTree类中,通过定义BiNode类型根结点变量root实现二叉链表存储结构。BinaryTree类实现 BinaryTreeInterface接口定义的方法。

public class BinaryTree<T> implements BinaryTreeInterface {

    protected BiNode<T> root;

    // 成员函数实现二叉树接口算法
}

结点数据结构

public class BiNode<T> {

    private T data; // 定义结点泛型数据域
    // 定义结点左右孩子引用域
    private BiNode leftChild;
    private BiNode rightChild;

    // 构造数据域为data值的结点
    public BiNode(T data) {
        this.data = data;
    }

    public T getData() { // 读取数据域
        return data;
    }

    public void setData(T data) { // 设置数据域
        this.data = data;
    }

    public BiNode getLeftChild() { // 读取左孩子
        return leftChild;
    }

    public void setLeftChild(BiNode leftChild) { // 设置左孩子
        this.leftChild = leftChild;
    }

    public BiNode getRightChild() { // 读取右孩子
        return rightChild;
    }

    public void setRightChild(BiNode rightChild) { // 设置右孩子
        this.rightChild = rightChild;
    }
}

二叉树的初始化

通过二叉树类(BinaryTree)的构造函数实现空二叉树初始化。

public BinaryTree() {
    this.root = null; // 根引用赋值为空
}

二叉树的建立

在内存中建立一棵二叉链表，如何输入二叉树的信息？

遍历将二叉树审视一遍，将非线性结构转换为线性结构。遍历是二叉树各种操作的基础，可以在遍历的过程中建立一棵二叉树

如何由一种遍历序列生成该二叉树？

由于前序、中序和后序序列中的任何一个都不能唯一确定一棵二叉树,因此不能直接使用。可以对二叉树作如下处理:

扩展二叉树： 将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如 ‘#’

在这里插入图片描述

算法实现

函数 creatBiTree的参数为某种遍历序列的顺序表(可为任意数据类型)。依据遍历序列实现二叉树建立，当前仅针对前序遍历序列实现，调用creatByPreOrder 递归函数实现算法。creatBiTree,creatByPreOrder算法实现如下:

@Override
public void createBiTree(SequentialList treeElements) {
    root = createByPreOrder(treeElements); // 据前序遍历序列构建

}

private int elementCount = 0; // 全局变量记录元素个数

private BiNode<T> createByPreOrder(SequentialList<T> treeElements) {
    BiNode node; // 定义根结点
    elementCount++; // 结点个数加一
    if (elementCount > treeElements.getLen() ||
            treeElements.getElementsData(elementCount).equals("#")) {
        // 递归结束
        node = null;
    } else {
        // 新结点
        node = new BiNode<>(treeElements.getElementsData(elementCount));
        node.setLeftChild(createByPreOrder(treeElements)); // 递归遍历左子树
        node.setRightChild(createByPreOrder(treeElements)); // 递归遍历右子树
    }
    return node;
}

🌟 递归算法实现前序，中序，后序遍历

递归算法实现和前面的顺序存储结构是类似的，这里不再重复阐述

前序遍历

@Override
public void preOrder() { // 前序遍历入口
    preOrder(root);
}

private void preOrder(BiNode node) { // 前序遍历递归实现
    if (node == null) { // 递归调用的结束条件
        return;
    } else {
        System.out.print(node.getData() + " "); // 访问当前根结点的数据域
        preOrder(node.getLeftChild()); // 前序递归遍历node的左子树
        preOrder(node.getRightChild()); // 前序递归遍历node的右子树
    }
}

中序遍历

@Override
public void inOrder() { // 中序遍历入口
    inOrder(root);
}

private void inOrder(BiNode node) {
    if (node == null) { // 递归调用的结束条件
        return;
    } else {
        inOrder(node.getLeftChild()); // 中序递归遍历node的左子树
        System.out.print(node.getData() + " "); // 访问当前根结点的数据域
        inOrder(node.getRightChild()); // 中序递归遍历node的右子树
    }
}

后序遍历

@Override
public void postOrder() { // 后序遍历入口
    postOrder(root);
}

private void postOrder(BiNode node) {
    if (node == null) { // 递归调用的结束条件
        return;
    } else {
        postOrder(node.getLeftChild()); // 后序递归遍历node的左子树
        postOrder(node.getRightChild()); // 后序递归遍历node的右子树
        System.out.print(node.getData() + " "); // 访问当前根结点的数据域
    }
}

🌟 非递归算法实现前序，中序，后序遍历

前序遍历非递归算法

@Override
public void preOrder() { 
    Stack<BiNode> stack = new Stack<>(); 
    BiNode node = root; // 工作结点初始化
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            System.out.print(node.getData() + " ");
            stack.push(node); // node入栈
            node = node.getLeftChild(); // 准备遍历node左孩子
        }
        if (!stack.isEmpty()) { // node为空，栈非空
            node = stack.pop(); // 栈顶元素出栈，赋予node
            node = node.getRightChild(); // 准备遍历node右孩子
        }
    }
}

中序遍历非递归算法

@Override
public void inOrder() {
    Stack<BiNode> stack = new Stack<>();
    BiNode node = root; // 工作结点初始化
    while (node != null || !stack.isEmpty()) {
        while (node != null) {
            stack.push(node); // node入栈
            node = node.getLeftChild(); // 准备遍历node左孩子
        }
        if (!stack.isEmpty()) { // node为空，栈非空
            node = stack.pop(); // 栈顶元素出栈，赋予node
            System.out.print(node.getData() + " ");
            node = node.getRightChild(); // 准备遍历node右孩子
        }
    }
}

后序遍历非递归算法

同样地，后序遍历与前序遍历和中序遍历不同。在后序遍历过程中,当遍历完左子树时,由于右子树尚未遍历,因此栈顶结点不能出栈,通过栈顶结点找到它的右子树,准备遍历它的右子树;当遍历完右子树时,将栈顶结点出栈,并访问它。

FlagBiNode.java

public class FlagBiNode {

    private BiNode node; // 定义BiNode类型结点
    private Integer flag; // 定义flag标识符

    public FlagBiNode(BiNode node, Integer flag) { // 构造函数初始化结点
        this.node = node;
        this.flag = flag;
    }

    public BiNode getNode() {
        return node;
    }

    public void setNode(BiNode node) {
        this.node = node;
    }

    public Integer getFlag() {
        return flag;
    }

    public void setFlag(Integer flag) {
        this.flag = flag;
    }
}

算法实现

@Override
public void postOrder() {
    Stack<FlagBiNode> stack = new Stack<>(); // 栈初始化
    BiNode node = root; // 工作结点初始化
    FlagBiNode flagNode;
    while (node != null || !stack.isEmpty()) {
        while (node != null) { // 当前结点非空
            flagNode = new FlagBiNode(node, 1); // 生成新结点，flag赋值为1
            stack.push(flagNode); // 新node入栈
            node = node.getLeftChild(); // 准备遍历结点左孩子
        }
        while (!stack.isEmpty() && stack.peek().getFlag() == 2) {
            node = stack.pop().getNode();
            System.out.print(node.getData() + " ");
            node = null;
        }
        if (!stack.isEmpty()) { // 栈非空且flag值为1
            flagNode = stack.pop(); // 栈顶元素出栈
            flagNode.setFlag(2); // 出栈结点flag赋值为2
            stack.push(flagNode); // flag赋值后结点入栈
            node = flagNode.getNode().getRightChild(); // 准备遍历结点右孩子
        }
    }
}

🌟 队列实现层序遍历

@Override
public void levelOrder() {
    Queue<BiNode> queue = new LinkedList<>();
    if (root == null) { // 当前二叉树为空，算法结束
        return;
    } else {
        queue.offer(root); // 根引用入队
        while (!queue.isEmpty()) { // 队列非空执行循环
            BiNode tempNode = queue.poll(); // 出队
            System.out.print(tempNode.getData() + " "); // 输出结点数据域
            if (tempNode.getLeftChild() != null) { // 结点非空左孩子入队
                queue.offer(tempNode.getLeftChild());
            }
            if (tempNode.getRightChild() != null) { // 结点非空右孩子入队
                queue.offer(tempNode.getRightChild());
            }
        }
    }
}

🌟 测试

public class BiTreeTest {
    public static void main(String[] args) {
        BinaryTree biTree = new BinaryTree();
        // 据前序遍历序列AB#D##C##构建二叉树
        String initialList[] = {"A", "B", "#", "D", "#", "#", "C", "#", "#"};
        SequentialList<String> treeElements = new SequentialList<>(initialList);
        biTree.createBiTree(treeElements);
        System.out.print("二叉树前序遍历：");
        biTree.preOrder();
        System.out.print("\n二叉树中序遍历：");
        biTree.inOrder();
        System.out.print("\n二叉树后序遍历：");
        biTree.postOrder();
        System.out.print("\n二叉树层序遍历：");
        biTree.levelOrder();
    }
}

在这里插入图片描述

🍑 三叉链表存储结构

在二叉链表存储方式下,从某结点出发可以直接访问到它的孩子结点,但要找到它的双亲结点,则需要从根结点开始搜索,最坏情况需要遍历整个二叉链表。此时,应该采用三叉链表(trident linked list)存储二叉树。

在三叉链表中,每个结点由四个域组成,其中,data 、lchild和 rchild三个域的含义与二叉链表的结点结构相同;parent域为该结点的双亲结点的引用。

在这里插入图片描述

缺点: 相对于二叉链表而言,它增加了空间开销

🌈 代码实现

🌟 三叉链表实现

二叉树的三叉链表存储结构比二叉链表多一个指向双亲结点的指针，因此，求双亲和左右兄弟都很容易。但在构造二叉树时要另给双亲指针赋值，从而增加了复杂度。

在BinaryTree类中,通过定义TriNode类型根结点变量root实现三叉链表存储结构。BinaryTree类实现 BinaryTreeInterface接口定义的方法。

public class BinaryTree<T> implements BinaryTreeInterface {

    protected TriNode<T> root;

    // 成员函数实现三叉树接口算法
}

结点数据结构

public class TriNode<T> {

    private T data; // 定义结点泛型数据域
    // 定义结点左，右孩子，双亲引用域
    private TriNode<T> leftChild;
    private TriNode<T> rightChild;
    private TriNode<T> parent;

    public TriNode(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public TriNode<T> getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(TriNode<T> leftChild) {
        this.leftChild = leftChild;
    }

    public TriNode<T> getRightChild() {
        return rightChild;
    }

    public void setRightChild(TriNode<T> rightChild) {
        this.rightChild = rightChild;
    }

    public TriNode<T> getParent() {
        return parent;
    }

    public void setParent(TriNode<T> parent) {
        this.parent = parent;
    }
}

二叉树的初始化

通过二叉树类(BinaryTree)的构造函数实现空二叉树初始化。

public BinaryTree() {
    this.root = null; // 根引用赋值为空
}

二叉树的建立

@Override
public void createBiTree(SequentialList treeElements) {
    root = createByPreOrder(treeElements); // 据前序遍历序列构建
}

private int elementCount = 0; // 全局变量记录元素个数

private TriNode<T> createByPreOrder(SequentialList<T> treeElements) {
    TriNode node; // 定义根结点
    elementCount++; // 结点个数加一
    if (elementCount > treeElements.getLen() ||
            treeElements.getElementsData(elementCount).equals("#")) {
        // 递归结束
        node = null;
    } else {
        // 新结点
        node = new TriNode<T>(treeElements.getElementsData(elementCount));
        node.setLeftChild(createByPreOrder(treeElements)); // 递归遍历左子树
        if (node.getLeftChild() != null) { // 有左孩子
            node.getLeftChild().setParent(node); // 给左孩子的双亲域赋值
        }
        if (node.getRightChild() != null) { // 有右孩子
            node.getRightChild().setParent(node); // 给右孩子的双亲域赋值
        }
        node.setRightChild(createByPreOrder(treeElements)); // 递归遍历右子树
    }
    return node;
}