当前位置：网站首页 > 程序开发学习 > 正文

[数据结构]树与二叉树知识点总结

作者：小教学发布时间：2023-09-20分类：程序开发学习浏览：74

导读：欢~迎~光~临~^_^目录1个、树1.1基本概念及基本术语1.2常考性质2个、二叉树2.1基本概念2.2满二叉树2.3完全二叉树2.4%二叉排序树2.5平衡二叉树2.6%二叉树的性...

欢~迎~光~临~^_^

1个、树

1.1基本概念及基本术语

1.2常考性质

2个、二叉树

2.1基本概念

2.2满二叉树

2.3完全二叉树

2.4%二叉排序树

2.5平衡二叉树

2.6%二叉树的性质

2.7%二叉树的存储结构

2.7.1顺序存储结构

2.7.2链式存储结构

3个、二叉树的遍历

3.1先序遍历

3.2中序遍历

3.3%后序遍历

3.4%层次遍历

3.5%由二叉树的遍历序列构造二叉树

3.5.1前序+中序

3.5.2后序+中序

3.5.3层次+中序

4个、线索二叉树

4.1概念及作用

4.2二叉树线索化

4.2.1中序线索化

4.2.2先序线索化

4.2.3后序线索化

4.3%存储结构

4.4%三种线索二叉树

4.4.1中序线索二叉树

4.4.2先序线索二叉树

4.4.3后序线索二叉树

4.5%手算画出线索二叉树

1个、树

1.1基本概念及基本术语

树的定义:树是n个结点的有限集.N个结点的树有n-1条边.他说：

树是一种非线性的数据结构，它由一系列节点(节点可以是任意类型的数据)以及它们之间的连接构成.树的基本概念如下：

1.根节点:树的顶端节点，没有父节点.

2.父节点:有子节点的节点被称为父节点.

3.子节点:树中直接连接在一个父节点下面的节点.

4.叶节点/终端节点:没有子节点的节点.

5.兄弟节点:拥有同一个父节点的节点被称为兄弟节点.

6.子树:一个节点及其子孙节点组成的子树称为该节点的子树.

7.祖先节点:从根节点到某个节点的所有节点构成该节点的祖先节点.

8.后代节点:从某个节点到其所有子节点的节点构成该节点的后代节点.

9.深度:根节点的深度为0，其他节点的深度为其父节点的深度加一。

10.高度:节点的高度等于其子树的最大深度加一.

11.路径长度:路径上经过多少条边.

12.结点之间的路径:只能从上往下.

树的常见应用场景包括文件系统、组织结构、编译器抽象语法树等.

1.2常考性质

具有以下的性质：

1.一个树是一个连通且无环的无向图.

2.一个树有n个节点，则它有n-1条边.

3.在一个树中，任意两个节点之间有且仅有一条简单路径.

4.树的最长路径必然是直径，且直径的长度等于树的最长距离；最长距离定义为从树中任意一个节点出发，到达树中任意一个节点所经过的边数的最大值.

5.在一个有根树中，每个非根节点都有唯一的父节点，而根节点没有父节点.

6.在一个二叉树中，如果按照从上到下、从左到右的顺序对每个节点进行编号，则对于任意一个节点I、它的左子节点编号为2i、右子节点编号为2i+1。

7.一棵树中，如果所有节点的度数都不超过2，则该树是一棵二叉树.若所有非叶节点的度数恰好为2，则该树是一棵满二叉树.

8.在一棵二叉树中，如果节点A到节点B的路径上没有其他节点，那么节点A就是节点B的祖先，节点B是节点A的后代.

下图中是更加重要的性质：是的

2个、二叉树

2.1基本概念

二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点.通常用以下术语来描述一个二叉树：

1.根节点:二叉树的顶部节点，没有父节点；

2.叶节点:没有子节点的节点，也称为“终端节点”或“叶子节点”；

3.父节点:一个节点的子节点的表示它的父节点；

