正文
java线索化二叉树代码 线索化二叉树流程图
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
有谁知道二叉树线索化的完整代码？
复制java线索化二叉树代码，保存为.C文件即可。
/* bo6-3.c 二叉树java线索化二叉树代码的二叉线索存储(存储结构由c6-3.h定义)的基本操作，包括算法6.5～6.7 */
void CreateBiThrTree(BiThrTree *T)
{ /* 按先序输入线索二叉树中结点的值，构造线索二叉树T。0(整型)/空格(字符型)表示空结点 */
TElemType ch;
scanf(form,ch);
if(ch==Nil)
*T=NULL;
else
{
*T=(BiThrTree)malloc(sizeof(BiThrNode)); /* 生成根结点(先序) */
if(!*T)
exit(OVERFLOW);
(*T)-data=ch; /* 给根结点赋植 */
CreateBiThrTree((*T)-lchild); /* 递归构造左子树 */
if((*T)-lchild) /* 有左孩子 */
(*T)-LTag=Link; /* 给左标志赋值(指针) */
CreateBiThrTree((*T)-rchild); /* 递归构造右子树 */
if((*T)-rchild) /* 有右孩子 */
(*T)-RTag=Link; /* 给右标志赋值(指针) */
}
}
BiThrTree pre; /* 全局变量，始终指向刚刚访问过的结点 */
void InThreading(BiThrTree p)
{ /* 通过中序遍历进行中序线索化，线索化之后pre指向最后一个结点。算法6.7 */
if(p) /* 线索二叉树不空 */
{
InThreading(p-lchild); /* 递归左子树线索化 */
if(!p-lchild) /* 没有左孩子 */
{
p-LTag=Thread; /* 左标志为线索(前驱) */
p-lchild=pre; /* 左孩子指针指向前驱 */
}
if(!pre-rchild) /* 前驱没有右孩子 */
{
pre-RTag=Thread; /* 前驱的右标志为线索(后继) */
pre-rchild=p; /* 前驱右孩子指针指向其后继(当前结点p) */
}
pre=p; /* 保持pre指向p的前驱 */
InThreading(p-rchild); /* 递归右子树线索化 */
}
}
void InOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ /* 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。算法6.6 */
*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!*Thrt) /* 生成头结点不成功 */
exit(OVERFLOW);
(*Thrt)-LTag=Link; /* 建头结点，左标志为指针 */
(*Thrt)-RTag=Thread; /* 右标志为线索 */
(*Thrt)-rchild=*Thrt; /* 右指针回指 */
if(!T) /* 若二叉树空，则左指针回指 */
(*Thrt)-lchild=*Thrt;
else
{
(*Thrt)-lchild=T; /* 头结点的左指针指向根结点 */
pre=*Thrt; /* pre(前驱)的初值指向头结点 */
InThreading(T); /* 中序遍历进行中序线索化，pre指向中序遍历的最后一个结点 */
pre-rchild=*Thrt; /* 最后一个结点的右指针指向头结点 */
pre-RTag=Thread; /* 最后一个结点的右标志为线索 */
(*Thrt)-rchild=pre; /* 头结点的右指针指向中序遍历的最后一个结点 */
}
}
void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType))
{ /* 中序遍历线索二叉树T(头结点)的非递归算法。算法6.5 */
BiThrTree p;
p=T-lchild; /* p指向根结点 */
while(p!=T)
{ /* 空树或遍历结束时，p==T */
while(p-LTag==Link) /* 由根结点一直找到二叉树的最左结点 */
p=p-lchild;
Visit(p-data); /* 访问此结点 */
while(p-RTag==Threadp-rchild!=T) /* p-rchild是线索(后继)，且不是遍历的最后一个结点 */
{
p=p-rchild;
Visit(p-data); /* 访问后继结点 */
}
p=p-rchild; /* 若p-rchild不是线索(是右孩子)，p指向右孩子，返回循环，*/
} /* 找这棵子树中序遍历的第1个结点 */
}
void PreThreading(BiThrTree p)
{ /* PreOrderThreading()调用的递归函数 */
if(!pre-rchild) /* p的前驱没有右孩子 */
{
pre-rchild=p; /* p前驱的后继指向p */
pre-RTag=Thread; /* pre的右孩子为线索 */
}
if(!p-lchild) /* p没有左孩子 */
{
p-LTag=Thread; /* p的左孩子为线索 */
p-lchild=pre; /* p的左孩子指向前驱 */
}
pre=p; /* 移动前驱 */
if(p-LTag==Link) /* p有左孩子 */
PreThreading(p-lchild); /* 对p的左孩子递归调用preThreading() */
if(p-RTag==Link) /* p有右孩子 */
PreThreading(p-rchild); /* 对p的右孩子递归调用preThreading() */
}
void PreOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ /* 先序线索化二叉树T，头结点的右指针指向先序遍历的最后1个结点 */
*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!*Thrt) /* 生成头结点 */
exit(OVERFLOW);
(*Thrt)-LTag=Link; /* 头结点的左指针为孩子 */
(*Thrt)-RTag=Thread; /* 头结点的右指针为线索 */
(*Thrt)-rchild=*Thrt; /* 头结点的右指针指向自身 */
if(!T) /* 空树 */
(*Thrt)-lchild=*Thrt; /* 头结点的左指针也指向自身 */
else
{ /* 非空树 */
(*Thrt)-lchild=T; /* 头结点的左指针指向根结点 */
pre=*Thrt; /* 前驱为头结点 */
PreThreading(T); /* 从头结点开始先序递归线索化 */
pre-rchild=*Thrt; /* 最后一个结点的后继指向头结点 */
pre-RTag=Thread;
(*Thrt)-rchild=pre; /* 头结点的后继指向最后一个结点 */
}
}
void PreOrderTraverse_Thr(BiThrTree T,void(*Visit)(TElemType))
{ /* 先序遍历线索二叉树T(头结点)的非递归算法 */
BiThrTree p=T-lchild; /* p指向根结点 */
while(p!=T) /* p没指向头结点(遍历的最后1个结点的后继指向头结点) */
{
Visit(p-data); /* 访问根结点 */
if(p-LTag==Link) /* p有左孩子 */
p=p-lchild; /* p指向左孩子(后继) */
else /* p无左孩子 */
p=p-rchild; /* p指向右孩子或后继 */
}
}
void PostThreading(BiThrTree p)
{ /* PostOrderThreading()调用的递归函数 */
if(p) /* p不空 */
{
PostThreading(p-lchild); /* 对p的左孩子递归调用PostThreading() */
PostThreading(p-rchild); /* 对p的右孩子递归调用PostThreading() */
if(!p-lchild) /* p没有左孩子 */
{
p-LTag=Thread; /* p的左孩子为线索 */
p-lchild=pre; /* p的左孩子指向前驱 */
}
if(!pre-rchild) /* p的前驱没有右孩子 */
{
pre-RTag=Thread; /* p前驱的右孩子为线索 */
pre-rchild=p; /* p前驱的后继指向p */
}
pre=p; /* 移动前驱 */
}
}
void PostOrderThreading(BiThrTree *Thrt,BiThrTree T)
{ /* 后序递归线索化二叉树 */
*Thrt=(BiThrTree)malloc(sizeof(BiThrNode));
if(!*Thrt) /* 生成头结点 */
exit(OVERFLOW);
(*Thrt)-LTag=Link; /* 头结点的左指针为孩子 */
(*Thrt)-RTag=Thread; /* 头结点的右指针为线索 */
if(!T) /* 空树 */
(*Thrt)-lchild=(*Thrt)-rchild=*Thrt; /* 头结点的左右指针指向自身 */
else
{ /* 非空树 */
(*Thrt)-lchild=(*Thrt)-rchild=T; /* 头结点的左右指针指向根结点(最后一个结点) */
pre=*Thrt; /* 前驱为头结点 */
PostThreading(T); /* 从头结点开始后序递归线索化 */
if(pre-RTag!=Link) /* 最后一个结点没有右孩子 */
{
pre-rchild=*Thrt; /* 最后一个结点的后继指向头结点 */
pre-RTag=Thread;
}
}
}
void DestroyBiTree(BiThrTree *T)
{ /* DestroyBiThrTree调用的递归函数，T指向根结点 */
if(*T) /* 非空树 */
{
if((*T)-LTag==0) /* 有左孩子 */
DestroyBiTree((*T)-lchild); /* 销毁左孩子子树 */
if((*T)-RTag==0) /* 有右孩子 */
DestroyBiTree((*T)-rchild); /* 销毁右孩子子树 */
free(*T); /* 释放根结点 */
T=NULL; /* 空指针赋0 */
}
}
void DestroyBiThrTree(BiThrTree *Thrt)
{ /* 初始条件：线索二叉树Thrt存在。操作结果：销毁线索二叉树Thrt */
if(*Thrt) /* 头结点存在 */
{
if((*Thrt)-lchild) /* 根结点存在 */
DestroyBiTree((*Thrt)-lchild); /* 递归销毁头结点lchild所指二叉树 */
free(*Thrt); /* 释放头结点 */
*Thrt=NULL; /* 线索二叉树Thrt指针赋0 */
}
}
相关问答
Q1: “先序线索化” //递归出错，同样的方式实现中序、后序线索化二叉树却是正确的，代码如下 //先序遍历线索
//给java线索化二叉树代码你两个代码 一个错误用于启示 一个正确却需要理解-也就是你java线索化二叉树代码的正确改版
//错误版本java线索化二叉树代码：
//看下面这个结果与你的相反 而且还要返回最后一个 正确的看下一个改版！！！！
//但你可以从这个错误中得到启示！！！！ 只是顺序相反了罢了 想法改过来就得
ThreadNode* PreOrderThread(ThreadTree bt)
{
static ThreadNode* pre=NULL;
if(bt != NULL) //只有不是NULL才是递归条件啊 没个结点都到这来检测是否为NULL
{
bt-lChild = pre; //bt永远指向pre 这样就构成了线索了 不过这样跟结点在最后罢了
pre = bt; //然后pre也该改变到了新的位置了 如此重复
//上面两句是 根遍历
PreOrderThread(bt-lchild); // 左子树遍历
PreOrderThread(bt-rchild); // 右子树遍历
// 一看就是先序线索了吗？根-左(根左右)-右(根左右)
}
return pre; //返回最后一个线索的结点 也就是最右边的结点 否则怎么知道呢
}
正确改版：
//由于方向相反了 我们就“右-左-根”的遍历 最后一个就是根了 也不用返回了
// 不就一切OK了
void PreOrderThread(ThreadTree bt)
{
static ThreadNode* pre=NULL;
if(bt != NULL) //只有不是NULL才是递归条件啊 没个结点都到这来检测是否为NULL
{
PreOrderThread(bt-rchild); // 右子树遍历
PreOrderThread(bt-lchild); // 左子树遍历
bt-lChild = pre; // 根遍历
pre = bt;
//怎么 没明白 呵呵 拿笔纸上写写看就明白了
//你想啊
//(1)只有根 正确
//(2)2个结点的(有根左或者有根右 两种情况) 都正确吧
//(3)3个结点(有根左右) 正确吧
//(4)现在多于3个结点的 归纳到(1)-(3) 呵呵 可以利用数学上的归纳法证明呀
//哈哈 扯淡到数学去了 反正就是这种简单的做法
}
}
就这么简单 就怕理解不了 而扯淡出一大堆代码 就像我上面的 有返回 费解易错
这和只遍历而不改变树是一个道理的
理解的话
其他的线索化 代码也这么简单 没什么的！！！
Q2: 中序线索化二叉树程序
#include iostream.h
typedef char elemtype ;
typedef enum{ Link , Thread } PointerTag;
typedef struct node{
elemtype data;
PointerTag leftChildTag,rightChildTag;
struct node *leftChild, *rightChild;
}ThreadBitreeNode,*ThreadBitree;
//先序创建线索二叉树
void InOrderThreadBitreeCreate(ThreadBitree T)
{
char ch;
cinch;
if(ch!='*')
{
T=new ThreadBitreeNode;
T-data=ch;
T-leftChildTag=T-rightChildTag=Link;
T-leftChild=NULL;
T-rightChild=NULL;
InOrderThreadBitreeCreate(T-leftChild);
InOrderThreadBitreeCreate(T-rightChild);
}
else T=NULL;
}
//中序线索化二叉树
void Threading(ThreadBitree p,ThreadBitree pre)
{
if(p)
{
Threading(p-leftChild,pre);
if(p-leftChild==NULL)
{
p-leftChild=pre;
p-leftChildTag=Thread;
}
if(pre-rightChild==NULL)
{
pre-rightChild=p;
pre-rightChildTag=Thread;
}
pre=p;
Threading(p-rightChild,pre);
}
}
void InOrderThread(ThreadBitree T,ThreadBitree head)
{
head=new ThreadBitreeNode;
head-leftChildTag=Link;
head-rightChildTag=Thread;
head-rightChild=head;
if(T==NULL)head-leftChild=head;
else
{
head-leftChild=T;
ThreadBitree pre;
pre=head;
Threading(T,pre);
pre-rightChild=head;
pre-rightChildTag=Thread;
head-rightChild=pre;
}
}
Q3: 求程序：线索二叉树插入删除运算
#include stdio.h
#include "malloc.h"
#include "windows.h"
#define maxsize 20 //规定树中结点的最大数目
typedef struct node{ //定义数据结构
int ltag,rtag; //表示child域指示该结点是否孩子
char data; //记录结点的数据
struct node *lchild,*rchild; //记录左右孩子的指针
}Bithptr;
Bithptr *Q[maxsize]; //建队java线索化二叉树代码，保存已输入的结点的地址
Bithptr *CreatTree(){ //建树函数，返回根指针
char ch;
int front,rear;
Bithptr *T,*s;
T=NULL;
front=1;rear=0; //置空二叉树
printf("建立一棵二叉树，请输入结点信息java线索化二叉树代码：\n");
printf("请输入新的结点信息，@为空结点，#为结束标志：");
ch=getchar(); //输入第一个字符
while(ch!='#') //判断是否为结束字符
{
s=NULL;
if(ch!='@') //判断是否为虚结点
{
s=(Bithptr *)malloc(sizeof(Bithptr));
s-data=ch;
s-lchild=NULL;
s-rchild=NULL;
s-rtag=0;
s-ltag=0;
}
rear++;
Q[rear]=s; //将结点地址加入队列中
if(rear==1)T=s; //输入为第一个结点为根结点
else
{
if(s!=NULLQ[front]!=NULL) //孩子和双亲结点均不是虚结点
if(rear%2==0)
Q[front]-lchild=s;
else Q[front]-rchild=s;
if(rear%2==1)front++;
}getchar();
printf("请输入新的结点信息，@为空结点，#为结束标志：");
ch=getchar();
}
return T;
}
void Inorder(Bithptr *T) //中序遍历
{
if(T)
{
if(T-ltag!=1)Inorder(T-lchild);
printf("→%c",T-data);
if(T-rtag!=1)Inorder(T-rchild);
}
}
Bithptr *pre=NULL;
void PreThread(Bithptr *root) //中序线索化算法，函数实现
{
Bithptr *p;
p=root;
if(p){
PreThread(p-lchild);//线索化左子树
if(prepre-rtag==1)pre-rchild=p; //前驱结点后继线索化
if(p-lchild==NULL)
{
p-ltag=1;
p-lchild=pre;
}
if(p-rchild==NULL) //后继结点前驱线索化
p-rtag=1;
pre=p;
PreThread(p-rchild);
}
}
void PrintIndex(Bithptr *t) //输出线索
{
Bithptr *f;
f=t;
if(f)
{
if(f-ltag==1f-lchild==NULLf-rtag==1) printf("【%c】",f-data); //如果是第一个结点
if(f-ltag==1f-lchild!=NULL) printf("%c→【%c】",f-lchild-data,f-data); //如果此结点有前驱就输出前驱和此结点
if(f-ltag==1f-rtag==1f-rchild!=NULL) printf("→%c",f-rchild-data); //如果此结点有前驱也有后继，就输出后继
else if(f-rtag==1f-rchild!=NULL) printf("【%c】→%c",f-data,f-rchild-data);//如果没有前驱，就输出此结点和后继
printf("\n");
if(f-ltag!=1)PrintIndex(f-lchild);
if(f-rtag!=1)PrintIndex(f-rchild);
}
}
Bithptr *SearchChild(Bithptr *point,char findnode) //查找孩子结点函数
{
Bithptr *point1,*point2;
if(point!=NULL)
{
if(point-data==findnode) return point;
else
if(point-ltag!=1) { point1=SearchChild(point-lchild,findnode); if(point1!=NULL)return point1;}
if(point-rtag!=1) { point2=SearchChild(point-rchild,findnode); if(point2!=NULL)return point2;}
return NULL;
}
else
return NULL;
}
Bithptr *SearchPre(Bithptr *point,Bithptr *child) //查找父亲结点函数
{
Bithptr *point1,*point2;
if(point!=NULL)
{
if((point-ltag!=1point-lchild==child)||(point-rtag!=1point-rchild==child)) return point;//找到则返回
else
if(point-ltag!=1)
{
point1=SearchPre(point-lchild,child);
if(point1!=NULL)
return point1;
}
if(point-rtag!=1)
{
point2=SearchPre(point-rchild,child);
if(point2!=NULL)
return point2;
}
return NULL;
}
else
return NULL;
}
void Insert(Bithptr *root)
{
char ch;
char c;
Bithptr *p1,*child,*p2;
printf("请输入要插入的结点的信息:");
scanf("%c",c);
scanf("%c",c);
p1=(Bithptr *)malloc(sizeof(Bithptr)); //插入的结点信息
p1-data=c;
p1-lchild=NULL;
p1-rchild=NULL;
p1-rtag=0;
p1-ltag=0;
printf("输入查找的结点信息:");
scanf("%c",ch);
scanf("%c",ch);
child=SearchChild(root,ch); //查孩子结点的地址
if(child==NULL){
printf("没有找到结点\n");
system("pause");
return ;
}
else printf("发现结点%c\n",child-data);
if(child-ltag==0) //当孩子结点有左孩子的时候
{
p2=child;
child=child-lchild;
while(child-rchildchild-rtag==0) //找到左子树下，最右结点
child=child-rchild;
printf("发现结点%c\n",child-data);
p1-rchild=child-rchild; //后继化
p1-rtag=1;
child-rtag=0;
child-rchild=p1; //连接
p1-lchild=child; //前驱化
p1-ltag=1;
}
else //当孩子结点没有左孩子的时候
{
p1-lchild=child-lchild; //前驱化
child-ltag=0;
p1-ltag=1;
child-lchild=p1;
p1-rchild=child;
p1-rtag=1;
}
printf("\t插入结点操作已经完成，并同时完成java线索化二叉树代码了线索化的恢复\n");
}
关于java线索化二叉树代码和线索化二叉树流程图的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
