备案控制台
探索云世界
开发者社区 人工智能 文章 正文

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

2022-11-24 81
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 408数据结构学习笔记——二叉树的遍历和线索二叉树

5.王道课后题

5a668bd3807a45d3afa52d2ba7a16cbb.png

每层只有一个节点

248a9612792645838753bd320c84f25c.png

只有根节点

99c202742f28411daa7506ddd87f691f.png

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
}

714e0508955840d0ad432f9281c13e3c.png

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);
    }
}

9675d4b79dd746ad8d1464b0af52090b.png

//非递归方式
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;
    }
}

2f34357c2a0a41a09b4502cc73b49da1.png

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;
}

cd62f16868ba4288a7c8890dedf25842.png

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;
}

d285097e033f4223b23be6a4579ca055.png

//递归实现
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;
}

e03f09df1ade4974b4c82e700eeebb34.png

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;
}

eee6acda314b4bc183fa98dc61ec0323.png

//递归    
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
}

343a35e65484427d8c17bcb82c27b77e.png

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

遍历树并查找值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     
}

6179b7c455da46c79c530ce3ad437343.png

使用先序遍历的特性（根左右的访问顺序），如果当前结点的值为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
}

0f14e68abe634a498225e2c9ea5e5bb4.png

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

#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;
}

45ad241a625e4adcba9c60dd7b5061cf.png

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;
}

c78e5c7b15874eff9fbb7368f4e6d70e.png

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

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

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

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);
    }
}

a955d4759e1a44538ca3f232ced24af7.png

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

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;
}

65f184e0ebb64947918ec2fd23ebb16f.png

//层次遍历，非递归
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;
    }
}

2ebaead5d6f044f987ef438ae9038781.png

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;
}

5d3e6d4d688240fcbdbbe633134f2b1c.png

//层次遍历
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;
}

68fdf788c78b48689ad062c25f347146.png

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 << "）";
    }
}
文章标签：
云数据库 ClickHouse
算法
关键词：
数据结构二叉树
数据结构遍历
数据结构二叉树的遍历
数据结构线索二叉树
数据结构线索
gbip7sii3jwms
目录
相关文章
阿森要自信
|
22天前
|
算法
【算法与数据结构】二叉树（前中后）序遍历2
【算法与数据结构】二叉树（前中后）序遍历
阿森要自信
18 0
筱姌
|
7天前
二叉树和数据结构
二叉树和数据结构
筱姌
16 0
认真学习的小雅兰.
|
8天前
|
算法 DataX
二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
认真学习的小雅兰.
8 0
阿森要自信
|
18天前
|
算法 索引
【算法与数据结构】深入二叉树实现超详解（全源码优化）
【算法与数据结构】深入二叉树实现超详解（全源码优化）
阿森要自信
29 1
阿森要自信
|
18天前
|
存储 算法
【算法与数据结构】深入解析二叉树（二）之堆结构实现
【算法与数据结构】深入解析二叉树（二）之堆结构实现
阿森要自信
24 1
快乐的流畅
|
29天前
|
存储 算法 程序员
【数据结构】【版本2.0】【树形深渊】——二叉树入侵
【数据结构】【版本2.0】【树形深渊】——二叉树入侵
快乐的流畅
70 2
泡沫o0
|
30天前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质：具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
【C/C++ 数据结构 】二叉树基本性质：具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
泡沫o0
11 0
Kevin_17
|
17天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列（二）：队列
深入理解栈和队列（二）：队列
Kevin_17
29 0
起飞的风筝
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现
起飞的风筝
32 0
诡异森林。
|
1月前
|
存储
数据结构--栈和队列
数据结构--栈和队列
诡异森林。
34 1

热门文章

最新文章

  • 1
    数据结构期末复习（fengkao课堂）
  • 2
    【C/C++ 数据结构 】从零开始实现哈希表：C++实践指南
  • 3
    Java数据结构与算法-java数据结构与算法（二）
  • 4
    【数据结构】【版本2.0】【树形深渊】——二叉树入侵
  • 5
    【C/C++ 数据结构 树】探索C/C++中的二叉树：从理论到实践
  • 6
    【C/C++ 数据结构 线性表】深入理解与实现栈：从基础到应用的全面探索
  • 7
    数据结构-概念版（七）
  • 8
    Java数据结构与算法-java数据结构与算法（五）
  • 9
    【C/C++ 数据结构】深入探索数据结构中算法复杂度：从C++和数学的视角
  • 10
    python学习-函数模块，数据结构，字符串和列表（下）
  • 1
    【手撕数据结构】二分查找(好多细节)
    16
  • 2
    【数据结构与算法】—— 手撕红黑树
    36
  • 3
    【排序算法】数据结构排序详解
    42
  • 4
    【链式二叉树】数据结构链式二叉树的（万字详解）
    42
  • 5
    【堆】数据结构堆的实现（万字详解）
    52
  • 6
    【树和二叉树】数据结构二叉树和树的概念认识
    25
  • 7
    【双向链表】数据结构双向链表的实现
    21
  • 8
    数据结构——单链表的基本操作
    11
  • 9
    数据结构——排序算法之快速排序
    33
  • 10
    数据结构——二叉树的链式结构
    36

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）