4.子节点:一个节点的子树中的节点称为它的子节点；

5.深度:根节点的深度为0，每往下一层，深度加1；

6.高度:一个节点的高度指从该节点到它的最深子孙节点的层数；

7.左节点和右节点:每个节点最多有两个子节点，分别称为左节点和右节点；

2.2满二叉树

满二叉树是一种特殊的二叉树，它满足以下条件：

1.所有的非叶子节点都有两个子节点；
2.所有叶子节点都在同一层.

满二叉树的特点是节点数目非常明确，如果树的深度为h，则树中节点总数为2^h-1。同时，满二叉树是一种完美二叉树，也就是说，所有的叶子节点都在同一层，并且每个非叶子节点都有两个子节点.由于这种特殊的结构，满二叉树很容易被理解和处理，因此在计算机科学中得到广泛的应用，例如堆排序、哈夫曼编码等.

2.3完全二叉树

完全二叉树是指除了最后一层节点不满外，其他层节点都必须达到最大数量的二叉树，且最后一层节点都靠左排列.具体来说，如果一棵深度为d(d>；1)的二叉树，除了第d层之外，其他各层的节点数都达到了最大值，且第d层所有的节点都从左向右紧密排列，那么这棵二叉树就是完全二叉树.

2.4%二叉排序树

二叉排序树(二叉搜索树)也叫二叉查找树，它是一种特殊的二叉树。在二叉排序树中，任何一个节点的左子树中的每个元素值都小于这个节点的元素值，右子树的每个节点的值都大于这个节点的元素值.

二叉排序树的节点结构通常包含三个元素:节点值、左子树指针和右子树指针.通过比较节点值和目标值的大小关系，就可以在二叉排序树中进行查找、插入和删除等操作.二叉排序树的插入、删除和查找时间复杂度都为O(Logn)，是一种高效的数据结构.

举个例子，若有一组数列{10，5，14，3，8，12，16}，可以构建一个二叉排序树如下：

在这个树中，10是根节点，5和14是它的左右子节点，3、8是5的左右子节点，12、16是14的左右子节点。根据二叉排序树的性质，在这个树中查找元素时，可以通过比较目标值和节点值的大小关系逐层向下搜索，直到找到目标值为止.

2.5平衡二叉树

平衡二叉树(AVL树)是一种自平衡的二叉搜索树，它的左右子树的高度差不超过1.这种平衡性保证了在每次插入、删除和查找操作后，树的高度不会超过Logn，从而保证了树的操作效率。

Avl树的插入、删除和旋转操作的实现比较复杂，因为需要在保持平衡的同时还要保证二叉搜索树的性质.Avl树的查找操作与普通的二叉搜索树相同，只需要进行常规的比较操作.

Avl树的优点是在插入、删除和查找操作时保证了树的平衡，从而保证了树的操作效率；缺点是实现比较复杂，需要额外的平衡操作.在实际应用中、Avl树适合用于需要频繁插入、删除和查找的场景，例如数据库索引、天气预报等应用领域.

2.6%二叉树的性质

1.二叉树由节点组成，每个节点最多有两个子节点，分别为左子节点和右子节点.
2.根节点是二叉树的顶端节点，它没有父节点.
3.叶子节点是没有子节点的节点.
4.每个节点都有一个键或值，用于对节点进行查找、排序或比较.
5.子树是由节点及其所有后代构成的子集.
6.二叉树的高度是从根节点到最深叶子节点的最长路径的长度.
7.二叉树可以是空的，也可以只有一个节点.
8.二叉树可以是有序的(例如，二叉搜索树)，也可以是无序的.
9.二叉树可以使用递归算法进行遍历，包括先序遍历、中序遍历和后序遍历.
10.二叉树的平衡性和搜索性能是构建二叉树时需要考虑的重要问题.

2.7%二叉树的存储结构

2.7.1顺序存储结构

