写程序实现教材上算法:二叉树的创建、中序递归遍历、 中序非递归遍历、 中序线索化、中序线索化二叉树的遍历,并写程序验证。
线索化的相关操作太过复杂,是抄的,而且好像有点问题,慎用!
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define STACKINITSIZE 20//栈初始空间大小
#define INCREASEMENT 10//栈空间大小的增量
using namespace std;
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//队列的结构体
typedef BiTree ElemType;
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear; // 链表头,链表尾,也可以称队头,队尾
}LinkQueue; //先进先出
//算法5.3 按照先序遍历的顺序建立二叉链表
void CreateBiTree(BiTree &T)
{
TElemType ch;
cin>>ch;
if( ch == '#' ) T = NULL; //递归结束,建空树
else
{
T = new BiTNode; //生成根节点
T -> data = ch; //根节点数据域置为ch
CreateBiTree(T -> lchild); //递归创建左子树
CreateBiTree(T -> rchild); //递归创建右子树
}
}
//算法5.1 中序遍历的递归算法
void InOrderTraverse(BiTree T)
{
if(T) //若二叉树非空
{
InOrderTraverse(T -> lchild); //中序遍历左子树
cout<<T -> data<<" "; //访问根节点
InOrderTraverse(T-> rchild); //中序遍历右子树
}
}
typedef struct SqStack
{
BiTNode *base;//栈底指针
BiTNode *top;//栈顶指针
int stacksize;//顺序栈空间大小
}SqStack;//定义顺序栈结构
//建立一个空栈,建立成功,返回1,失败,返回0
int InitStack(SqStack &S)
{
S.base = (BiTNode*)malloc(STACKINITSIZE * sizeof(BiTNode));//20为栈的大小,可以更改
if(!S.base)
return 0;
S.top = S.base;
S.stacksize = STACKINITSIZE;
return 1;
}
//进栈操作
int Push(SqStack &S,BiTNode e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (BiTNode*)realloc(S.base,(STACKINITSIZE + INCREASEMENT) * sizeof(BiTNode));
if(!S.base)
return 0;
S.stacksize = 30;
}
*S.top = e;
S.top ++;
return 1;
}
//出栈操作,若栈为空,则返回0;栈不为空,则返回1
int Pop(SqStack &S,BiTNode &e)
{
if(S.base == S.top)
return 0;
S.top --;
e = *S.top;
return 1;
}
//判断栈是否为空,若栈为空,则返回true,栈不为空,则返回false
bool StackEmpty(SqStack S)
{
if(S.base == S.top)
return true;
else
return false;
}
//算法5.2 中序遍历的非递归算法
int aInOrderTraverse(BiTree T)
{
if(!T)
return 0;
SqStack S;
int n = InitStack(S);//建立空栈
if(!n)
return 0;
BiTree p = T;
BiTNode e;//二叉树节点,用于存放从栈中取出的节点
while(p || !StackEmpty(S))
{
if(p)
{
Push(S,*p);
p = p->lchild;
}
else
{
Pop(S,e);
printf("%c ",e.data);
p = e.rchild;
}
}
printf("\n");
return 1;
}
/*
建树输入梳理:
a 建立根节点
b 建立左子树根节点
# 表示左子树的左子树为空树
# 表示右子树的右子树为空树
c 建立右子树根节点
# 表示右子树的左子树为空树
# 表示右子树的右子树为空树
*/
//线索化
using namespace std;
typedef struct BiThrNode
{
char data;
struct BiThrNode *lchild,*rchild;
int LTag,RTag;
} BiThrNode,*BiThrTree;
BiThrNode *pre=new BiThrNode;
void CreateBiTree(BiThrTree &T)
{
char ch;
cin >> ch;
if(ch=='#')
T=NULL;
else
{
T=new BiThrNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void InThreading(BiThrTree root)/* 对root所指的二叉树进行中序线索化,其中pre始终指向刚访问过的结点,其初值为NULL*/
{
if (root!=NULL)
{
InThreading(root->lchild); /* 线索化左子树 */
if (root->lchild==NULL)/*没有左孩子指向前驱*/
{
root->LTag=1;
root->lchild=pre->rchild; /*置前驱线索 */
}
if (pre!=NULL&&pre->rchild==NULL) /* 置后继线索 */
{
pre->rchild=root;
pre->RTag=1;
}
pre=root;
InThreading(root->rchild); /*线索化右子树*/
}
}
BiThrNode * InNext(BiThrNode *p)
/*在中序线索二叉树中查找p的中序后继结点,并用next指针返回结果*/
{
BiThrNode *Next;
BiThrNode *q;
if (p->RTag==1)
Next=p->rchild; /*直接利用线索*/
else
{
/*在p的右子树中查找"最左下端"结点*/
if(p->rchild!=NULL)
{
for(q=p->rchild; q->LTag==0 ; q=q->lchild);
Next=q;
}
else
Next = NULL;
}
return Next;
}
BiThrNode* TinFirst(BiThrTree root)
{
BiThrNode *q=root;
q=root;
if(q)
while(q->lchild!=NULL)/*找左子树的左子树。。。*/
q=q->lchild;
return q;
}
void InOrderTraverse_Thr(BiThrTree root)
{
BiThrNode *p;
p=TinFirst(root);/*找到第一个结点*/
while(p!=NULL)
{
printf("%c ",p->data);
p=InNext(p);
}
}
void ThreadMain()
{
pre->RTag=1;
pre->rchild=NULL;
BiThrTree tree;
cout<<"可输入:abd##e##cf##g##建立线索化二叉树"<<endl;
CreateBiTree(tree);
InThreading(tree);
cout<<"中序线索化遍历二叉树"<<endl;
InOrderTraverse_Thr(tree);
}
int main()
{
BiTree T;
cout<<"可输入:abd##e##cf##g##"<<endl;
CreateBiTree(T); //使层次遍历顺序为abcdefg需要输入:abd##e##cf##g##
cout<<"中序遍历二叉树"<<endl;
InOrderTraverse(T); //递归中序遍历
cout<<"非递归中序遍历二叉树"<<endl;
aInOrderTraverse(T);
ThreadMain(); //线索化主操作
return 0;
}
可输入:abd##e##cf##g##
abd##e##cf##g##
中序遍历二叉树
d b e a f c g 非递归中序遍历二叉树
d b e a f c g
可输入:abd##e##cf##g##建立线索化二叉树
abd##e##cf##g##
中序线索化遍历二叉树
d b e a c g