学校-二叉树相关操作复习笔记

二叉树相关操作复习笔记

一、二叉树的基本结构定义

// 常见的二叉树节点结构定义
struct BiTNode {
    char data;  // 数据域，根据需求可改为int等类型
    BiTNode *lchild, *rchild;  // 左右孩子指针
};
// 或使用typedef定义
typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;  // BiTree为指向BiTNode的指针类型

二、二叉树的创建

1. 基于带虚节点的先序序列创建

// 根据带虚结点的先序序列创建二叉树（*表示空节点）
BiTNode *createBT(string &s) {
    if(s[0]=='*') {  // 遇到虚节点，创建空树
        s=s.substr(1);  // 移除已处理的字符
        return NULL; 
    }
    BiTNode *p=new BiTNode;  // 创建新节点
    p->data=s[0];  // 赋值数据
    s=s.substr(1);  // 移除已处理的字符
    p->lchild=createBT(s);  // 递归创建左子树
    p->rchild=createBT(s);  // 递归创建右子树
    return p;
}

分析：

• 利用先序遍历的思想（根左右），通过递归方式创建二叉树
• 虚节点*用于标识空节点，解决了二叉树创建时的歧义问题
• 字符串通过引用传递并不断截取，实现了序列的顺序处理

三、二叉树的遍历

1. 层次遍历（广度优先遍历）

void LevelTraverse(BiTNode* T){
    if(T == NULL){  // 空树直接返回
        return ;
    }
    queue<BiTNode*> qu;  // 辅助队列
    qu.push(T);  // 根节点入队
    while(!qu.empty()){  // 队列不为空时循环
        BiTNode* curr = qu.front();  // 获取队头节点
        printf("%c", curr->data);  // 访问节点
        if (curr->lchild != NULL){  // 左孩子非空则入队
            qu.push(curr->lchild);
        }
        if (curr->rchild != NULL){  // 右孩子非空则入队
            qu.push(curr->rchild);
        }
        qu.pop();  // 队头节点出队
    }
    cout << endl;
}

分析：

• 核心思想是使用队列实现按层次访问节点
• 过程：根节点入队→队头节点出队并访问→其左右孩子依次入队→重复直至队空
• 时间复杂度 O (n)，空间复杂度 O (n)（最坏情况为满二叉树的最后一层）

2. 先序遍历（递归）

// 先序遍历打印叶节点示例
void PreorderPrintLeaves( BinTree BT ){
    if (BT == NULL){  // 空树直接返回
        return ;
    }
    // 若为叶节点则打印（叶节点：左右孩子均为空）
    if (BT->Left == NULL && BT->Right == NULL){
        printf (" %c", BT->Data);
    }
    PreorderPrintLeaves(BT->Left);  // 遍历左子树
    PreorderPrintLeaves(BT->Right);  // 遍历右子树
}

分析：

• 先序遍历顺序：根节点→左子树→右子树
• 递归实现简洁，利用函数调用栈保存节点状态

3. 非递归遍历

先序非递归遍历

void PreorderTraversal( BinTree BT ){
    if (BT == NULL){
        return ;
    }
    Stack st = CreateStack();  // 创建栈
    BinTree p = BT;
    Push(st, BT);  // 根节点入栈
    while (!IsEmpty(st)){  // 栈非空时循环
        p = Pop(st);  // 出栈并访问
        printf(" %c", p->Data);
        // 注意：先右后左入栈，保证左子树先访问
        if (p->Right != NULL){
            Push(st, p->Right);
        }
        if (p->Left != NULL){
            Push(st, p->Left);
        }
    }
}

中序非递归遍历

void InorderTraversal( BinTree BT ){
    if (BT == NULL){
        return;
    }
    Stack s = CreateStack();
    BinTree p = BT;
    // 循环条件：p非空或栈非空
    while (p != NULL || !IsEmpty(s)){
        if (p != NULL){  // 左子树一直入栈
            Push(s, p);
            p = p->Left;
        }
        else{  // 左子树为空时出栈访问，再处理右子树
            BinTree pop = Peek(s);
            printf (" %c", pop->Data);
            Pop(s);
            p = pop->Right;
        }
    }
}

后序非递归遍历（带标志位）

void PostorderTraversal( BinTree BT ){
    if (BT == NULL){
        return ;
    }
    Stack st = CreateStack();
    BinTree p = BT;
    while (p != NULL || !IsEmpty(st)){
        // 左子树一直入栈，标记未访问
        while (p != NULL){
            p->flag = 0;  // 0表示未访问右子树
            Push (st, p);
            p = p->Left;
        }
        p = Peek(st);
        // 若右子树存在且未访问，则处理右子树
        if (p->Right != NULL && p->flag == 0){
            p->flag = 1;  // 标记已访问右子树
            p = p->Right;
        }
        else{  // 否则出栈访问
            p = Pop(st);
            printf(" %c", p->Data);
            p = NULL;  // 避免重复处理左子树
        }
    }
}

分析：