二叉树的顺序存储结构是将树的节点按照层次顺序依次存放在一个一维数组中，使父节点和子节点之间的关系通过数组下标来确定的存储方式.对于一颗深度为k的二叉树，其顺序存储结构需要开辟2^k-1个空间，空节点也需要占位.

具体的存储方式如下：

假设二叉树的根节点存放在数组下标为1的位置，则：

-节点I的父节点为I/2
-节点i的左子节点为2*i
-节点i的右子节点为2*i+1

在顺序存储结构中，可以方便地进行遍历操作.但是，由于二叉树节点数量的限制，该存储方式对于完全二叉树的利用率最高，对于其他类型的二叉树则存在空间浪费的问题.同时，在进行插入或删除操作时，可能需要移动其他节点，效率较低.

2.7.2链式存储结构

二叉树的链式存储结构是将二叉树中的每个节点定义为一个结构体，该结构体中包含3个字段:数据域、左子节点指针和右子节点指针.每个节点的左子节点指针指向其左子节点，右子节点指针指向其右子节点，如果没有子节点，则相应指针为空.

下面是一个二叉树节点的结构体定义示例：

struct BinaryTreeNode{
    int val;   // 数据域
    BinaryTreeNode* left;  // 左子节点指针
    BinaryTreeNode* right;  // 右子节点指针
};

使用链式存储结构构建二叉树时，需要定义一个二叉树的根节点指针，表示整个二叉树的根节点.示例代码如下：

BinaryTreeNode* root = NULL;   // 二叉树的根节点指针

在实际应用中，可以通过递归的方式构建二叉树，将每个节点的左子树和右子树作为独立的二叉树进行构建.例如，下面的代码演示了如何构建一个简单的二叉树.

BinaryTreeNode* buildTree(){
    int val;
    cin >> val;
    if(val == -1)   // 如果输入-1，表示该节点为空
        return NULL;
    BinaryTreeNode* node = new BinaryTreeNode();
    node->val = val;
    node->left = buildTree();   // 构建左子树
    node->right = buildTree();   // 构建右子树
    return node;
}

上述代码中，如果输入为-1，则返回空，表示该节点为空。否则，创建一个新节点，并递归构建左、右子树，最终返回该节点.使用该方法可以构建一棵任意形态的二叉树.

3个、二叉树的遍历

3.1先序遍历

先序遍历二叉树的算法如下：

访问根节点.
对根的左子树进行先序遍历.
对根的右子树进行先序遍历.

C语言实现代码如下：

//先序遍历二叉树
void preOrderTraversal(BiTree p)
{
    if(p != NULL)
    {
        printf("%c ", p->data);                //输出根节点的值
        preOrderTraversal(p->lchild);          //遍历左子树
        preOrderTraversal(p->rchild);          //遍历右子树
    }
}

其中，BiTree是二叉树的节点类型，包含指向左子树和右子树的指针，以及节点的数据.由于先序遍历是从根节点开始的，所以该算法的入口参数是指向根节点的指针：p那就是。

3.2中序遍历

中序遍历二叉树的算法如下：

对根的左子树进行中序遍历.
访问根节点.
对根的右子树进行中序遍历.

C语言实现代码如下：

//中序遍历二叉树
void preOrderTraversal(BiTree p)
{
    if(p != NULL)
    {

        preOrderTraversal(p->lchild);          //遍历左子树
        printf("%c ", p->data);                //输出根节点的值
        preOrderTraversal(p->rchild);          //遍历右子树
    }
}

3.3%后序遍历

后序遍历二叉树的算法如下：

对根的左子树进行后序遍历.
对根的右子树进行后序遍历.
访问根节点.

C语言实现代码如下：

//后序遍历二叉树
void preOrderTraversal(BiTree p)
{
    if(p != NULL)
    {

        preOrderTraversal(p->lchild);          //遍历左子树

        preOrderTraversal(p->rchild);          //遍历右子树
        printf("%c ", p->data);                //输出根节点的值
    }
}

3.4%层次遍历

