#include <stdio.h>
#include <stdlib.h>
typedef struct BTNode{
char data;
struct BTNode *lchild,*rchild;
}BTNode,*BiTree;
//----------------------二叉树的建立------------------------------
void CreatBiTree(BiTree &bt){
//① 输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树的二叉链表。
char ch;
ch = getchar();
if(ch=='#')
bt = NULL;
else{
bt = (BiTree)malloc(sizeof(BTNode));
bt->data = ch;
CreatBiTree(bt->lchild);
CreatBiTree(bt->rchild);
}
}//CreatBiTree
void CreatBiTree1(BiTree &bt,char Pre[],char In[],int n){
//② 已知二叉树的先序遍历序列和中序遍历序列，建立二叉树的二叉链表。
//bt-->树 Pre[]-->二叉树的先序输入 In[]-->二叉树的中序输入 n-->结点的个数
char Prel[20],Prer[20],Inl[20],Inr[20];//声明存储先序的右左孩子，中序的左右孩子
int i,j,l,r;
if(n < 1){
bt = NULL;
exit(0);
}
else{
bt = (BiTree)malloc(sizeof(BTNode));//申请结点
bt->data = Pre[0];//将二叉树的根节点赋予bt->data
bt->lchild = bt->rchild = NULL;//设置bt的右左孩子为空
i = 0;
while(In[i]!=Pre[0])
i++;
l = i;
r = n-i-1;
for(j = 0; j < i; j++){
Prel[j] = Pre[j+1];
Inl[j] = In[j];
}
for(j = i + 1; j < n; j++){
Prer[j-i-1] = Pre[j];
Inr[j-i-1] = In[j];
}
if(l<1){
bt->lchild = NULL;
}
else
{
CreatBiTree1(bt->lchild,Prel,Inl,l);
}
if(r<1){
bt->rchild = NULL;
}
else{
CreatBiTree1(bt->rchild,Prer,Inr,r);
}
}
}//CreatBiTree1
//-------------------------end--------------------------------------
//------------------二叉树的递归遍历start--------------------------
void PreOrderTraverse(BiTree bt){
//二叉树先序遍历的递归算法
if(bt){
printf("%c",bt->data);
PreOrderTraverse(bt->lchild);
PreOrderTraverse(bt->rchild);
}
}//PreOrderTraverse
void InOrderTraverse(BiTree bt){
//二叉树中序遍历的递归算法
if(bt){
InOrderTraverse(bt->lchild);
printf("%c",bt->data);
InOrderTraverse(bt->rchild);
}
}//InOrderTraverse
void PostOrderTraverse(BiTree bt){
//二叉树后序遍历的递归算法
if(bt){
PostOrderTraverse(bt->lchild);
PostOrderTraverse(bt->rchild);
printf("%c",bt->data);
}
}//PostOrderTraverse
//------------------------end-------------------------------------
//----------------------二叉树的非递归遍历start-------------------
#define MAXSIZE 100
#define INCEMENT 10
typedef struct {
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;
void InitStack(SqStack &s){
//初始化一个空栈
s.base = (BiTree *)malloc(sizeof(BiTree) * MAXSIZE);
if(!s.base){
printf("初始化失败!\n");
exit(0);
}
s.top = s.base;
s.stacksize = MAXSIZE;
}//InitStack
void Push(SqStack &s,BiTree bt){
//数据入栈
if(s.top - s.base >= s.stacksize){
s.base = (BiTree *)realloc(s.base,sizeof(BiTree)*(s.stacksize + INCEMENT ));
if(!s.base){
printf("增加地址出错!\n");
exit(0);
}
s.top = s.base + s.stacksize;
s.stacksize += INCEMENT;
}
*s.top++ = bt;
}//Push
int StackEmpty(SqStack s){
//判断是否栈空！
if(s.base == s.top){
return 1;
}
return 0;
}//StackEmpty
void Pop(SqStack &s,BiTree &bt){
//数据出栈
if(StackEmpty(s)){
printf("此时栈已空!\n");
exit(0);
}
bt = *(--s.top);
}//Pop
int GetTop(SqStack s,BiTree &bt){
//取栈顶元素
if(StackEmpty(s)){
printf("此时栈已空!\n");
exit(0);
}
//s.top= s.top -1;
bt = *(s.top -1);
return 1; //关键！！！！
}//GetTop
void PreOrderTraverse1(BiTree bt){
//二叉树的非递归遍历
BiTree p;
SqStack s;
if(bt){
InitStack(s);
Push(s,bt);
while(!StackEmpty(s)){
while(GetTop(s,p) && p){
printf("%3c",p->data);
Push(s,p->lchild);
}
Pop(s,p);
if(!StackEmpty(s)){
Pop(s,p);
Push(s,p->rchild);
}
}
}
printf("\n");
}//PreOrderTraverse
void InOrderTraverse1(BiTree bt){
//非递归函数的中序遍历
SqStack s;
BiTree p;
if(bt){
InitStack(s);
Push(s,bt);
while(!StackEmpty(s)){
while(GetTop(s,p) && p)
Push(s,p->lchild);
Pop(s,p);
if(!StackEmpty(s)){
Pop(s,p);
printf("%3c",p->data);
Push(s,p->rchild);
}
}
}
printf("\n");
}//InOrderTraverse
void PostOrderTraverse1(BiTree bt){
//非递归函数的后序遍历
SqStack s;
BiTree p,q;
if(bt){
InitStack(s);
Push(s,bt);
while(!StackEmpty(s)){
while(GetTop(s,p) && p)
Push(s,p->lchild);
Pop(s,p);
if(!StackEmpty(s)){
GetTop(s,p);
if(p->rchild)
Push(s,p->rchild);
else{
Pop(s,p);
printf("%3c",p->data);
while(!StackEmpty(s) && GetTop(s,q) && q->rchild == p){
Pop(s,p);
printf("%3c",p->data);
}
if(!StackEmpty(s)){
GetTop(s,p);
Push(s,p->rchild);
}
}
}
}
}
printf("\n");
}
//-----------------------end--------------------------------------
//-----------------------二叉树的应用函数-------------------------
int BiTree_Depth(BiTree bt){
//用递归的方法计算二叉树的高度
int dl,dr;
if(!bt) return 0;
else{
dl = BiTree_Depth(bt->lchild);
dr = BiTree_Depth(bt->rchild);
if(dl >= dr)
return dl+1;
else
return dr+1;
}
}//BiTree_Depth
//----------------------------------------------------------------
//----------------------主函数------------------------------------
void main(){
BiTree bt;
CreatBiTree1(bt,"ABDCEGF","BDAEGCF",7);
printf("递归函数的遍历:\n");
PreOrderTraverse(bt);
printf("\n");
InOrderTraverse(bt);
printf("\n");
PostOrderTraverse(bt);
printf("\n");
printf("非递归函数的遍历:\n");
PreOrderTraverse1(bt);
printf("\n");
InOrderTraverse1(bt);
printf("\n");
PostOrderTraverse1(bt);
printf("\n");
int length = BiTree_Depth(bt);
printf("二叉树的高度为:%d\n",length);
}
