2020-11-19 三叉链表的构建以及利用mark实现三叉链表后序遍历（不用栈）

题目6.39：

题目里面注明了mark如何使用，也让我学习到了一定的知识

//利用mark(0:继续向左 1:向右 2:访问并回到双亲)的三叉链表的后序遍历（不用栈）
#include<iostream>
using namespace std;
#define TElemType double
typedef struct BiTNode
{
    TElemType data;
    int mark;//标志变量0:继续向左 1:向右 2:访问该结点
    struct BiTNode* lchild,* rchild,* parent;//在二叉链表的基础上+parent构成三叉链表
}BiTNode,* BiTree;

void Creat_BiTree(BiTree& T,BiTree parent)//在原来创建二叉树的情况下设置双亲指针的值
//递归构建三叉链表是在递归构建二叉链表的基础上
//parent存放 指向T的双亲结点 的指针，若为根结点，则parent为nullptr
{
    TElemType num;
    if(cin>>num){
        T=new BiTNode;
        if(!T) exit(-2);
        T->data=num;
        T->parent=parent;//设置双亲
        T->mark=0;//新开辟的结点的mark设为0
        Creat_BiTree(T->lchild,T);
        Creat_BiTree(T->rchild,T);
    }
    if(!cin){
        T=nullptr;
        if(parent)//为了后序遍历
            parent->mark++;//每有一个孩子(即T)为空，则parent的mark++
        cin.clear();
        cin.sync();
    }
}

void PreOrder_BiTree(BiTree T)//先序遍历打印三叉链表每个结点的mark值
{
    if(T){
        cout<<T->mark<<endl;
        PreOrder_BiTree(T->lchild);
        PreOrder_BiTree(T->rchild);
    }
}
void PostOrder_BiTree(BiTree T)//利用mark对三叉链表进行后序遍历
{
    BiTree p=T;
    while(p){//当p为空结束循环
        while(p->mark==0){//0：继续向左  “继续”体现了循环，所以用while
            p->mark++;
            p=p->lchild;
        }
        if(p->mark==1){//1：向右
            p->mark++;
            p=p->rchild;
        }
        if(p->mark==2){//2：访问并回到双亲结点
            cout<<p->data<<endl;
            p=p->parent;
        }
    }
}

int main()
{
    BiTree T;
    Creat_BiTree(T,nullptr);//根结点的双亲为空
    cout<<"检验mark值:\n";
    PreOrder_BiTree(T);//带mark的三叉链表构建完成后，检验每个结点的mark值
    cout<<"检验完成\n";
    PostOrder_BiTree(T);
    return 0;
}

1
2
4
@
7
3
@
@
4
@
@
5
@
@
3
@
@
检验mark值:
0
0
1
0
2
2
2
2
检验完成
3
4
7
4
5
2
3
1

Process returned 0 (0x0)   execution time : 4.365 s
Press any key to continue.