二叉树的层次遍历是按照树的层次顺序遍历每个节点.具体实现方法是使用队列数据结构，从根节点开始，将其入队，然后循环执行以下步骤：

将队首节点出队，并输出该节点的值.
将该节点的左子节点入队(如果该节点有左子节点的话)。
将该节点的右子节点入队(如果该节点有右子节点的话)。
如果队列不为空，则返回步骤1、否则遍历结束.

下面是C语言的代码实现：

#include<stdio.h>
#include<stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct TreeNode* create_node(int val) {
    struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void level_order_traversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode* queue[1000];
    int front = 0;
    int rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        struct TreeNode* node = queue[front++];
        printf("%d ", node->val);
        if (node->left != NULL) {
            queue[rear++] = node->left;
        }
        if (node->right != NULL) {
            queue[rear++] = node->right;
        }
    }
}

int main() {
    struct TreeNode* root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);
    root->right->left = create_node(6);
    root->right->right = create_node(7);
    level_order_traversal(root);
    return 0;
}

3.5%由二叉树的遍历序列构造二叉树

3.5.1前序+中序

据二叉树的遍历序列，可以分为前序遍历、中序遍历和后序遍历三种.其中，前序遍历的第一个节点为根节点，中序遍历中根节点前面的都是左子树的节点，根节点后面的都是右子树的节点.因此，可以利用前序遍历和中序遍历序列构造二叉树.

具体步骤如下：

根据前序遍历序列确定根节点.
在中序遍历序列中找到根节点的位置，根节点左边的节点构成左子树的中序遍历序列，右边的节点构成右子树的中序遍历序列.
根据左子树的中序遍历序列和左子树的前序遍历序列，递归构造左子树.
根据右子树的中序遍历序列和右子树的前序遍历序列，递归构造右子树.
最后得到完整的二叉树.

例如，假设有如下的前序遍历序列和中序遍历序列：

前序遍历序列：1 2 4 7 3 5 6 8中序遍历序列：4 7 2 1 5 3 8 6

首先确定根节点为%1、在中序遍历序列中找到根节点%1的位置，左边的序列为%4%7%2、右边的序列为%5%3%8%6。

根据左子树的前序遍历序列1 2 4 7和中序遍历序列4 7 2，可以递归构造左子树.同理，根据右子树的前序遍历序列3 5 6 8和中序遍历序列5 3 8 6，可以递归构造右子树.

最后得到如下的二叉树：

3.5.2后序+中序

我们可以根据以下步骤构造出该二叉树.

从层次遍历序列中取出根节点，将其作为二叉树的根节点.
在中序遍历序列中找到根节点的位置，并将其分为左子树和右子树两个部分.
在层次遍历序列中找到左子树和右子树的位置，并分别取出左子树和右子树的节点序列.
对左子树和右子树分别递归执行步骤1-3，直到所有节点都被处理完毕.

下面是一个示例：

层次遍历序列：[1，2，3，4，5，6，7]中序遍历序列：[4，2，5，1，6，3，7]

首先取出根节点1，然后在中序遍历序列中找到位置3，将其分为左子树[4，2，5]和右子树[6，3，7]。接下来，在层次遍历序列中分别取出左子树[2，4，5]和右子树[3，6，7]，然后对它们分别递归执行以上步骤.

左子树：[2，4，5]中序遍历序列：[4，2，5]从中序遍历序列中可以得知，根节点为2，左子树为空，右子树为[4，5]。在层次遍历序列中分别取出左子树[4]和右子树[5]，对它们分别递归执行以上步骤.

左子树：[4]中序遍历序列：[4]根节点为4，左子树为空，右子树为空。

右子树：[5]中序遍历序列：[5]根节点为5，左子树为空，右子树为空。

把左右子树分别添加到节点2的左右子节点，并返回节点2.

右子树：[3，6，7]中序遍历序列：[6，3，7]从中序遍历序列中可以得知，根节点为3，左子树为[6]，右子树为[7]。在层次遍历序列中分别取出左子树[6]和右子树[7]，对它们分别递归执行以上步骤.

