crethrtr.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

#include<stdio.h>
#include<stdlib.h>
#define NULL 0
typedef char datatype;
typedef struct node            /*二叉树结点定义*/
 {
  datatype data;
  int ltag,rtag;
  struct node *lchild,*rchild;
  }binthrnode;
typedef binthrnode *binthrtree;


binthrtree pre=NULL; /*初始化前驱结点*/
void createbintree(binthrtree *t)  /*按前序遍历顺序建立二叉树*/
{ char ch;
  if ((ch=getchar())==' ')   /*所建立的二叉树为空二叉树*/
      *t=NULL;
  else {
	     *t=(binthrnode *)malloc(sizeof(binthrnode));/*生成根结点*/
	     (*t)->data=ch;
	     createbintree(&(*t)->lchild);  /*创建左子树*/
	     createbintree(&(*t)->rchild);  /*创建右子树*/
       }
 }
void inthreading(binthrtree *p)  /*对二叉树进行中序线索化*/
{
   if(*p)
    { inthreading(&((*p)->lchild));    /*中序线索化左子树*/
      (*p)->ltag=((*p)->lchild)?0:1;   /*对当前结点及其前驱结点进行穿线*/
      (*p)->rtag=((*p)->rchild)?0:1;
      if (pre)
         {  if(pre->rtag==1)  pre->rchild=*p;
	        if((*p)->ltag==1) (*p)->lchild=pre;
          }
       pre=*p;
       inthreading(&((*p)->rchild));    /*中序线索化右子树*/
    }
}
void createthrtree(binthrtree  *p) /*创建中序穿线二叉树*/
{   createbintree(p);
    inthreading(p);
}
main()
{ binthrtree  root;
  createthrtree(&root);
}