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

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

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

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

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

  线索二叉树

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

  #

  #

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

   char ;

   struct

   data;

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

   LTag,RTag; //左右标志

  },*;

   pre; //前驱指针

  void ( *T)//建树

  char ch;

  scanf("%c",&ch);

  fflush(stdin);

  if(ch==' ')

  else

  {

  if(!(*T=()malloc(sizeof()))) exit();

  (*T)->data = ch;

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

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

  (&(*T)->lchild);

  (&(*T)->rchild);

  }

  void ( T) //建立线索

  if(T)

  {

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

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

  {

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

  }

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

  {

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

  }

  pre = T;

  (T->rchild);

  }

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

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

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

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

  (*Thrt)->RTag = Thread;

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

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

  else

  {

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

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

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

  (*Thrt)->rchild = pre;

  }

  void ( T)//线索化中序遍历

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

   p;

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

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

  {

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

  //左子树为空时访问

  [printf]2;

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

  {

  p = p->rchild;

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

  }

  p = p->rchild;

  }

  int main(void)

   tree,;

  (&tree);

  (&,tree);

  printf("\:\n");

  ();

  return 0;

  this is blank

  this is blank

  this is blank

  this is blank

  < ----这代表打空格

  this is blank

  this is blank

  this is blank

  this is blank

  this is blank

  this is blank

  this is blank

  this is blank

  a + b * c - d - e / f

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

  #"stdlib.h"

  #"string.h"

   struct {

  int ltag,rtag;

  char date[20];

  struct lchild, rchild;

  } , *;

   pre=null;

  void visite(char * ch)

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

  printf("%s",ch);

  //初始化二叉树

   (char ch[])

   t;

  char ch1[20],ch2[20];

  t=( )malloc(sizeof());

  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=(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=(ch2);

  return t;

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

  void ( t)

  { if (t)

  { (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;

   (t->rchild); }

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

   ( p)

  { post;

  post=p->rchild;

  if (p->rtag==0)

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

  return (post);

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

   search ( t,char x[] )

  { p;

  p=t;

  if (p)

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

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

  p= (p);

  return p;

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

   ( p)

  { 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 ( t)

  { p;

  if (t)

  { p=t;

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

  while (p)

  { visite(p->date);

  p= (p);

  void main()

   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=(ch);

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

  case 2:

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

   (t) ;break;

  case 3:

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

   ( t) ;break;

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

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

  scanf("%s",x);

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

  p=search (t,x) ;

  ( 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=( 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;

  :break;

  if(flag!=0)

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

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

  #.h

  中序线索化二叉树程序

  #

   char ;

   enum{ Link , Thread } ;

   struct node{

   data;

   ,;

  struct node , ;

  },*;

  //先序创建线索二叉树

  void reate( &T)

  char ch;

  cin>>ch;

  if(ch!='*')

  T=new ;

  T->data=ch;

  T->=T->=Link;

  T->=NULL;

  T->=NULL;

  reate(T->);

  reate(T->);

  else T=NULL;

  //中序线索化二叉树

  void ( p, &pre)

  if(p)

  (p->,pre);

  if(p->==NULL)

  p->=pre;

  p->=Thread;

  if(pre->==NULL)

  pre->=p;

  pre->=Thread;

  pre=p;

  (p->,pre);

  void ( &T, &head)

  head=new ;

  head->=Link;

  head->=Thread;

  head->=head;

  if(T==NULL)head->=head;

  else

  head->=T;

   pre;

  pre=head;

  (T,pre);

  pre->=head;

  pre->=Thread;

  head->=pre;

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

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

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

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

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

本文共 940 个字数,平均阅读时长 ≈ 3分钟