小yo 博客

Back

数据结构--二叉树[更新中]
3 min read
数据结构— views

数据结构--二叉树[更新中]

本篇旨在总结数据结构——二叉树的相关知识，并通过C语言实现各种算法 二叉树的代码实现 二叉树构造算法 递归算法 - 以二叉链表，且输入序列为先序序列为例（其中输入-1表示该处为空指针） 前序+中序遍历序列构造算法 后续+中序遍历序列构造算法 前序遍历算法 递归算法 非递归算法1 非递归算法2 时间/空间复杂度分析 -

二叉树的代码实现

二叉树构造算法

递归算法

  • 以二叉链表，且输入序列为先序序列为例（其中输入-1表示该处为空指针）
typedef struct Node{
    int data;
    Node* left;
    Node* right;
}BTree; // 二叉链表的结点定义

BTree* CreateBTree(){
    int x;
    scanf("%d",&x);
    if (x == -1) return NULL; // 输入-1表示该处为指针
    BTree* BT;
    BT = (BTree*)malloc(sizeof(BTree));
    BT->data = x; // 先序序列，则优先存储根结点
    BT->left = CreateBTree(BT->left); // 递归创建左子树
    BT->right = CreateBTree(BT->right); // 递归创建右子树
    return BT;
}

前序+中序遍历序列构造算法

后续+中序遍历序列构造算法

前序遍历算法

递归算法

int PreOrderBTree(BTree* BT){
    if (BT == NULL) return 0; // 节点为空则结束递归
    visit(BT);  // 先序遍历，先访问根节点
    PreOrderBTree(BT->left); // 节点不为空，开始递归
    PreOrderBTree(BT->right);
    return 0;
}

非递归算法1

int PreOrderBTree(BTree* BT,S*S){ // 借助堆栈来记录路径
    if (BT == NULL) return 0; // 空二叉树直接返回0
    BTree* p = BT;
    S->top = 0; // 初始化
    while (p != NULL || S->top != 0){ 
        while (p != NULL){ // 一直沿左子树遍历直至空
            visit(p); // 先序遍历。先访问根节点
            push(p); // 记录该结点
            p = p->left; // 沿左子树遍历
        }
        if (S->top != 0){ 
            p = pop(S); // 栈顶元素出栈
            p = p->right; // 访问右子树
        }
    }
    return 0;
}

非递归算法2

int PreOrderBTree(BTree* BT,S*S){ // 借助堆栈来记录路径
    if (BT == NULL) return 0; // 空二叉树直接返回0
    BTree* p = BT;
    S->top = 0; // 堆栈置空
    push(p); // 根结点先入栈
    while(S->top >0){ //循环结束条件：堆栈为空
        p = pop(S); //出栈
        visit(p); //先序遍历，所以先访问根节点
        if (p->right != NULL){
            push(p->right); // 右结点入栈
        }
        if (p->left != NULL){
            push(p->left); // 左结点入栈，入栈顺序：右结点->左结点，保证能够先访问左结点
        }
    }
    return 0;
}

时间/空间复杂度分析

  • 时间复杂度：由非递归算法2可知，每个结点都只被访问一次，则时间复杂度 T=O(n)T=O(n)

  • 空间复杂度：由非递归算法2可知，堆栈一次性最多存储h+1h+1个元素(hh表示二叉树的深度)，而hh最大为nn，所以空间复杂度 S=O(n)S=O(n)

中序遍历算法

递归算法

int InOrderBTree(BTree* BT){
    if (BT == NULL) return 0; // 节点为空直接结束递归
    InOrderBTree(BT->left); //中序遍历先访问左子树
    visit(BT); // 其次访问根节点
    InOrderBTree(BT->right); //最后访问右子树
    return 0;
}

非递归算法1

int InOrderBTree(BTree* BT , S*S){ // 借助堆栈来记录路径
    if (BT == NULL) return 0; // 空二叉树直接返回0
    BTree* p = BT;
    S->top = 0; // 堆栈置空
    while (p != NULL || S->top != 0){ 
        while (p != NULL) { // 一直沿左子树遍历直至为空
            push(p); //中序遍历，所以先不需要访问根结点
            p = p->left;
        }
        if (S->top != 0){
            p = pop(S); 
            visit(p); // 左子树都遍历完了，访问根节点
            p = p->rigth; // 开始右子树
        }
    }
    return 0;
}

非递归算法2

  • 需要改造堆栈，使每个元素加上一个tag（1,2）来标识第几次访问
int InOrderBTree(BTree* BT, S*S){
    if (BT == NULL) return 0;
    BTree* p = BT;
    S->top = NULL; // 把栈置空
    push(p,1); // p入栈的同时tag记为1
    while (S->top != NULL){ // 循环条件：堆栈不空
        if (S->top.tag == 1){ // tag=1 标识第一次访问
            p = pop(S); // 出栈
            if (p->right != NULL) push(p->right,1); // 右子树入栈，tag记为1
            push(p,2); // 二次入栈，tag记为2
            if (p->left != NULL) push(p->left,1); // 左子树入栈，tag记为1
        }
        else if (S->top.tag == 2){ // tag=2 标识第二次访问
            p = pop(S); // 出栈
            visit(p); // 访问
        }
    }
    return 0;
}

时间/空间复杂度分析

  • 时间复杂度：由非递归算法2可知，每个结点被访问两次，所以时间复杂度 T=O(n)T=O(n)
  • 空间复杂度：由非递归算法2可知，堆栈一次性最多存储h+1h+1个元素(hh表示二叉树的深度)，而hh最大为nn，所以空间复杂度 S=O(n)S=O(n)

后序遍历算法

  • 非递归算法需借用堆栈

递归算法

