欢迎访问我的主页!http://godweiyang.com edited 7 年，2 月前
/*******************二叉树各种操作*********************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BiTreeNode
{
char data;
struct BiTreeNode* lchild, * rchild;
}BiTreeNode;
/**创建二叉树结点**/
BiTreeNode* CreatBiTreeNode(char x)
{
BiTreeNode* node = (BiTreeNode* )malloc(sizeof(BiTreeNode));
node->data = x;
node->lchild = node->rchild = NULL;
return node;
}
/**创建二叉树(先序输入)**/
BiTreeNode* CreatBiTree()
{
char x;
BiTreeNode* root;
scanf("%c", &x);
getchar();
if (x == '0')
root = NULL;
else
{
root = (BiTreeNode* )malloc(sizeof(BiTreeNode));
root->data = x;
root->lchild = CreatBiTree();
root->rchild = CreatBiTree();
}
return root;
}
/**在指定结点左孩子处插入新结点**/
void Insert_lBt(BiTreeNode* parent, char x)
{
BiTreeNode* ptr = CreatBiTreeNode(x);
if (ptr->lchild)
{
ptr->lchild = parent->lchild;
parent->lchild = ptr;
}
else
parent->lchild = ptr;
}
/**在指定结点右孩子处插入新结点**/
void Insert_rBt(BiTreeNode* parent, char x)
{
BiTreeNode* ptr = CreatBiTreeNode(x);
if (ptr->rchild)
{
ptr->rchild = parent->rchild;
parent->rchild = ptr;
}
else
parent->rchild = ptr;
}
/**先序遍历非递归**/
void Pre_Bt(BiTreeNode* Bt)
{
int Ss_top = 0;
BiTreeNode* ptr = Bt;
BiTreeNode* Ss[1000];
while (Ss_top >= 0)
{
while (ptr)
{
printf("%c ", ptr->data);
if (ptr->rchild)
Ss[Ss_top++] = ptr->rchild;
ptr = ptr->lchild;
}
if (Ss_top-- > 0)
ptr = Ss[Ss_top];
}
printf("\n");
}
/**先序遍历递归**/
void Pre_BtRec(BiTreeNode* Bt)
{
if(Bt)
{
printf("%c",Bt->data);
Pre_BtRec(Bt->lchild);
Pre_BtRec(Bt->rchild);
}
}
/**中序遍历非递归**/
void In_Bt(BiTreeNode* Bt)
{
int Ss_top = 0;
BiTreeNode* ptr = Bt;
BiTreeNode* Ss[1000];
while (Ss_top >= 0)
{
while (ptr)
{
Ss[Ss_top++] = ptr;
ptr = ptr->lchild;
}
if (Ss_top-- > 0)
{
ptr = Ss[Ss_top];
printf("%c", ptr->data);
ptr = ptr->rchild;
}
}
printf("\n");
}
/**中序遍历递归**/
void In_BtRec(BiTreeNode* Bt)
{
if(Bt)
{
In_BtRec(Bt->lchild);
printf("%c",Bt->data);
In_BtRec(Bt->rchild);
}
}
/**后序遍历非递归**/
void Post_Bt(BiTreeNode* Bt)
{
int Ss1_top = 0, Ss2_top = 0, Ss2[1000], flag;
BiTreeNode* ptr = Bt;
BiTreeNode* Ss1[1000];
while (Ss1_top >= 0)
{
while (ptr)
{
Ss1[Ss1_top++] = ptr;
Ss2[Ss2_top++] = 0;
ptr = ptr->lchild;
}
if (Ss1_top-- > 0)
{
flag = Ss2[--Ss2_top];
ptr = Ss1[Ss1_top];
if (!flag)
{
Ss1[Ss1_top++] = ptr;
Ss2[Ss2_top++] = 1;
ptr = ptr->rchild;
}
else
{
printf("%c", ptr->data);
ptr = NULL;
}
}
}
printf("\n");
}
/**后序遍历递归**/
void Post_BtRec(BiTreeNode* Bt)
{
if(Bt)
{
Post_BtRec(Bt->lchild);
Post_BtRec(Bt->rchild);
printf("%c",Bt->data);
}
}
/**根据二叉树先序和中序遍历生成二叉树**/
BiTreeNode* CreatBTFromPreIn(char* Pre, char* In, int len)
{
BiTreeNode* root = (BiTreeNode* )malloc(sizeof(BiTreeNode));
if (len <= 0)
{
root = NULL;
return root;
}
root = CreatBiTreeNode(*Pre);
int i;
for (i = 0; i < len; ++i)
if (*Pre == *(In+i))
break;
root->lchild = CreatBTFromPreIn(Pre+1, In, i);
root->rchild = CreatBTFromPreIn(Pre+1+i, In+i+1, len-i-1);
return root;
}
/*****************************************************************************/
typedef struct BiTreeNode1
{
char data;
int ltag, rtag;
struct BiTreeNode1* lchild, * rchild;
}BiTreeNode1;
/**创建二叉树(先序输入)**/
BiTreeNode1* CreatBiTree1()
{
char x;
BiTreeNode1* root;
scanf("%c", &x);
getchar();
if (x == '0')
root = NULL;
else
{
root = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
root->data = x;
root->lchild = CreatBiTree1();
root->rchild = CreatBiTree1();
}
return root;
}
/**中序线索化二叉树**/
BiTreeNode1* InPre;//全局指针变量，用于指向中序遍历过程中的直接前驱结点
void InThread(BiTreeNode1* Bt)
{
if (Bt)
{
InThread(Bt->lchild);
if (Bt->lchild == NULL)
{
Bt->lchild = InPre;
Bt->ltag = 1;
}
else
Bt->ltag = 0;
if (InPre->rchild == NULL)
{
InPre->rchild = Bt;
InPre->rtag = 1;
}
else
InPre->rtag = 0;
InPre = Bt;
InThread(Bt->rchild);
}
}
BiTreeNode1* Cr_InThread(BiTreeNode1* Bt)//为BT所指的二叉树添加头结点
{
BiTreeNode1* root = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
root->data = '0';
root->ltag = 0;
root->rtag = 1;
root->rchild = Bt;
if (Bt == NULL)
root->lchild = root;
else
{
root->lchild = Bt;
InPre = root;
InThread(Bt);
InPre->rchild = root;
InPre->rtag = 1;
root->rchild = InPre;
}
return root;
}
/**基于中序线索二叉树，求指定节点在中序序列中的前驱**/
BiTreeNode1* InLtr_F(BiTreeNode1* ptr)
{
BiTreeNode1* qtr = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
if (ptr->ltag == 1)
return ptr->lchild;
else
{
qtr = ptr->lchild;
while (qtr->rtag)
qtr = qtr->rchild;
return qtr;
}
}
/**基于中序线索二叉树，求指定节点在中序序列中的后继**/
BiTreeNode1* InLtr_N(BiTreeNode1* ptr)
{
BiTreeNode1* qtr = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
if (ptr->rtag == 1)
return ptr->lchild;
else
{
qtr = ptr->rchild;
while (qtr->ltag)
qtr = qtr->lchild;
return qtr;
}
}
/**对中序线索二叉树进行中序遍历**/
void Ltr_Thread(BiTreeNode1* Bt)
{
BiTreeNode1* ptr = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
BiTreeNode1* qtr = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
ptr = Bt;
if (ptr)
{
while (ptr->ltag == 0)
ptr = ptr->lchild;
while (ptr && ptr->data != '0')
{
printf("%c", ptr->data);
if (ptr->rtag == 1)
ptr = ptr->rchild;
else
{
qtr = ptr->rchild;
while (qtr->ltag == 0)
qtr = qtr->lchild;
ptr = qtr;
}
}
}
}
int main()
{
BiTreeNode1* Bt = (BiTreeNode1* )malloc(sizeof(BiTreeNode1));
Bt = Cr_InThread(CreatBiTree1());
Ltr_Thread(Bt);
return 0;
}