鱼C论坛

 找回密码
 立即注册
查看: 2383|回复: 0

[技术交流] 线索二叉树的c++实现代码

[复制链接]
发表于 2018-2-17 12:20:47 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
#include <iostream>
using namespace std;
typedef char ElemType;
typedef enum{Link,Thread} PointerTag;
//Link(0),Thread(1)
// 0表示存储左右孩子的指针,1表示存放前驱和后继

typedef struct BNode{
    ElemType data;
    struct BNode *lchild,*rchild;
    PointerTag rtag,ltag;//记载线索的两个位置
}BNode,*BTree;
//全局变量始终指向刚刚访问的结点

BTree pre;
//创建树,并且初始化zhizhen
void CreatBiTree(BTree *T){
    char ch;
    cin>>ch;
    if( '#' != ch)
    {
        *T=new BNode;
        (*T)->data=ch;
        (*T)->ltag=Link;
        (*T)->rtag=Link;
        CreatBiTree(&(*T)->lchild);
        CreatBiTree(&(*T)->rchild);
    }
}
//中序遍历
void InOrder(BTree T) {
    if (T)
    {
        InOrder(T->lchild);
        if (!T->lchild) //如果左孩子不存在,将左孩子线索化,指向前趋结点
        {
            T->ltag = Thread;
            T->lchild = pre;
        }
        if(!pre->rchild)//如果上一个结点的右孩子不存在,就让他指向后继结点
        {
            pre->rtag=Thread;
            pre->rchild=T;
        }
        pre=T;
        InOrder(T->rchild);
    }
}
//创建头结点,并且完成左右指针的初始化
void InOrderPre(BTree *p,BTree T){
    *p=new BNode;
    (*p)->ltag=Link;
    (*p)->rtag=Thread;//因为最后这个要指向中序遍历最后一个结点,所以先把他线索化
    //(*p)->lchild=T;
    (*p)->rchild=*p;//首先让他的右边的指针指向自己
    if(!T)
    {
        (*p)->lchild=*p;//如果是空树,左孩子也指向自己了
    }else{
        (*p)->lchild=T;
        pre=*p;//将pre变成了头指针
        InOrder(T);
        //下面是将头结点和中序遍历最后一个结点构成循环
        pre->rchild=*p;
        pre->rtag=Thread;
        (*p)->rchild=pre;
    }
}
//迭代进行中序遍历,并且打印出结果
void InOrderTraverse(BTree T){
    BTree p;
    p=T->lchild;
    while(p != T)
    {
        while(p->ltag == Link)
        {
            p=p->lchild;
        }
        cout<<p->data<<"\t";
        while(p->rtag == Thread && p->rchild != T)
        {
            p=p->rchild;
            cout<<p->data<<"\t";
        }
        p=p->rchild;
    }
}
int main(){
    BTree T;
    BTree p;
    CreatBiTree(&T);
    InOrderPre(&p,T);
    cout<<"输出中序遍历:"<<endl;
    InOrderTraverse(p);
    //InOrder( T);
    return 0;
}

本人亲自调试过了,还加了注释
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 02:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表