int PostOrderBTree(BTree* BT){
    if (BT == NULL) return 0; // 空二叉树直接返回0
    PostOrderBTree(BT->left);  // 后序遍历先访问左子树
    PostOrderBTree(BT->right); // 然后访问右子树
    visit(BT); // 后序遍历最后访问根节点
    return 0;
}

非递归算法1

int PostOrderBtree(BTree* BT,S*S){ // 借助堆栈来记录路径，同时需要引入tag来标识状态
    BTree* p = BT;
    S->top =0; // 初始化
    while (p != NULL || top != 0){
        while (p != NULL){ // 先一直遍历左子树直至空
            push(p,1); //p入栈并将tag记为1
            p = p->left;
        }
        p = pop(S); // 出栈
        if (p->tag == 1){ //tag=1标识第一次访问
            push(p,2); //二次入栈，tag记为2
            p = p->right; // 开始遍历右子树
        }
        else {
            visit(p); // 第二次访问，说明左右子树都遍历完了，可以访问p了
            p = NULL; // 非常重要的一步！将p置为空，才能开启下次循环，否则又开始遍历p的左子树了
        }
    }
    return 0;
}

非递归算法2

  • 需要改造堆栈，使每个元素加上一个tag（1,2,3）来标识第几次访问
int PostOrder(BTree* BT,S*S){
    if (BT == NULL) return 0;
    BTree* p = BT;
    S->top = NULL; // 堆栈置空
    push(p,1); // p入栈，同时tag记为1
    while (S->top != NULL){ // 循环结束条件：堆栈为空
        if (S->top.tag == 1){ //tag=1，标识第一次访问
            p = pop(S); // 出栈
            push(p,2); // 二次入栈，同时tag记为2
            if (p->left != NULL) push(p->left,1); //左子树入栈
        }
        else if (S->top.tag == 2){ // tag=2，标识第二次访问
            p = pop(S); // 出栈
            push(p,3); // 三次入栈，同时tag记为3
            if (p->right != NULL) push(p->right,1); // 右子树入栈
        }
        else if (S->top.tag == 3){ // tag=3，标识第三次访问
            p = pop(S); // 出栈
            visit(p); // 访问p
        }
    }
    return 0;
}

时间/空间复杂度分析

  • 时间复杂度：由非递归算法2可知，每个结点被访问两次，所以时间复杂度 T=O(n)T=O(n)

  • 空间复杂度：由非递归算法2可知，堆栈一次性最多存储h+1h+1个元素(hh表示二叉树的深度)，而hh最大为nn，所以空间复杂度 S=O(n)S=O(n)

逐层遍历二叉树

  • 需借助队列

算法

int Q(BTree* BT, Quene*Q){ // 逐层遍历二叉树
    BTree p = BT;
    Empty(Q); // 将队列置空
    if (p != NULL){ // 根节点入队
        InsQ(p);
    }
    while(!Empty(Q)){ // 当队列为空时遍历结束
        p = outQ(Q); //出队并访问
        visit(p);
        if (p->left != NULL){ // 左节点入队
            InsQ(p->left);
        }
        if (p->right != NULL){ // 右节点入队
            InsQ(p->right);
        }
    }
}

时间/空间复杂度分析

  • 时间复杂度：每个结点访问一次，则时间复杂度 T=O(n)T=O(n)
  • 空间复杂度：显然空间复杂度 S=O(n)S=O(n)

TBT(Thread BT)遍历算法

  • 任何包含n个结点的二叉树，采用二叉链表表示，有2n个指针域……（实现基础）

  • 需要修改存储结构，在节点上加入左右标识

  • 空的左指针指向“前驱”

  • 空的右指针指向“后继”

代码实现

typedef struct Node{
    int data;
    Node* left;
    Node* right;
    bit Ltag; // 取0标识指针指向儿子结点，取1标识指针指向前驱或后继
    bit Rtag; // 
}; //更改存储结构

时间/空间复杂度分析

三叉链表存储遍历

  • 需在节点上加入一个标识符，用来标注遍历情况（访问左、根、右节点）

代码实现

typedef struct Node{
    int data;
    Node* left;
    Node* right;
    char tag; // 使用char类型占用空间最小
};

int oderBTree(BTree* BT){
    BTree* p = BT;
    while( p != NULL){ 
        if(p->tag == 1){ // tag=1标识第一次访问该结点
            visit(p); // 这里以前序遍历为例
            p->tag = 2; // 访问完即改变tag
            if (p->left != NULL) p = p->left; // 访问左子树
        }
        if (p->tag == 2){ // tag=2标识第二次访问该结点
            p->tag = 3; // 若中序遍历，需在此句前visit(p)
            if (p->right != NULL) p = p->right; // 访问右子树
        }
        if (p->tag == 3){ // tag=3标识第三次访问该结点
            p->tag = 1; // 重置结点
            p = p->parent; // 返回父子树
        }
    }
    return 0;
}

时间/空间复杂度分析

  • 时间复杂度：每个结点都访问了三次，则时间复杂度 T=O(n)T=O(n)
  • 空间复杂度：没有借助任何附加空间，则空间复杂度 S=O(0)S=O(0)

递归算法

  1. 递归算法的书写过程
  2. 递归算法的执行过程 -> 非递归过程
  3. T/S分析

二叉树的应用

1. 哈夫曼树

性质

  1. WPL是最小的

  2. 权值越大的离根节点越近

  3. 不唯一

2. BST/AVL

3. T / BT转化

4. Heap(堆)

“数据结构实验”
数据结构--二叉树[更新中]
https://smallyo.top/blog/4cfde08f5a05fff5
Author小yo
Published atOctober 24, 2025
CopyrightCC BY-NC-SA 4.0
Buy me a cup of coffee ☕.