中序线索二叉树加注释 在线急等

来源:百度知道 编辑:UC知道 时间:2024/05/07 06:46:35
#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
typedef enum{Link,Thread} PointerTag;
typedef struct node{
DataType data;
PointerTag ltag,rtag;
struct node * lchild,* rchild;
}BinTNode;
typedef BinTNode *BinTree;
BinTNode *pre=NULL;

void CreateBinTree(BinTree *T)
{
char ch;
if((ch=getchar())==' ')
*T=NULL;
else{
*T=(BinTNode*)malloc(sizeof(BinTNode));
(*T)->data=ch;
CreateBinTree(&(*T)->lchild);
CreateBinTree(&(*T)->rchild);

}

}

void InorderThreading(BinTree p)
{
if(p)
{
InorderThreading(p->lchild);
p->ltag=(p->lchild)? Link:Thread;
p->rtag=(p->rchild)? Link:Thread;
if(pre)
{
if(pre->rtag==Thread)
pre->rchild=p;
if(p->ltag==Thread)
p->lchild=pre;
}
pre=p;

#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
typedef enum{Link,Thread} PointerTag; //指针域是孩子还是线索的标志
typedef struct node{
DataType data; //数据域
PointerTag ltag,rtag; //指针域信息的标志
struct node * lchild,* rchild; //指针域

}BinTNode; //线索树结点
typedef BinTNode *BinTree;
BinTNode *pre=NULL; //前驱指针

void CreateBinTree(BinTree *T) //按前序建立二叉树,数据按前序输入
{
char ch;
if((ch=getchar())==' ')
*T=NULL;
else{
*T=(BinTNode*)malloc(sizeof(BinTNode));
(*T)->data=ch;
CreateBinTree(&(*T)->lchild);
CreateBinTree(&(*T)->rchild);

}

}

void InorderThreading(BinTree p) //递归函数,建立中序线索信息.注意这里有两个指针p和pre,其中pre指向p的前驱结点
{
if(p)
{
InorderThreading(p->lchild);
p->ltag=(p->lchild)? Link:Thread;
p->rtag=(p->rchild)? Link:Thread;
if(pre)
{
if(pre->rtag==Thread) <