线索二叉树构造和遍历

(实验)线索二叉树构造和遍历

任选一种（先序、中序、后序）线索二叉树，实现如下功能：

①创建二叉树：按照先序序列依次输入各个结点以及空子树，创建二叉树；

②线索化二叉树：对创建的二叉树进行先序遍历；

③遍历线索二叉树：对线索二叉树进行相应的遍历。

#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW -1
typedef struct BiTNode {
 int data;
 struct BiTNode* lchild;
 struct BiTNode* rchild;
 int ltag, rtag;//左右线索标志
}BiTNode,* BiTree;
BiTNode* pre = NULL;//全局变量，指向当前访问结点的前驱


void CreateBiTree(BiTree* T)//二叉树的输入规则
{
 int num;//定义一个变量用于储存输入的字符
 scanf("%d", &num);
 if (num == 0)(*T) = NULL;
 else {
  (*T) = (BiTree)malloc(sizeof(BiTNode));//申请新空间
  if (!(*T)) {
   printf("
内存分配失败
");
   exit(OVERFLOW);
  }
  (*T)->data = num;
  (*T)->ltag = 0;
  (*T)->rtag = 0;
  CreateBiTree(&(*T)->lchild);//建立左子树
  CreateBiTree(&(*T)->rchild);//建立右子树
 }
}
void BuildBiTree_Thr(BiTree T) //创建线索二叉树并对右子树标记
{
 if (T != NULL) {
  ThreadBiTree(T);
  if (pre->rchild == NULL)
   pre->rtag = 1;//右子树标记
 }
 printf("
线索二叉树建立完成!
");
}
void visit(BiTree T)//遍历输出树的结点
{
 printf("%d ", T->data);//输出结点
}
void BuildThread(BiTree T)//线索化
{
 if (T->lchild == NULL) {//左子树为空，建立前驱结点
  T->lchild = pre;
  T->ltag = 1;
 }
 if (pre != NULL && pre->rchild == NULL) 右子树为空，建立后继结点
    {
  pre->rchild = T;
  pre->rtag = 1;
 }
 pre = T;
}
void ThreadBiTree(BiTree T)//中序递归
 {
 if (T != NULL) {
  ThreadBiTree(T->lchild);
  BuildThread(T);
  ThreadBiTree(T->rchild);
 }
}
BiTNode* FirstNode(BiTNode* p) {//寻找最先被访问的结点
 while (p->ltag == 0)p = p->lchild;
 return p;
}
BiTNode* NextNode(BiTNode* p) {//寻找后继结点
 if (p->rtag == 0)return FirstNode(p->rchild);
 else return p->rchild;
}
BiTNode* LastNode(BiTNode* p) {//寻找最后被访问的结点
 while (p->rtag == 0)p = p->rchild;
 return p;
}
BiTNode* PreNode(BiTNode* p){//寻找前驱结点
 if (p->ltag == 0)return LastNode(p->lchild);
 else return p->lchild;
}
void InOrder_Thread(BiTree T) {//中序遍历线索二叉树
 for (BiTNode* p = FirstNode(T);p != NULL;p = NextNode(p))
  visit(p);
}

void main() {
 BiTree T;
 printf("
输入先序序列构建二叉树(空结点用“0”表示):");
 CreateBiTree(&T);
 BuildBiTree_Thr(T);
 printf("
中序遍历线索二叉树序列为:");
 InOrder_Thread(T);
}