东北大学842（6）——树编程题

笔记所有内容参考《东大红皮书》《王道》《天勤》，由本人分析整理。

二叉链表结构

typedef struct BiTNode {
    int data;
    struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;

递归模板，可以解决大部分的算法题

void func(BiTree T, ...) {
    if(!T) {
        return;
    }
    //visit(T); 先序遍历
    func(T->lchild, ...);
    //visit(T); 中序遍历
     func(T->rchild, ...);
    //visit(T); 后序遍历
}

可以解决的问题：

遍历树
建立树
- 一个结点getchar一次，空格就直接不建这个结点
- 顺序结构的序列
- 两个遍历序列
统计结点数
统计叶子数
统计度为1的结点数
求树高
- max{ 左树高 + 1, 右树高 + 1 }
求两个结点相距最远的距离
- 距离 = 左树高 + 1 + 右树高
求某结点的平衡因子
- 左树高 - 右树高
根据结点的平衡因子求树高
- 右树高 + 平衡因子 + 1
- 左树高 - 平衡因子 + 1
统计平衡的结点数
统计不平衡的结点数
交换左右子树
判断两棵树是否相似
复制树
利用叶子结点的空指针区域将叶子结点链接成一个带头结点的双链表
- 新建一个树结点作为链表的头结点，每遍历到了叶子，利用头插法插入头结点后
```
//p是叶子，L是链表头结点
p->lchild = L->lchild;
p->rchild = L;
L->lchild = p;
p->rchild->lchild = p; //要检查是否有rchild
```
求算术表达式
- 叶子是数值value，非叶子是运算符op，return lvalue op rvalue;
查找值为x的结点
求值为x的结点所在层数

求值为x的所有祖先

利用一个全局栈，函数一开始把结点压栈，函数结束前弹栈；全局栈保存了当前结点的祖先和本身

Stack S;
void func(BiTree T, int x) {
    if(!T) {
        return;
    }
    push(&S, T);
    if(T->data == x) {
        print(&S);
    }
    func(T->lchild, x);
    func(T->rchild, x);
    pop(&S, T);
}

建立祖先关系
- func(T->child, T);

层次遍历模板，可以解决剩余问题

void levelOrderTravel(BiTree T) {
    Queue Q;
    initQueue(&Q);
    enQueue(&Q, T);
    BiTNode* p;
    while(!isEmpty(&Q)) {
         p = deQueue(&Q);
         visit(p);
         if(p->lchild) {
            enQueue(&Q, p->lchild);
        }
        if(p->rchild) {
            enQueue(&Q, p->rchild);
        }
    }
}

可以解决的问题：

遍历树
判断是否为完全二叉树
- 不管左右子树是否为NULL，直接入队；当出队出现NULL，看看队列剩余是否全为NULL
求树最大宽度
- 把结点的层数也一起入队，统计同一层结点数

非递归先序遍历

注意压栈顺序，先压右再压左，先弹左再弹右。（没考过）

void preOrderTravel(BiTree T, ...) {
    Stack S；
    initStack(&S);
    push(&S, T);
    BiTNode* p;
    while(!isEmpty(&S)) {
        p = pop(&S);
        visit(p);
        if(p->rchild) {
            push(&S, p->rchild);
        }
        if(p->lchild) {
            push(&S, p->lchild);
        }
    }
}

非递归的中序、后序都比较复杂，一般不考。

线索二叉树

不使用栈和递归，中序遍历中序线索二叉树

BiTNode* First(BiTNode* p) {
    while(p -> lchild) {
        p = p->lchild;
    }
    return p;
}

BiTNode* Next(BiTNode* p) {
    if(p->rtag) {
        return p->rchild;
    }
    return First(p->rchild);
}

void InOrder(BiTree T) {
    for(BiTNode* p = First(T); p; p = Next(p)) {
        visit(p);
    }
}

不使用栈和递归，先序遍历先序线索二叉树

void preOrder(BiTree T) {
    BiTNode* p = T;
    while(p) {
        while(!p->ltag) {
            visit(p);
            p = p->lchild;
        }
        visit(p);
        p=p->rchild;
    }
}

不使用栈和递归，先序遍历中序线索二叉树

void preOrder(BiTree T) {
    BiTNode* p = T;
    while(p) {
        while(!p->ltag) {
            visit(p);
            p = p->lchild;
        }
        visit(p);
        while(p->rtag) {
            p = p->child; //一直往上爬，直到有右孩子
        }
        if(p) { //防止最后一个结点
            p = p->child; //跳到上面双亲的右孩子上
        }
    }
}

不使用栈和递归，后序遍历后序线索二叉树
- 还需要parent区域。当右孩子都遍历结束了，通过parent往上跑
二叉树中序线索化（没考过）
- 需要入参时候把pre结点传进来，然后pre结点尝试与当前结点建立线索

二叉排序树

插入一个结点到排序树

BiTNode* pre, * p;
pre保存要插入位置的双亲结点，
p要插入位置，类似于链表的插入。

void insert(BiTree T, BiTNode* node) {
    BiTNode* pre, * p = T;
    while(p) {
        if(node->data < p->data) {
            pre = p;
            p = p->lchild;
        } else if(p->data < node->data) {
            pre = p;
            p = p->rchild;
        } else {
            //存在等值结点处理，一般不可能有等值的题目，可以去掉这个情况
        }
    }
    if(node->data < pre->data) {
        pre->lchild = node;
    } else if(pre->data < node->data) {
        pre->rchild = node;
    } else {
        //存在等值结点处理，一般不可能有等值的题目，可以去掉这个情况
    }
}

删除排序树某结点
- 叶子结点，直接free
- 只有左孩子，左孩子代替原结点
- 只有右孩子，右孩子代替原结点
- 既有左孩子，又有右孩子，把右孩子插入左孩子的最右子孙的右孩子；
  此时变成最后左孩子的情况
```
BiTNode* maxNode = (*T)->lchild;
while(maxNode->rchild) {
    maxNode = maxNode->rchild;
}
maxNode->rchild = (*T)->rchild;
BiTNode* temp = *T;
*T = (*T)->lchild;
free(temp);
```
合并两个排序树
- 一棵树递归遍历，获取结点，把这个结点插入另外一棵树。

特别的题

一棵树采用孩子兄弟链表存储，计算树的度
- 一个结点的度为左孩子的右子孙个数