线索二叉树.txt

这是有关数据结构的例程序

definition.h
============================================
typedef char TElemType;
typedef enum{Link, Thread} PointerTag;//Link==0：指针；Thread==1：线索

typedef struct{
TElemType data;
struct BiThrNode *lchild, *rchild;//左右孩子指针
PointerTag LTag, RTag;//左右标志
}BiThrNode, *BiThrTree;//二叉树的二叉链表存储表示

BiThrTree CreateBiThrTree(void);//按先序次序输入二叉树中结点的值，'#'代表空树
void InOrderTraverse_Thr(BiThrTree);//中序遍历二叉线索树，非递归
BiThrTree InOrderThreading(BiThrTree);//中序线索化二叉线索树
BiThrTree InThreading(BiThrTree, BiThrTree);//中序遍历进行中序线索化
=======================================================================

main.c
====================================================
#include <stdio.h>
#include "definition.h"

int main()
{ BiThrTree bt;

printf("请输入根结点：");
bt = CreateBiThrTree();//按先序次序创建二叉树
if( !(bt=InOrderThreading(bt)) )//中序线索化二叉线索树
  return 1;//线索化失败
InOrderTraverse_Thr(bt);//中序遍历二叉线索树，非递归
printf("\n");

return 0;
} =================================================================

function.c
==================================================
#include <stdio.h>
#include <malloc.h>
#include "definition.h"

BiThrTree CreateBiThrTree(void)//按先序次序输入二叉树中结点的值，'#'代表空树
{ TElemType e;
BiThrTree tmp = NULL;

if( (e=getchar())!='#' ){
  getchar();//接收回车符
  tmp=(BiThrTree)malloc(sizeof(BiThrNode));
  if(!tmp)
   return NULL;
  tmp->data=e;
  tmp->LTag=tmp->RTag=Link;
  printf("请输入左孩子：");
  tmp->lchild=CreateBiThrTree();
  printf("请输入右孩子：");
  tmp->rchild=CreateBiThrTree();
}
else
  getchar();//接收回车符

return tmp;
}

BiThrTree InOrderThreading(BiThrTree bt)//中序线索化二叉线索树
{ BiThrTree thrt, pre;

if( !( thrt=(BiThrTree)malloc(sizeof(BiThrNode)) ) )
  return NULL;//建头结点失败
thrt->LTag=Link;
thrt->RTag=Thread;
thrt->rchild=thrt;//右指针回指
if(!bt)
  thrt->lchild=thrt;//若二叉树空，左指针回指
else{
  thrt->lchild=bt;
  pre=thrt;
  pre=InThreading(bt, pre);//中序遍历进行中序线索化
  //最后一个结点线索化
  pre->rchild=thrt;
  pre->RTag=Thread;
  thrt->rchild=pre;
}

return thrt;
}

BiThrTree InThreading(BiThrTree bt, BiThrTree pre)//中序遍历进行中序线索化
{ if(bt){
  pre=InThreading(bt->lchild, pre);//左子树线索化
  //前驱线索
  if(!bt->lchild){
   bt->LTag=Thread;
   bt->lchild=pre;
  }
  //后继线索
  if(!pre->rchild){
   pre->RTag=Thread;
   pre->rchild=bt;
  }
  pre=bt;//保持pre指向p的前驱
  pre=InThreading(bt->rchild, pre);//右子树线索化
}

return pre;
}

void InOrderTraverse_Thr(BiThrTree bt)//中序遍历二叉线索树，非递归
{ BiThrTree tmp = bt->lchild;

while(tmp != bt){
  while(tmp->LTag==Link)
   tmp=tmp->lchild;
  printf("%c", tmp->data);
  while(tmp->RTag==Thread && tmp->rchild!=bt){
   tmp=tmp->rchild;
   printf("%c", tmp->data);
  }
  tmp=tmp->rchild;
}
}