前序线索二叉树画法

秒速五厘米 2023-09-25 11:11 47阅读 0赞

## 先序线索二叉树和中序线索二叉树有什么区别 最好图解 ##

先序是先根节点在左结点再右结点,中序是先左,再根节点,再右结点

![前序线索二叉树画法\_java中序线索二叉树][java]

## 先序线索二叉树和中序线索二叉树有什么区别 ##

先序是先根节点在左结点再右结点，中序是先左，再根节点，再右结点

## 线索二叉树 ##

//二叉树的二叉线索存储表示

\#include

typedef enum PointerTagpointerType;//Link==0,指针,Thread==1,线索

typedef char TElemType;

typedef struct BiThrNode

TElemType data;

struct BiThrNode \*lchild,\*rchild; //左右孩子指针

pointerType LTag,RTag; //左右标志

\}BiThrNode,\*BiThrTree;

BiThrTree pre; //前驱指针

void CreateBiThrTree(BiThrTree \*T)//建树

char ch;

scanf("%c",&ch);

fflush(stdin);

if(ch==' ')

else

if(!(\*T=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(EXIT\_FAILURE);

(\*T)->data = ch;

(\*T)->lchild = (\*T)->rchild = NULL;

(\*T)->LTag = (\*T)->RTag = Link;

CreateBiThrTree(&(\*T)->lchild);

CreateBiThrTree(&(\*T)->rchild);

void InThreading(BiThrTree T) //建立线索

if(T)

InThreading(T->lchild); //左子树线索化

if(!T->lchild)//前驱线索

T->LTag = Thread; T->lchild = pre;

if(!pre->rchild)//后继线索

pre->RTag = Thread; pre->rchild = T;

pre = T;

InThreading(T->rchild);

void InOrderThreading(BiThrTree \*Thrt,BiThrTree T)//建立线索头结点

//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。

if(!(\*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(1);

(\*Thrt)->LTag = Link; //建立头结点

(\*Thrt)->RTag = Thread;

(\*Thrt)->rchild = \*Thrt; //右指针回指

if(!T) (\*Thrt)->lchild = \*Thrt; //若二叉树空,左指针也回指

else

(\*Thrt)->lchild = T; pre = \*Thrt;

InThreading(T); //进行中序线索化

pre->rchild = \*Thrt; pre->RTag = Thread; //最后一个结点线索化

(\*Thrt)->rchild = pre;

void InOrderTraverse\_Thr(BiThrTree T)//线索化中序遍历

//T指向头结点，头结点左链lchild指向根结点。

BiThrTree p;

p = T->lchild;//p指向根结点

while(p!=T)//空树或遍历结束时，p==t

while(p->LTag==Link) p = p->lchild;

//左子树为空时访问

printf("%c ",p->data);

while(p->RTag==Thread && p->rchild!=T)

p = p->rchild;

printf("%c ",p->data); //访问后继结点

p = p->rchild;

int main(void)

BiThrTree tree,treeHead;

CreateBiThrTree(&tree);

InOrderThreading(&treeHead,tree);

printf("\\nInOrderTraverse:\\n");

InOrderTraverse\_Thr(treeHead);

return 0;

this is blank

< ----这代表打空格

this is blank

a + b \* c - d - e / f

线索二叉树的遍历比较麻烦，没有把他都搞出来。上面是参考老严的代码。根结点也需要处理，根结点的前驱为空，后继为队里中的下一个元素。\#include"stdio.h"

\#include"stdlib.h"

\#include"string.h"

typedef struct threadnode \{

int ltag,rtag;

char date\[20\];

struct threadnode \*lchild, \*rchild;

\} threadnode, \*threadtree;

threadtree pre=null;

void visite(char \* ch)

printf("\\n输出节点信息:");

printf("%s",ch);

//初始化二叉树

threadtree creatthreadtree(char ch\[\])

threadtree t;

char ch1\[20\],ch2\[20\];

t=( threadtree )malloc(sizeof(threadnode));

strcpy(t->date,ch);

printf("\\n请输入左子树的数值，结束输入0:\\n");

scanf("%s",ch1);

if(strcmp(ch1,"0")==0)

t->ltag=1;

t->lchild=null;

else

\{ t->ltag=0;

t->lchild=creatthreadtree(ch1);

printf("\\n请输入右子树的数值，结束输入0:\\n");

scanf("%s",ch2);

if(strcmp(ch2,"0")==0)

t->rtag=1;

t->rchild=null;

else

\{t->rtag=0;

t->rchild=creatthreadtree(ch2);

return t;

//建立中序线索二叉树算法实现

void inthread (threadtree t)

\{ if (t)

\{ inthread(t->lchild);

if (t->lchild==null)

\{ t->ltag=1; t->lchild=pre; \}

if (t->rchild==null)

t->rtag=1;

if ((pre)&&(pre->rtag==1))

pre->rchild=t;

pre=t;

inthread (t->rchild); \}

//在中序线索二叉树上寻找结点p的中序后继结点的算法:

threadtree inpostnode(threadtree p)

\{ threadtree post;

post=p->rchild;

if (p->rtag==0)

while (post->ltag==0) post=post->lchild;

return (post);

// 在中序线索二叉树上查找值为x的结点

threadtree search (threadtree t,char x\[\] )

\{ threadtree p;

p=t;

if (p)

\{ while (p->ltag==0) p=p->lchild;

while (p&&strcmp(p->date,x)!=0)

p= inpostnode (p);

return p;

//在中序线索二叉树上寻找结点p的中序前驱结点的算法：

threadtree inprenode(threadtree p)

\{ threadtree prel;

prel=p->lchild;

if (p->ltag==0)

while (prel->rtag==0) prel= prel->rchild;

printf("\\n结点p的中序前驱结点信息！\\n");

visite(prel->date);

return(prel);

// 中序线索二叉树的遍历算法

void inorderth ( threadtree t)

\{ threadtree p;

if (t)

\{ p=t;

while (p->ltag==0) p=p->lchild;

while (p)

\{ visite(p->date);

p= inpostnode (p);

void main()

threadtree t,p;

char ch\[20\],x\[20\];

int flag=1;

while(flag)\{

printf("\\n请选择需要进行的操作:\\n");

printf("\\n1：创建二叉树\\n");

printf("\\n2：线索二叉树\\n");

printf("\\n3：中序线索二叉树\\n");

printf("\\n4：寻找结点p的中序前驱结点\\n");

printf("\\n5：寻找结点p的中序后继结点\\n");

printf("\\n6：查找值为x的结点\\n");

printf("\\n0：退出！\\n\\n");

scanf("%d",&flag);

switch(flag)\{

case 1 :

printf("\\n开始创建二叉树\\n");

printf("\\n请输入一个数值:");

scanf("%s",ch);

t=creatthreadtree(ch);

printf("\\n\\n\\n\\n\\n");break;

case 2:

printf("\\n开始线索二叉树！\\n");

inthread (t) ;break;

case 3:

printf("\\n中序线索二叉树！\\n");

inorderth ( t) ;break;

case 4://在中序线索二叉树上寻找结点p的中序前驱结点的算法：

printf("\\n输入p节点信息，以方便查找\\n");

scanf("%s",x);

printf("\\n寻找结点p的中序前驱结点!\\n");

p=search (t,x) ;

inprenode( p);

break;

case 5://在中序线索二叉树上寻找结点p的中序后继结点的算法:

printf("\\n输入p节点信息，以方便查找!\\n");

scanf("%s",x);

printf("\\n结点p的中序后继结点信息！\\n");

printf("\\n寻找结点p的中序后继结点!\\n");

p=search (t,x) ;

p=inpostnode( p);

visite(p->date);

break;

case 6:// 在中序线索二叉树上查找值为x的结点

printf("\\n请输入查找的数值！\\n");

scanf("%s",x);

p=search(t,x);

if(p) printf("\\n查找成功！\\n\\n"); else printf("\\n查找失败！\\n\\n");

break;

default:break;

if(flag!=0)

printf("\\n\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*请选择操作\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\\n");

\}二叉树的二叉线索存储表示

\#includestdio.h

![前序线索二叉树画法\_java中序线索二叉树\_02][java_02]

## 中序线索化二叉树程序 ##

\#include

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;

cin>>ch;

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;

\}inthreaded(curr->left(),pre); //这句 ，结点往左走，pre还不变吗？还能这样写吗？

这个是递归调用本函数，如果不为空，有节点，就顺左子树的线路往下找，pre指向该节点本身的前驱节点(也就是左孩子)

if(pre==null) curr->lth()=1; //置线索 是curr->left()为空才置1吧？跟pre==null有什么关系？

这个pre==null是看该节点是不是叶子节点，要是按你说的curr->left()为空才置1，那curr->right呢？不就错了

我也是刚学的数据结构，不过我看的书的线索二叉树是 如果该节点没有左孩子，则空出来的指针域指向其前驱(都是中序遍历)，没有又孩子，则指向其后继，你这个看起来有点怪， 我也正在学，说的也不一定对

[java]: https://img-blog.csdnimg.cn/img_convert/1a81cefcc867914e2ca15eee347047a4.jpeg
[java_02]: https://img-blog.csdnimg.cn/img_convert/58a88fa9688593eaddd95ff1cdea4618.png

前序线索二叉树画法

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 C语言——线索二叉树（前序、中序、后序-附代码）

相关前序线索二叉树画法

相关中序线索二叉树

相关前序、中序、后序线索化二叉树

相关中序线索二叉树

相关数据结构-线索二叉树（中序线索二叉树及遍历）

相关数据结构-线索二叉树（后序线索二叉树及遍历）

相关数据结构-线索二叉树（先序线索二叉树及遍历）

相关线索二叉树原理及前序、中序线索化（Java实现）

相关线索二叉树（中序创建）