左子树：[6]中序遍历序列：[6]根节点为6，左子树为空，右子树为空。

右子树：[7]中序遍历序列：[7]根节点为7，左子树为空，右子树为空。

把左右子树分别添加到节点3的左右子节点，并返回节点3.

最后把节点2和节点3分别添加到根节点1的左右子节点，二叉树的构造完成.

具体步骤如下：

后序遍历的最后一个节点一定是根节点，根据根节点在中序遍历中的位置，可以将中序遍历序列分为左子树和右子树两部分.
再根据左子树和右子树的节点数量，可以将后序遍历序列分为左子树和右子树两部分.
递归地对左子树和右子树分别进行步骤1和2，构造出左子树和右子树的二叉树.
将根节点与左子树和右子树连接起来，构造出整个二叉树.

中序序列为：[9，3，15，20，7]
后序序列为：[9，15，7，20，3]
构造出来的二叉树为：是的

3.5.3层次+中序

具体步骤如下：

从层次遍历序列中取出根节点，将其作为二叉树的根节点.
在中序遍历序列中找到根节点的位置，并将其分为左子树和右子树两个部分.
在层次遍历序列中找到左子树和右子树的位置，并分别取出左子树和右子树的节点序列.
对左子树和右子树分别递归执行步骤1-3，直到所有节点都被处理完毕.

下面是一个示例：

层次遍历序列：[1，2，3，4，5，6，7]中序遍历序列：[4，2，5，1，6，3，7]

左子树：[4]中序遍历序列：[4]根节点为4，左子树为空，右子树为空。

右子树：[5]中序遍历序列：[5]根节点为5，左子树为空，右子树为空。

把左右子树分别添加到节点2的左右子节点，并返回节点2.

左子树：[6]中序遍历序列：[6]根节点为6，左子树为空，右子树为空。

右子树：[7]中序遍历序列：[7]根节点为7，左子树为空，右子树为空。

把左右子树分别添加到节点3的左右子节点，并返回节点3.

最后把节点2和节点3分别添加到根节点1的左右子节点，二叉树的构造完成.

4个、线索二叉树

4.1概念及作用

线索二叉树是一种对二叉树进行优化的数据结构，它的作用是在二叉树的基础上添加线索，使得遍历二叉树时能够更加高效地进行.

线索化的思路是将二叉树中的空节点指向该节点在某种遍历次序下的前驱或后继节点，这样就可以避免在遍历时需要通过递归或栈来跳转到该节点的前驱或后继节点.

具体来说，线索二叉树可以实现以下几个功能：

1.实现中序遍历的非递归算法.由于线索化后，可以直接找到节点的前驱或后继节点，因此可以不使用递归或栈而直接遍历整个二叉树，从而避免了空间复杂度的增加.

2.查找节点的前驱或后继节点.由于线索化后，可以直接找到节点的前驱或后继节点，因此可以在常数时间内完成该操作，而不需要遍历整个二叉树.

3.实现双向链表.将二叉树进行线索化后，可以得到一个双向链表，该链表可以用于实现一些高效的算法，如快速查找某个节点的前驱或后继节点等.

4.2二叉树线索化

4.2.1中序线索化

二叉树线索化是指对一个二叉树进行遍历，记录遍历的过程中每个节点的前驱和后继节点，然后将这些节点的左右子树指针改为指向其前驱和后继节点的指针的操作.

常见的线索化方式分为前序线索化、中序线索化和后序线索化，它们的区别在于记录前驱和后继节点的顺序不同.

中序线索化，具体过程如下：

从根节点开始，进行中序遍历；
如果当前节点有左子树，就递归遍历左子树；
处理当前节点，记录前驱节点和后继节点；
如果当前节点有右子树，就递归遍历右子树.
遍历完整棵树后，将最后一个节点的后继指针指向空节点.

