二叉树的建立遍历以及线索化二叉树
需积分: 14 146 浏览量
2010-04-23
10:24:07
上传
评论 2
收藏 36KB DOC 举报
#include"stdio.h"
#include"malloc.h"
#include"math.h"
#dene NULL 0
#dene MAX 100
//定义二叉树结点类型
typedef int datatype; //线索二叉树数据为整型
typedef struct node //线索二叉树的结点类型
{int ltag,rtag; //左线索和右线索为整型
datatype data;
struct node *lchild,*rchild; //左孩子、右孩子
}bithptr;
bithptr *pre; //全程量*pre
//建立二叉树
bithptr *Q[MAX]; //队列 Q 为 bithptr 指针类型的数组，下面算法使用下标 1 到 n
的元素
bithptr *CREATREE() //建立二叉树，函数值返回指向根的指针
{
char ch;
int front,rear; //队头和队尾指针
bithptr *root,*s;
root=NULL; //置空二叉树
front=1;
rear=0; //置空队列
ch=getchar(); //从键盘输入二叉树的结点数据
while(ch!='#') //#作为结束符号
{
s=NULL;
if(ch!='@') //@表示虚节点，不是虚节点是建立新节点
{
s=(bithptr *)malloc(sizeof(bithptr)); //申请新节点地址空间
s->data=ch; //数据域是输入的字符
s->lchild =NULL;
s->rchild =NULL;
s->ltag=0;
s->rtag=0;
}
rear++; //队尾加 1
Q[rear]=s; //将新节点指针 NULL 或新节点地址入队
if(rear==1) root=s; //输入的第一个节点做为根节点
else
评论0
最新资源