/**********************************************************************
二叉树的基本操作
(1)二叉树的数据结构
(2)二叉树的构造
(3)二叉树遍历 ：先序，中序，后序
************************************************************************/
#include <cstdio>
#include <cstdlib>
const int MAX=20;
//二叉树的结构 利用双链表实现
typedef struct Node
{
char ch; // 数据域
struct Node *plchild; //左子树指针
struct Node *prchild; //右子树指针
}BiTreeNode;
//构造二叉树
//1.按照先序遍历法构造 利用递归构造
// ABD#G##EH##I##CF#J###
void CreateBiTree_PreOrder(BiTreeNode * &T) //注意这里传入的是指针的引用
{
char ch;
scanf("%c",&ch);
if('#'==ch)
T=NULL;
else {
T=new BiTreeNode;
if(NULL==T)
exit(-1);
T->ch=ch;
CreateBiTree_PreOrder(T->plchild); // 构造左子树
CreateBiTree_PreOrder(T->prchild); // 构造右子树
}
}
//2.按照带括号的字符串创建二叉树结构
/*思路：a(b(c,d),e(f(,g),h(i)))
'(': 表明已创建的节点为双亲节点，入栈。将要创建左孩子节点，用flag=1标记
',': 表明将要创建右孩子节点。用flag=2标记
')': 表明左右孩子节点创建和链接完毕，父节点出栈。
default: 创建节点，并且赋值，判断链接情况
*/
void CreateBiTree_ByString(BiTreeNode* &T, char str[])
{
BiTreeNode* Stack[MAX]; // 栈用于存储父节点
int top=0,flag=0;
BiTreeNode* p=NULL; //用于临时指针
while(*str)
{
switch(*str)
{
case '(':
Stack[top++]=p;
flag=1; //表示即将要创建的是 左孩子节点
break;
case ',':
flag=2; //表明将要创建 右孩子节点
break;
case ')':
--top; //将父节点出栈
break;
default:
{
p=new BiTreeNode;
if(NULL==p)
return ;
if(T==NULL)
T=p;
p->ch=*str;
p->plchild=NULL;
p->prchild=NULL;
switch(flag) //此时 flag要初始化 不然非法访问
{
case 1:
Stack[top-1]->plchild=p; //将父节点与左孩子节点链接
break;
case 2:
Stack[top-1]->prchild=p; //将父节点与右孩子节点链接
break;
}
break;
}
}
++str;
}
}
// 递归先序遍历
void PreOrderTraverse_Recur(BiTreeNode *T)
{
if(T)
{
printf("%2c",T->ch);
PreOrderTraverse_Recur(T->plchild);
PreOrderTraverse_Recur(T->prchild);
}
}
// 非递归先序遍历
/* 思路: 先访问父节点，打印。然后压入栈中，然后访问左孩子节点，访问打印压栈。
将左孩子一个个压入栈中，直到NULL.然后在访问右孩子节点。同理按前
*/
void PreOrderTraverse_NoRecur(BiTreeNode *T)
{
BiTreeNode* Stack[MAX]; //利用数组构造栈 先进后出
int top=0;
BiTreeNode *p=T;
while( p || top >0)
{
while(p)
{
printf("%2c",p->ch); //先访问
Stack[top++]=p; //将 父节点压栈
p=p->plchild; //访问左孩子节点
}
if(top>0) //top 代表栈中有多个节点
{ //开始访问 右孩子节点
p=Stack[--top]; //如果某个父节点的左孩子节点为NULL 那么出栈该父节点。
p=p->prchild; //然后又跳入到 访问该右孩子的左子树
}
}
}
// 递归中序遍历
void InOrderTraverse_Recur(BiTreeNode *T)
{
if(T) //如果节点不为NULL
{
InOrderTraverse_Recur(T->plchild); //先放问 左孩子树
printf("%2c",T->ch); //然后在 访问根节点
InOrderTraverse_Recur(T->prchild); // 然后在访问 右孩子树
}
}
// 非递归中序遍历
/* 思路：相比于先序而言(一直将父节点压栈，父节点出栈的时候就是要访问该节点的右孩子树）
所以中序遍历，一直压入左孩子节点,直到NULL.在出栈的时候打印父节点值。
*/
void InorderTraverse_NoRecur(BiTreeNode *T)
{
BiTreeNode* Stack[MAX];
int top=0;
BiTreeNode *p=T;
while( p || top>0 )
{
while(p)
{
Stack[top++]=p; //直接将父节点入栈
p=p->plchild; // 然后访问左子树
}
if(top>0)
{
p=Stack[--top]; //将父节点处栈
printf("%2c",p->ch); //打印父节点值
p=p->prchild; //访问右孩子子树
}
}
}
// 递归后序遍历
void AfterOrderTraverse_Recur(BiTreeNode *T)
{
if(T)
{
AfterOrderTraverse_Recur(T->plchild);
AfterOrderTraverse_Recur(T->prchild);
printf("%2c",T->ch);
}
}
// 非递归后序遍历
/*思路：依旧是将父节点依次压栈。直到左节点为NULL,此时不出栈父节点，而是直接访问右孩子节点
同时设定q用于检测是否已经访问过右孩子节点。
*/
void AfterOrderTraverse_NoRecur(BiTreeNode *T)
{
BiTreeNode* Stack[MAX];
int top=0;
BiTreeNode *p=T,*q=NULL; // q用于判断右节点是否访问过
while(p || top>0)
{
while(p) //直到没有左孩子节点
{
Stack[top++]=p;
p=p->plchild;
}
if(top>0)
{
p=Stack[top-1]; //不出栈 直接访问右子树
if(p->prchild==NULL || p->prchild == q) //没有右节点或者右节点已经访问过
{
printf("%2c",p->ch);
q=p;
p=NULL;
top--;
}
else //有右节点 且没被访问过
p=p->prchild;
}
}
}
//销毁二叉树
void DestoryBiTree(BiTreeNode* &T)
{
if(T)
{
if(T->plchild)
DestoryBiTree(T->plchild);
if(T->prchild)
DestoryBiTree(T->prchild);
delete T;
T=NULL;
}
}
int main()
{//ABD#G##EH##I##CF#J###
BiTreeNode *T=NULL;
CreateBiTree_PreOrder(T);
puts("递归先序遍历:");
PreOrderTraverse_Recur(T);
puts("");
puts("非递归先序遍历:");
PreOrderTraverse_NoRecur(T);
puts("");
puts("递归中序遍历:");
InOrderTraverse_Recur(T);
puts("");
puts("非递归中序遍历:");
InorderTraverse_NoRecur(T);
puts("");
puts("递归后序遍历:");
AfterOrderTraverse_Recur(T);
puts("");
puts("非递归后序遍历:");
AfterOrderTraverse_NoRecur(T);
puts("");
DestoryBiTree(T); //销毁二叉树
puts("
--按照带括号的字符串输入------------");
BiTreeNode *T2=NULL;
char str[]="a(b(c,d),e(f(,g),h(i)))";
CreateBiTree_ByString(T2,str);
puts("递归先序遍历:");
PreOrderTraverse_Recur(T2);
puts("");
puts("非递归先序遍历:");
PreOrderTraverse_NoRecur(T2);
puts("");
puts("递归中序遍历:");
InOrderTraverse_Recur(T2);
puts("");
puts("非递归中序遍历:");
InorderTraverse_NoRecur(T2);
puts("");
puts("递归后序遍历:");
AfterOrderTraverse_Recur(T2);
puts("");
puts("非递归后序遍历:");
AfterOrderTraverse_NoRecur(T2);
puts("");
//DestoryBiTree(T2); //销毁二叉树
}