线索二叉树
- 格式：docx
- 大小：12.16 KB
- 文档页数：3
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
typedef enum{Link,Thread}Btag; //Link表示结点，Thread表示线索typedef struct BiTreeNode{
ElemType data;
struct BiTreeNode *lchild,*rchild;
Btag ltag,rtag;
}BiTreeNode,*BiTree;
BiTree pro; //遍历前结点
void creat_tree(BiTree *T,ElemType **arr); //函数功能：按前序遍历的次序，创建一颗二叉树
void InOrderTraverse(BiTree T); //函数功能：按中序遍历二叉树
void visit(BiTree T); //函数功能：访问函数
void InOrder_Threading(BiTree T); //函数功能：按中序遍历建立线索二叉树void InOrder_thread(BiTree T); //函数功能：按中序遍历线索二叉树
int main()
{
ElemType *arr = "ab d ce ";
BiTree T;
creat_tree(&T,&arr);
InOrder_Threading(T);
//InOrder_thread(T);
// InOrderTraverse(T);
}
//函数功能：按前序遍历的次序，创建一颗二叉树
void creat_tree(BiTree *T,ElemType **arr)
{
ElemType c;
sscanf(*arr,"%c",&c);
(*arr)++;
if(c == ' ')
(*T) = NULL;
else
{
(*T) = (BiTree)malloc(sizeof(BiTreeNode));
(*T) -> data = c;
(*T) -> ltag = Link;
(*T) -> rtag = Link;
creat_tree(&(*T) -> lchild,arr);
creat_tree(&(*T) -> rchild,arr);
}
}
//函数功能：按中序遍历二叉树
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T -> lchild);
visit(T);
InOrderTraverse(T -> rchild);
}
}
//函数功能：访问函数
void visit(BiTree T)
{
printf("-%d-%c-%d-\n",T -> ltag,T -> data,T -> rtag); }
//函数功能：按中序序列建立线索二叉树
void InOrder_Threading(BiTree T)
{
if(T)
{
InOrder_Threading(T -> lchild);
if(!T -> lchild)
{
T -> lchild = pro;
T -> ltag = Thread;
}
if(!pro -> rchild)
{
pro -> rchild = T;
pro -> rtag = Thread;
}
pro = T;
InOrder_Threading(T -> rchild);
}
}
//函数功能：中序遍历线索二叉树
void InOrder_thread(BiTree T)
{
if(T)
{
if(T -> ltag == Link)
InOrder_thread(T -> lchild);
visit(T);
if(T -> rtag == Link)
InOrder_thread(T -> rchild);
}
}
//函数功能:增加一个头结点，使二叉树构成一个封闭环void in_thread(BiTree *p,BiTree T)
{
}。
