5.王道课后题

每层只有一个节点

只有根节点

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
typedef struct Stack{
    int top;
    Elemtype data[MAXSIZE];
}Stack;
 
void PostOrder(BiTree T){
    Stack S;
    InitStack(S);    //初始化栈
    BiTNode *p = T, *r = NULL;
    //栈空并且p为NULL结束循环
    while (p || !(isEmpty(S)){
        //p非空
        if (p) {
            push(S, p);    //p入栈
            p = p->lchild;    //p指向p的左孩子
        }
        //p空
        else {
            //p右孩子存在并且r不指向p的右孩子（p的右孩子未遍历过）
            if (p->rchild && p->rchild != r){
                //p的右孩子入栈，并且p指向其右孩子的左孩子
                p = p->rchild;
                push(S,p);
                p = p->lchild;
            }
            //p的右孩子不存在 或 p右孩子存在，并且r指向p的右孩子
            else {
                //出栈栈顶元素并且访问它
                pop(S, p);
                visit(p);
                //r指向p，并且p置空（防止进入死循环）
                r = p;
                p = NULL;
            }
        }//else
    }//while
}

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
typedef struct LNode{
    struct LNode *next;
    BiTNode *data;
}LNode;
 
typedef struct Queue{
    int rear, front;
}LinkQueue;
 
void LevelOrder(BiTree T){
    BiTNode *p;
    LinkQueue Q;
    InitQueue(Q);    //初始化队列
    if (T == NULL) return; //空树返回
    EnQueue(T);    //根节点入队
    //循环直到队空
    while (!(isEmpty(Q)) {
        //队头元素出队，并用p指向它，进行访问
        DeQueue(Q, p);
        visit(p);
        //按顺序入栈p的右孩子和左孩子
        if (p->rchild) EnQueue(p->rchild);
        if (p->lchild) EnQueue(p->lchild);
    }
}

//非递归方式
typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
typedef struct LNode{
    BiTNode *data;
    struct LNode *next;
}LNode;
 
typedef struct Queue{
    int front, rear;
}
 
int getDepth(BiTree T) {
    //树空，返回高度0
    if (!T) return 0;
    //last指向每层最后一个元素，第一层指向根节点
    int depth = 0, front = -1, rear = -1, last = 0;
    BiTree Q[MAXSIZE];
    //根节点入队
    Q[++rear] = T;
    BiTNode* p = NULL;
    //循环直到队空
    while (front < rear) {
        //出队队头元素，并且p指向它
        p = Q[++front];
        //入队p的左右孩子（如果存在）
        if (p->lchild) Q[++rear] = p->lchild;
        if (p->rchild) Q[++rear] = p->rchild;
        //遍历到本层最后一个元素
        if (last == front) {
            //深度+1
            depth++;
            //last指向下层最后一个元素
            last = rear;
        }
    }
    return depth;
}
 
//递归方式
typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
int deep(BiTree T) {
    int ldeep, rdeep;
    //执行到叶子结点，返回高度0
    if (T == NULL) return 0;
    else {
        ldeep = deep(T->lchild);
        rdeep = deep(T->rchild);
        return (ldeep > rdeep ? ldeep : rdeep) + 1;
    }
}

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
//m1和m2分别指向PreOrder的第一个元素和最后一个元素的数组下标
//n1和n2分别指向InOrder的第一个元素和最后一个元素的数组下标
BiTree CreateTree(int PreOrder[], int InOrder[], int m1, int m2, int n1, int n2) {
    //新建结点，并传入数据
    BiTree T = (BiTNode*)malloc(sizeof(BiTNode));
    T->data = PreOrder[m1];
    //在中序序列中找到当前的树的根节点
    int i = n1;
    while (InOrder[i] != PreOrder[m1]) i++;
    //leftLen标记当前节点的左子树个数
    int leftLen = i - n1;
    //rightLen标记当前节点的右子树个数
    int rightLen = n2 - i;
    //左子树个数>0，传入相应数组内容，递归建立左子树，
    if (leftLen) T->lchild = CreateTree(PreOrder, InOrder, m1 + 1, m1 + leftLen, n1 , n1 + leftLen - 1);
    //左子树=0，左子树置空
    else T->lchild = NULL;
    //右子树同理
    if (rightLen) T->rchild = CreateTree(PreOrder, InOrder, m1 + leftLen + 1, m2, n2 - rightLen + 1, n2);
    else T->rchild = NULL;
    return T;
}

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
typedef struct LNode{
    BiTNode *data;
    struct LNode *next;
}LNode; 
 
typedef struct Queue{
    int rear, front;
}Queue;
 
bool IsComplete(BiTree T){
    BiTNode *p;
    Queue Q;
    InitQueue(Q);    //初始化队列
    if (!T) return ture;    //空树也是完全二叉树
    EnQueue(Q, T);    //根节点入队
    while( !(IsEmpty)) {    //循环直到队空
        DeQueue(Q,p);    //出队队头元素
        if(p) {    //p存在
            EnQueue(p, T->lchild);
            EnQueue(p, T->rchild);
        }
        //p不存在
        else {
            //出队队头元素，并用p指向它
            while( !(IsEmpty)){
                DeQueue(Q, p);
                //p存在则返回false
                if (p) return false;
            }
        }//else
    }//while
    return true;
}

//递归实现
typedef struct BiTNode{
    BiTNode *lchild, rchild;
    Elemtype data;
}BiTNode, *BiTree;
 
//法1
int count = 0;
int FullChildNode(BiTree T){
    if (T){
        if (T->lchild && T->rchild) count++;
        FullChildNode(T->lchild);
        FullChildNode(T->rchild);
    }
}
 
//法2
int FullChildNode(BiTree T){
    //空树，返回0
    if (T == NULL) return 0;
    //双孩子都存在
    if (T->lchild && T->rchild) {
        return FullChildNode(T->lchild) + FullChildNode(T->rchild) + 1;
    }
    //双孩子中至少有一个不存在
    else return FullChildNode(T->lchild) + FullChildNode(T->rchild);
}
 
 
//层次遍历
typedef struct BiTNode{
    BiTNode *lchild, *rchild;
    elemtype value;
}BiTNode, *BiTree;
 
typedef struct LNode{
    BiTNode *data;
    struct LNode *next;
}LNode;
 
typedef struct Queue{
    int  rear, front;
}Queue;
 
int FullChildNode(BiTree T) {
    //空树则返回0
    if (T == null) return 0;
    int count = 0;
    BiTNode* p = NULL;
    Queue Q;
    //初始化队列
    InitQueue(Q); 
    //根节点入队
    EnQueue(Q, T);
    //层次遍历二叉树
    while (!(IsEmpty(Q)) {
        //队头元素出队，并用p指向它
        DeQueue(Q, p);
        //左孩子和右孩子都存在，count++
        if (p->rchild && p->lchild) count++;
        //左孩子存在，左孩子入队
        if (p->lchild) EnQueue(Q, p->lchild);
        //右孩子存在，右孩子入队
        if (p->rchild) EnQueue(Q, p->rchild);
    }
    return count;
}

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
BiTree exchangeNode(BiTree T) {
    //temp保存右子树
    BiTNode* temp = T->rchild;
    //将右子树指针指向左子树
    T->rchild = T->lchild;
    //右子树指向temp
    T->lchild = temp;
    return T;
}
 
BiTree InOrder(BiTree T) {
    //当前节点为空，返回
    if (!T) return T;
    //交换当前节点的左右子树
    T = exchangeNode(T);
    //访问左子树
    InOrder(T->lchild);
    //访问右子树
    InOrder(T->rchild);
    return T;
}

//递归    
typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
int i = 0;    //全局变量i用于记录遍历第几个结点
 
char ch;    //ch用来标记是否找到该结点
 
int PreOrderK(BiTree T, int k) {
    //当前结点为NULL，返回'#'
    if (!T) return '#';
    //当前结点非空，已遍历结点数+1
    i++;
    //扫描到第k个结点，返回当前结点的值
    if (i == k) return T->value;
    //遍历左子树
    ch = PreOrderK(T->lchild, k);
    //如果ch的值不是'#'，则说明找到了第k个结点的值，递归出口
    //ch的值是'#'，则继续遍历右子树
    if (ch != '#') return ch;
    //遍历右子树
    else ch = PreOrderK(T->rchild, k);
    //递归出口
    return ch;
}
 
    
//非递归
#define MAXSIZE 100
typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
typedef struct Stack{
    int top = -1;
    BiTNode data[MAXSIZE];
}Stack;
 
Elemtpye PreOrderK(BiTree T, int k) {
    Stack S;
    InitStack(S);
    BiTNode* p = T;
    int count = 0;
    while (p || !(IsEmpty(S))) {
        if (p) {
            //count标记当前是第几个元素
            count++;
            //count = k返回当前p的值
            if (k == count) return p->value;
            //将p入栈
            push(S, p);
            p = p->lchild;
        }//if
        else {
            pop(S, p);
            p = p->rchild;
        }//else
    }//while
    return 0;    //0表示当前树中没有k
}

删除以它为根的子树：使用后序遍历，后序遍历的左右根的访问顺序可以很好的满足删除操作的需求

遍历树并查找值x的结点：使用层次遍历从上至下的访问树

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
typedef struct LNode{
    struct LNode *next;
    BiTNode *data;
}LNode;
 
typedef struct Queue{
    LNode *rear, *front;
}Queue;
 
//释放T及其左右子树
bool DeleteX(BiTree T) {
    //T不为空时
    if (T) {
        //T的左子树存在，删除左子树
        if (T->lchild) DeleteX(T->lchild);
        //T的右子树存在，删除右子树
        if (T->rchild) DeleteX(T->rchild);
        //释放T的存储空间
        free(T);
    }
    return true;
}
 
//遍历树查找x
BiTNode* LevelOrder_SearchX(BiTree &T, int x) {
    //树空，返回NULL
    if (!T) return NULL;
    //根节点为x，删除根节点及其子树，返回NULL
    if (T->value == x) {
        DeleteX(T);
        return NULL;
    }
    Queue Q;
    InitQueue(Q);
    //根节点入队
    EnQueue(Q, T);
    BiTNode* p = NULL;
    //循环直到队空
    while (!(IsEmpty(Q))) {
        //出队队首元素，并用p指向它
        DeQueue(Q, p);
        if (p->lchild){
            //当前结点的左孩子为x，删除左子树，并将左孩子的指针设为NULL
            if (p->lchild->value == x) {
                DeleteX(p->lchild);
                p->lchild = NULL;
            }
            //当前结点的左孩子不为x，将左孩子入队
            else EnQueue(Q, p->lchild);
        }
        if (p->rchild) {
            //当前结点的右孩子为x，删除右子树，并将右孩子的指针设为NULL
            if (p->rchild->value == x) {
                DeleteX(p->rchild);
                p->rchild = NULL;
            }
            //当前结点的右孩子不为x，将右孩子入队
            else EnQueue(Q, p->rchild);
        }
    }//while     
}

使用先序遍历的特性（根左右的访问顺序），如果当前结点的值为x，更改标记位置，依次返回双亲结点，直到根节点

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    elemtype value;
}BiTNode, *BiTree;
 
//全局变量res，用于标记是否找到x
int res = 0;
 
void InOrderSearchX(BiTree T, int x) {
    //当前结点为空，返回上一个结点
    if (!T) return;
    //当前结点的值为value，标记位res的值改为1，返回上一个结点
    if (T->value == x) {
        res = 1;
        return;
    }
    //左孩子存在，进入左孩子
    if (T->lchild) InOrderSearchX(T->lchild, x);
    //标记位为1，输出当前结点的值，返回上一个结点
    if (res) {
        cout << T->value << endl;
        return;
    }
    //右孩子存在，进入右孩子
    if (T->rchild) InOrderSearchX(T->rchild, x);
    //标记位为1，输出当前结点的值，返回上一个结点
    if (res) cout << T->value << endl;
    return;
}

非递归后序遍历，访问到值为x的结点时，栈中所有元素即为该结点的根节点，依次出栈并输出

#define MAXSIZE 100
 
typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
typedef struct Stack{
    BiTNode[MAXSIZE];
    int top;
}Stack;
 
void PostOrderSearchX(BiTree T){
    Stack S;
    InitStack(S);
    BiTNode *p = T, *r = NULL;
    while(p || !(IsEmpty(S)){
        if (p) {
            push(S, p);
            p = p->lchild;
        }
        else{
            //查看栈顶元素
            GetTop(S, p);
            //栈顶元素的值为x时
            if (p->value == x) {
                //弹出栈顶元素
                pop(S, p);
                //栈中的剩余元素都是值为x的元素的双亲结点，依次弹出并输出，return结束函数
                while(!(IsEmpty(S){
                    pop(S, p);
                    cout << p->value;
                    return;
                }
            if (p->rchild && p->rchild != r){
                p = p->rchild;
                push(S, p);
                p = p->lchild;
            }
            else {
                pop(S, p);
                visit(p);
                r = p;
                p = NULL;
            }
        }//else
    }//while
}

找公共节点和根到结点的路径用后序遍历的非递归算法

#define MAXSIZE 100
 
typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype info;
}BiTNode, *BiTree;
 
typedef struct Stack{
    int top;
    BiTNode data[MAXSIZE];
}Stack;
 
BiTNode *CommonBiTNode(BiTree root, BiTNode *p, BiTNode *q){
    Stack S, A;
    int tag = 0;
    InitStack(S);
    InitStack(A);
    BiTNode *r = NULL, *t = root, *commonNode = NULL;
    while(t || !(IsEmpty(S)){
        if (t){
            push(S, t);
            t = t->lchild;
        }
        else{
            //查看栈顶元素
            GetTop(S, t);
            //t是pq任意一个时，tag+1
            if (t == p || t == q) tag++;
            //当tag = 1时，将S中的元素自栈低到栈顶逐一压入到A中
            if (tag == 1) {
                for (int i = 0; A.top <= S.top; i++) push(A, S.data[i]);
            }
            //当tag = 2时，遍历两个栈找到相同元素
            if (tag == 2){
                //top指向的栈顶元素是p或者q，因此从top - 1去开始遍历
                for (int i = S.top - 1; i >= 0; i--){
                    for (int j = A.top - 1; j >=; j--){
                        if (S.data[i] == A.data[j]) return A.data[top];
                    }
            }
            if (t->rchild && t->rchild != r) {
                t = t->rchild;
                push(S, t);
                t = t->lchild;
            }
            else {
                pop(S, t);
                r = t;
                t = NULL;
            }
        }//else
    }//while
    //没有公共结点
    return NULL;
}

1.用层次遍历的特性，由上至下逐一遍历各层的元素，并且用cur标记已经扫描的结点个数

2.层次遍历，双队列

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype data;
}BiTNode, *BiTree;
 
typedef struct LNode{
    struct LNode *next;
    BiTNode *data;
}LNode;
 
typedef struct Queue{
    LNode *rear, *front;
}Queue;
 
//记录每层的最后一个结点
int BiTreeWidth(BiTree T) {
    //空树，宽度为0
    if (!T) return 0;
    //temp标记是否队首元素是当前层最后一个元素
    //cur记录当前层的节点个数，max记录最大值
    int width = 0, cur = 0, max = 0, temp = 0;
    BiTNode* p = NULL;
    Queue Q;
    InitQueue(Q);
    EnQueue(Q, T);
    //last指针标记每层的最后一个元素
    LNode* last = Q.rear;
    while (!IsEmpty(Q)) {
        //队头元素为last
        if (Q.front->next == last) {
            cur++;
            //更新最大值
            if (max < cur) max = cur;
            cur = 0;
            //更改temp值，表示已经到当前层最后一个元素
            temp = 1;
        }
        else {
            cur++;
            temp = 0;
        }
        DeQueue(Q, p);
        if (p->lchild) EnQueue(Q, p->lchild);
        if (p->rchild) EnQueue(Q, p->rchild);
        //更改last为下一层最后一个元素
        if (temp) last = Q.rear;
    }//while
    return max;
}
 
//双队列
int BiTreeWidth(BiTree T) {
    if (!T) return 0;
    Queue A, B;
    InitQueue(A);
    InitQueue(B);
    int level = 1, width = 0, max = 0;
    EnQueue(A, T);
    LNode* last = A.front->next;
    LNode* temp = NULL;
    BiTNode* p = NULL;
    while (!IsEmpty(A) || !IsEmpty(B)) {
        //奇数层A出队，B入队
        if (level % 2) {
            DeQueue(A, p);
            if (p->lchild) EnQueue(B, p->lchild);
            if (p->rchild) EnQueue(B, p->rchild);
        }
        //偶数层A入队，B出队
        else {
            DeQueue(B, p);
            if (p->lchild) EnQueue(A, p->lchild);
            if (p->rchild) EnQueue(A, p->rchild);
        }
        //A空
        if (IsEmpty(A)) {
            //层数+1
            level++;
            //宽度重置
            width = 0;
            //temp指向B的头结点
            temp = B.front;
            //循环遍历队列B，每遍历到一个元素宽度+1
            while (temp->next) {
                temp = temp->next;
                width++;
            }
            //更新最大值
            if (max < width) max = width;
        }
        //B空同理
        if (IsEmpty(B)) {
            level++;
            width = 0;
            temp = A.front;
            while (temp->next) {
                temp = temp->next;
                width++;
            }
            if (max < width) max = width;
        }
    }//while
    return max;
}

普通二叉树无法通过先序序列和后序序列判断二叉树，但是满二叉树可以

满二叉树中，先序序列的第一个结点和后序序列的第二个结点都是根节点

先序序列除第一个节点的左半边是左子树，右半边是右子树；后序序列除最后一个节点外，左半边是左子树，右半边是右子树

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    Elemtype value;
}BiTNode, *BiTree;
 
BiTNode* post[MAXSIZE];
 
BiTNode* PreToPost(BiTNode* pre[], BiTNode *post[], int s1,int e1, int s2, int e2) {
    int half;
    if (e1 >= s1) {
        //找到当前的中间结点
        half = (e1 - s1) / 2;
        //满二叉树中的先序遍历的第一个结点和后序遍历的最后一个结点相同，都是根节点
        post[e2] = pre[s1];
        //处理左子树
        PreToPost(pre, post, s1 + 1, s1 + half, s2, s2 + half - 1);
        //处理右子树
        PreToPost(pre, post, s1 + half + 1, e1, s2 + half, e2 - 1);
    }
}

从左到右，满足先序遍历的特性

typedef struct BiTNode{
    struct BiTNode *lchild, *rchild;
    elemtype value;
}BiTNode, *BiTree;
 
typedef struct LNode{
    struct LNode *next;
    BiTNode *data;
}LNode;
 
LinkList L;
LNode* last;
LinkList InOrder(BiTree T, LinkList &L, LNode *&last) {
    //第一次进入函数，为头结点申请空间，并且用last指向它
    if (!L) {
        L = (LNode*)malloc(sizeof(LNode));
        last = L;
    }
    //设置标记位tag
    int tag = 0;
    //有左孩子则进入左孩子，没有则tag+1
    if (T->lchild) InOrder(T->lchild, L, last);
    else tag++;
    //有左孩子则进入左孩子，没有则tag+1
    if (T->rchild) InOrder(T->rchild, L, last);
    else tag++;
    //左右孩子都不存在，则用尾插法将当前节点插入链表中
    if (tag == 2) {
        LNode* temp = (LNode*)malloc(sizeof(LNode));
        temp->data = T;
        temp->next = NULL;
        last->next = temp;
        last = temp;
    }
    return L;
}

//层次遍历，非递归
bool IsSymmetry(BiTree A, BiTree B) {
    //两树都空，返回true
    if (!A && !B) return true;
    //一树空一树不空，返回false
    else if (A && !B) return false;
    else if (!A && B) return false;
    BiTNode* p = NULL, * q = NULL;
    Queue a, b;
    InitQueue(a);
    InitQueue(b);
    //分别入队根节点
    EnQueue(a, A);
    EnQueue(b, B);
    //ab栈任意一个空则结束循环
    while (!IsEmpty(a) && !IsEmpty(b)) {
        //出队队首元素
        DeQueue(a, p);
        DeQueue(b, q);
        //pq都有左孩子则左孩子进队
        if (p->lchild && q->lchild) {
            EnQueue(a, p->lchild);
            EnQueue(b, q->lchild);
        }
        //p有左孩子，q没有左孩子，返回false
        else if (p->lchild && q->lchild == NULL) return false;
        //p没有左孩子，q有左孩子，返回false
        else if (p->lchild == NULL && q->lchild) return false;
        //右孩子同理
        if (p->rchild && q->rchild) {
            EnQueue(a, p->rchild);
            EnQueue(b, q->rchild);
        }
        else if (p->rchild && q->rchild == NULL) return false;
        else if (p->rchild == NULL && q->rchild) return false;
    }
    //结束循环时，栈都空则返回true，有栈不空则返回false
    if (IsEmpty(a) && IsEmpty(b)) return true;
    else return false;
}

//先序遍历递归实现
bool IsSymmetry(BiTree A, BiTree B) {
    int left, right;
    //当前结点都空，返回true
    if (!A && !B) return true;
    //当前结点一空一不空，返回false
    else if (!A || !B) return false;
    //当前结点都存在，进入左右子树
    else {
        left = IsSymmetry(A->lchild, B->lchild);
        right = IsSymmetry(A->rchild, B->rchild);
        return left && right;
    }
}

typedef struct ThreadNode {
    struct ThreadNode* lchild, * rchild;
    elemtype value;
    int ltag, rtag;
}ThreadNode, *ThreadTree;
 
ThreadNode *SearchPre(ThreadTree T, ThreadNode *& p) {
    ThreadNode* q = NULL;
    //p右子树存在，右子树就是p的前驱结点
    if (p->rtag == 0) q = p->rchild;
    //p右子树不存在，左子树存在，左子树就是p的前驱结点
    else if (p->ltag == 0) q = p->lchild;
    //中序线索二叉树的第一个结点的左子树为空
    else if (p->lchild == NULL) q = NULL;
    else {
        //顺着左线索寻找中序遍历的前驱结点
        while (p->lchild && p->ltag == 1) p = p->lchild;
        //p结点的祖先的左孩子是其前驱
        if (p->ltag == 0) q = p->lchild;
        //单边树，没有前驱
        else q = NULL;
    }
    return q;
}

//层次遍历
typedef struct BiTNode {
    struct BiTNode* lchild, * rchild;
    int weight;
}BiTNode, *BiTree;
 
typedef struct Queue {
    BiTNode *data[MAXSIZE];
    int top;
}Queue;
 
int GetWpl(BiTree T) {
    Queue Q;
    InitQueue(Q);
    BiTNode* p = T;
    int level = 0, wpl = 0;
    EnQueue(Q, p);
    int last = Q.rear;
    while (!IsEmpty(Q)) {
        DeQueue(Q, p);
        if (p->lchild) EnQueue(Q, p->lchild);
        if (p->rchild) EnQueue(Q, p->rchild);
        //遍历到当前层的最后一个结点，并且不是队列中最后一个结点
        if (last == Q.front && Q.front != Q.rear) {
            level++;
            last = Q.rear;
        }
        //当前结点左右孩子都不存在，计算其wpl值
        if (!p->lchild && !p->rchild) wpl = wpl + level * p->value;
    }
    return wpl;
}

void InOrder(BiTree T) {
    //空结点
    if (!T) return;
    //叶子结点，输出data
    else if (!T->lchild && !T->rchild) cout << T->data;
    //分支节点
    else {
        //输出左括号
        cout << "(";
        //T左孩子存在，进入左孩子
        if (T->lchild) InOrder(T->lchild);
        //输出当前结点data
        cout << T->data;
        //T右孩子存在，进入右孩子
        if (T->rchild) InOrder(T->rchild);
        //输出右括号
        cout << "）";
    }
}

408数据结构学习笔记——二叉树的遍历和线索二叉树(下）

5.王道课后题