# 线索二叉树构建和遍历_小甲鱼数据结构和算法

XAMPP案例 468浏览

— tag typedef pre == 约定cnblogs amp scan

# include  <stdio.h> # include <stdlib.h>

typedef  char ElemType;

//线索存储标志位
// Link(0):表示指向左右孩子的指针
// Thread(1):表示指向前驱后继的线索
typedef  enum {Link, Thread} PointerTag;

typedef  struct BiThrNode
{ char data;
struct BiThrNode * lchild ,* rchild ;

PointerTag ltag;
PointerTag rtag;
} BiThrNode, * BiThrTree;

//定义一个全局变量表示刚刚走过的节点
BiThrTree pre;

//创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
void CreateBiThrTree (BiThrTree * T) {
char c;
scanf ( " %c " ,& c);

if ( '  ' == c ){
*T = NULL ;
} else {
*T = (BiThrNode *) malloc ( sizeof (BiThrNode));
( *T)->data = c;
( *T)->ltag = Link;
( *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 * p, BiThrTree T) {
*p = (BiThrNode *) malloc ( sizeof (BiThrNode));
( *p)->ltag = Link;
( *p)->rtag = Link;
( *p)->rchild = * p;
if (! T) {
( *p)->lchild = * p;
} else {
( *p)->lchild = T;
pre = * p;
InThreading(T);
pre ->rchild = * p;
pre ->rtag = Thread;
( *p)->rchild = pre;
}
}

void visit ( char c) {
printf ( " %c " ,c);
}
//中序遍历二叉树，叠代
void InOrderTraverse ( BiThrTree T ) {
BiThrTree p;
p = T-> lchild;

while ( p!= T ){
while ( p->ltag == Link ){
p = p-> lchild;
}
visit(p -> data);

while ( p->rtag == Thread && p->rchild != T ){
p = p-> rchild;
visit(p -> data);
}
p = p-> rchild;
}

}
int main () {

BiThrTree P,T = NULL ;

CreateBiThrTree( & T );

InOrderThreading( & P, T );

printf ( "中序遍历二叉树的结果为：" );

InOrderTraverse( P );

printf ( " \n " );

return  0 ;
}