处理当前节点时，记录前驱和后继节点的方法如下：

如果当前节点的左子树为空，那么它的前驱节点就是它的前一个被访问的节点；
如果当前节点的前驱节点的右子树为空，那么它的前驱节点就是当前节点；
如果当前节点的右子树为空，那么它的后继节点就是它的后一个被访问的节点；
如果当前节点的后继节点的左子树为空，那么它的后继节点就是当前节点.

线索化后的二叉树可以使遍历操作更加高效，因为不需要再使用递归或栈等数据结构来获得下一个节点，而是可以直接通过前驱和后继指针来找到.

4.2.2先序线索化

先序线索化，步骤如下：

初始化:定义一个指针Pre保存上一个访问的结点，初始值为为空。
从根节点开始，按照先序遍历的顺序遍历二叉树.
对于当前结点Curr、若其左孩子为空，则将其左指针指向Pre、并将其左标记设置为线索，即Thread。此时，Pre的右指针指向Curr.
对于当前结点Curr，若其右孩子为空，则将其右指针指向Pre的右孩子，并将其右标记设置为线索，即Thre.此时，Pre指向Curr.
对于当前结点Curr，若其左孩子和右孩子都不为空，则将其左指针指向其左孩子，并将其左标记设置为指针，即链接。然后，递归处理其左子树，处理完后，将其右指针指向其右孩子，并将其右标记设置为指针，即链接。最后，递归处理其右子树.

4.2.3后序线索化

后序线索化的步骤如下：

1.从根节点开始遍历二叉树，依次访问左子树和右子树.
2.对于每一个节点，若其左子树非空且未被访问过，则递归遍历其左子树.
3.对于每一个节点，若其右子树非空且未被访问过，则递归遍历其右子树.
4.当节点的左、右子树都已被访问过，将该节点加入到后序线索化的链表中.若左子树为空，则将该节点的前驱指向其父节点，并将左线索标志设置为1.若右子树为空，则将该节点的后继指向其父节点，并将右线索标志设置为1.

重复以上步骤，直到遍历完整个二叉树，并得到后序线索化的链表.

4.3%存储结构

线索二叉树的存储结构包括两部分:数据结构和线索.

1.数据结构：
线索二叉树的数据结构和普通二叉树的数据结构一样，包含节点的数据和指向左右子树的指针.每个节点包含以下元素：
--数据
-指向左子节点的指针(左子)
--标志位LTag，用于表示该指针是否为线索
-指向右子节点的指针(右孩子)
--标志位rtag，用于表示该指针是否为线索

2.线索：
在线索二叉树中，每个节点左右子节点的指针可能是指向其前驱或者后继节点.因此，需要在节点的数据结构中增加两个标志位LTag和rtag，来表示该指针是否为线索，以及指向的是前驱还是后继.

具体来说，如果一个节点的左子节点指针为线索，那么它的LTag标志位为1，表示该指针指向的是该节点的前驱节点；如果右子节点指针为线索，那么它的rTag标志位为1，表示该指针指向的是该节点的后继节点。如果左右子节点均不是线索，则对应的LTag和rTag都为0。

线索化过程就是对二叉树的节点进行标记，将左右子节点指针指向它们的前驱后继节点，把普通二叉树转化为线索二叉树.

4.4%三种线索二叉树

4.4.1中序线索二叉树

中序线索二叉树是一种特殊的二叉树，其特点是在二叉树的节点中添加了指向中序遍历序列中该节点的前驱和后继节点的指针，这样就可以通过这些指针快速地访问该节点的前驱和后继节点，从而在中序遍历时，可以直接找到下一个节点，而无需递归查找.

在中序线索二叉树中，每个节点可以分为两种类型:左线索节点和右线索节点.

左线索节点:如果一个节点没有左子树，则将其左指针指向其在中序遍历中的前驱节点，即左线索.

右线索节点:如果一个节点没有右子树，则将其右指针指向其在中序遍历中的后继节点，即右线索.