• 非递归遍历需借助栈模拟递归过程
• 先序：根节点先出栈访问，再右后左入栈
• 中序：左子树全部入栈后，出栈访问根节点，再处理右子树
• 后序：需标记节点是否已处理右子树，确保左右子树都处理完再访问根节点

四、二叉树的常用属性计算

1. 二叉树的深度（高度）

int Depth(BiTree Tree){
    if (Tree == NULL){  // 空树深度为0
        return 0;
    }
    int leftcount = Depth(Tree->lchild);  // 左子树深度
    int rightcount = Depth(Tree->rchild);  // 右子树深度
    // 树的深度=max(左子树深度,右子树深度)+1（当前节点）
    return (leftcount > rightcount) ? (1 + leftcount) : (1 + rightcount);
}

分析：

• 递归思想：树的深度等于左右子树中深度较大者加 1
• 时间复杂度 O (n)，需要遍历所有节点

2. 叶子节点数统计

int LeafCount(BiTree T){
    if (T == NULL){  // 空树叶子数为0
        return 0;
    }
    // 叶子节点：左右孩子均为空
    if (T->lchild == NULL && T->rchild == NULL){
        return 1;
    }
    // 非叶子节点：叶子数=左子树叶子数+右子树叶子数
    return LeafCount(T->lchild) + LeafCount(T->rchild);
}

3. 度为 1 的节点数统计

int CountSingle(BiTNode *T){
    if (T == NULL){  // 空树返回0
        return 0;
    }
    // 左空右非空：度为1
    if (T->lchild == NULL && T->rchild != NULL){
        return 1 + CountSingle(T->rchild);
    }
    // 左非空右空：度为1
    if (T->lchild != NULL && T->rchild == NULL){
        return 1 + CountSingle(T->lchild);
    }
    // 其他情况：度为0或2，不计数，继续递归
    return CountSingle(T->lchild) + CountSingle(T->rchild);
}

4. 节点总数统计

int NodeCountOfBiTree ( BiTree T){
    if (T == NULL){  // 空树节点数为0
        return 0;
    }
    // 节点总数=1（当前节点）+左子树节点数+右子树节点数
    return 1 + NodeCountOfBiTree(T->lchild) + NodeCountOfBiTree(T->rchild);
}

5. 二叉树的最大宽度

int MaxWidth(BiTree T){
    if (T == NULL){  // 空树宽度为0
        return 0;
    }
    BiTree queue [100];  // 辅助队列
    int front = 0;  // 队头指针
    int rear = 0;   // 队尾指针
    int max = 0;    // 最大宽度
    queue[rear] = T;  // 根节点入队
    rear++;
    while (front < rear){
        int curr = rear - front;  // 当前层节点数
        if (curr > max){  // 更新最大宽度
            max = curr;
        }
        // 遍历当前层所有节点，将其孩子入队
        for (int i = 0; i < curr; i++){
            BiTNode* node = queue[front];
            if (node->lchild != NULL){
                queue[rear] = node->lchild;
                rear++;
            }
            if (node->rchild != NULL){
                queue[rear] = node->rchild;
                rear++;
            }
            front++;  // 节点出队
        }
    }
    return max;
}

分析：

• 利用层次遍历思想，统计每一层的节点数
• 每一层处理前，队列中元素个数即为当前层节点数
• 比较各层节点数，取最大值即为最大宽度

五、由遍历序列构造二叉树

先序序列和中序序列构造二叉树

BiTNode* CreateBT(int* pre, int *in, int n){
    if (n <= 0) {  // 节点数为0，返回空
        return NULL;
    }
    int rootVal = pre[0];  // 先序序列第一个元素为根节点值
    int pos = 0;
    // 在中序序列中找到根节点位置
    for (; pos < n; pos++) {
        if (in[pos] == rootVal) {
            break;
        }
    }
    // 递归创建左子树：先序序列从1开始，中序序列从0开始，长度pos
    BiTNode* leftTree = CreateBT(pre + 1, in, pos);
    // 递归创建右子树：先序序列从pos+1开始，中序序列从pos+1开始，长度n-pos-1
    BiTNode* rightTree = CreateBT(pre + pos + 1, in + pos + 1, n - pos - 1);
    // 创建根节点并连接左右子树
    BiTNode* root = new BiTNode(rootVal, leftTree, rightTree);
    return root;
}

分析：

• 核心原理：先序序列第一个元素是根节点，中序序列中根节点左侧为左子树，右侧为右子树
• 递归过程：找到根节点→划分左右子树范围→分别构建左右子树
• 时间复杂度 O (n²)（查找根节点位置耗时 O (n)），可通过哈希表优化为 O (n)

总结

1. 递归是二叉树操作的核心思想：创建、遍历、属性计算等都可通过递归实现
2. 辅助数据结构的应用：层次遍历用队列，非递归遍历用栈
3. 遍历序列的特性：不同遍历序列组合可唯一确定二叉树（如先序 + 中序、后序 + 中序）
4. 边界条件处理：空树（NULL）是各类操作的重要边界条件，需优先判断