AI 助理
备案控制台
开发者社区 人工智能 文章 正文

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

2022-11-24 114
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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
目录
相关文章
RossyYan
|
8天前
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
34 12
RossyYan
|
8天前
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
33 10
RossyYan
|
9天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
31 2
三三是该溜子
|
22天前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
34 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
RossyYan
|
8天前
|
数据采集 存储 算法
【C++数据结构——图】图的遍历（头歌教学实验平台习题） 【合集】
本文介绍了图的遍历算法，包括深度优先遍历（DFS）和广度优先遍历（BFS）。深度优先遍历通过递归方式从起始节点深入探索图，适用于寻找路径、拓扑排序等场景；广度优先遍历则按层次逐层访问节点，适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例，演示了如何实现这两种遍历方法，并附有测试用例及结果，帮助读者理解和实践图的遍历算法。
RossyYan
24 0
XIAZHI
|
2月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法，包括先序、中序、后序的递归与非递归遍历方法。通过编程实践，加深对二叉树结构的理解，学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
XIAZHI
110 4
ephemerals__
|
2月前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
168 8
ephemerals__
|
2月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
281 9
那年春天
|
2月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
43 1
RossyYan
|
8天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
125 75

热门文章

最新文章

  • 1
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
  • 2
    局域网屏幕监控系统中的Python数据结构与算法实现
  • 3
    【C++数据结构——查找】二分查找（头歌实践教学平台习题）【合集】
  • 4
    Pandas数据结构：Series与DataFrame
  • 5
    探索局域网电脑监控软件：Python算法与数据结构的巧妙结合
  • 6
    【C++数据结构——树】哈夫曼树（头歌实践教学平台习题） 【合集】
  • 7
    【C++数据结构——图】最短路径（头歌教学实验平台习题） 【合集】
  • 8
    【C++数据结构——内排序】希尔排序（头歌实践教学平台习题）【合集】
  • 9
    【C++数据结构——查找】二叉排序树（头歌实践教学平台习题）【合集】
  • 10
    【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
  • 1
    Python 数据结构和算法实用指南（四）（4）
    306
  • 2
    Python 数据结构和算法实用指南（四）（3）
    48
  • 3
    Python 数据结构和算法实用指南（四）（2）
    32
  • 4
    Python 数据结构和算法实用指南（三）（3）
    34
  • 5
    Python 数据结构和算法实用指南（三）（1）
    42
  • 6
    Python 数据结构和算法实用指南（二）（4）
    41
  • 7
    Python 数据结构和算法实用指南（二）（3）
    45
  • 8
    Python 数据结构和算法实用指南（二）（2）
    28
  • 9
    Python 数据结构和算法实用指南（一）（2）
    42
  • 10
    【Python进阶（七）】——Series数据结构
    198

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    DataWorks智能交互式数据开发与分析之旅