对于一个节点，如果其存在左子树，则将其左子树中最右侧的节点的右指针指向该节点，即为其中序遍历序列中的前驱节点；如果其存在右子树，则将其右子树中最左侧的节点的左指针指向该节点，即为其中序遍历序列中的后继节点.

通过添加这些线索指针，可以在中序遍历时避免递归查找下一个节点，从而提高了遍历效率.

4.4.2先序线索二叉树

先序线索二叉树是对二叉树的一种特殊表示方法，它利用线索来连接指向二叉树中各个结点的前驱和后继.其中，先序线索二叉树是在先序遍历的基础上建立起来的.

具体地，将二叉树中所有的空指针域改为指向该结点在先序遍历中的直接前驱或直接后继的线索，从而形成先序线索二叉树.

建立先序线索二叉树的过程中，需要额外开辟两个指针域，分别记录当前结点的直接前驱和直接后继.具体建立方法如下：

1.对于根结点，将其前驱指针指向空.
2.对于左子树不为空的结点，将其左孩子作为其直接后继，将其前驱指针指向其在先序遍历中的前面一个结点(即其父结点)。
3.对于右子树不为空的结点，将其右孩子作为其直接后继，将其前驱指针指向其左子树的最右下的结点(即其左子树中最后被访问的结点)。

这样，就可以建立起一棵先序线索二叉树.在遍历时，可以利用线索快速地访问结点的前驱和后继.

4.4.3后序线索二叉树

后序线索二叉树是一种二叉树的线索化方式，它在中序线索二叉树的基础上，再添加了对后继结点的线索化.在后序线索二叉树中，每个结点除了有一个后继结点指针，还有一个前驱结点指针.

后序线索化的过程是从根结点开始遍历二叉树，先递归线索化左子树，再递归线索化右子树，最后对根结点进行线索化.具体步骤如下：

1.如果当前结点的左子树为空，则将其左子树指向其前驱结点，标记左子树为线索化.

2.如果当前结点的前驱结点的右子树为空，则将其右子树指向当前结点，标记右子树为线索化.

3.更新当前结点的前驱结点为当前结点.

最后一个结点的后继结点指针为空，前驱结点指针指向其前驱结点.通过后序线索化，可以实现对二叉树的后序遍历的线性时间复杂度.

4.5%手算画出线索二叉树

步骤如下：

1.确定线索二叉树的类型--中序，先序，后序

2.按照对应的遍历规则，确定各个结点的访问顺序，并写上序号

3.将n+1个空链域连上前驱，后继

🤞❤️🤞❤️🤞❤️🤞❤️🤞❤️🤞❤️树与二叉树的知识点总结就到这里啦，如果对博文还满意的话，劳烦各位看官动动“发财的小手”留下您对博文的赞和对博主的关注吧

上一篇：蟒蛇新手入门
下一篇：Perch WordPress主题博客主题下载

[数据结构]树与二叉树知识点总结

欢~迎~光~临~^_^

1个、树

1.1基本概念及基本术语

1.2常考性质

2个、二叉树

2.1基本概念

2.2满二叉树

2.3完全二叉树

2.4%二叉排序树

2.5平衡二叉树

2.6%二叉树的性质

2.7%二叉树的存储结构

2.7.1顺序存储结构

2.7.2链式存储结构

3个、二叉树的遍历

3.1先序遍历

3.2中序遍历

3.3%后序遍历

3.4%层次遍历

3.5%由二叉树的遍历序列构造二叉树

3.5.1前序+中序

3.5.2后序+中序

3.5.3层次+中序

4个、线索二叉树

4.1概念及作用

4.2二叉树线索化

4.2.1中序线索化

4.2.2先序线索化

4.2.3后序线索化

4.3%存储结构

4.4%三种线索二叉树

4.4.1中序线索二叉树

4.4.2先序线索二叉树

4.4.3后序线索二叉树

4.5%手算画出线索二叉树

相关推荐