#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include <queue>
#include <stack>
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;
typedef char TElemType;
TElemType Nil = ' ';
int index=1;
typedef char String[24];
String str;
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
Status InitBiTree(BiTree *T);
void CreateBiTree(BiTree *T);
void DestroyBiTree(BiTree *T);
Status BiTreeEmpty(BiTree T);
TElemType Root(BiTree T);
TElemType Value(BiTree p);
void visit(BiTree T);
int BiTreeDepth(BiTree T);
int BiTreeDepthNonRecursion(BiTree T);
int BiTreeDepthNonRecursion2(BiTree T);
void PreOrderTraverse(BiTree T);
void PreOrderNonRecursion(BiTree T);
void InOrderTraverse(BiTree T);
void InOrderNonRecursion(BiTree T);
void PostOrderTraverse(BiTree T);
void PostOrderNonRecurion(BiTree T);
void LevelOrderTraverse(BiTree T);
void PrintLastInEachLevel(BiTree T);
void PrintLevelOrderByLevel(BiTree T);
int main()
{
int i;
BiTree T;
TElemType e1;
InitBiTree(&T);
CreateBiTree(&T);
printf("构造空二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepthNonRecursion2(T));
e1=Root(T);
printf("二叉树的根为: %c\n",e1);
printf("\n前序遍历二叉树:\n");
PreOrderTraverse(T);
printf("\n中序遍历二叉树:\n");
InOrderTraverse(T);
printf("\n后序遍历二叉树:\n");
PostOrderTraverse(T);
printf("\n层次遍历二叉树:\n");
PrintLevelOrderByLevel(T);
printf("\n输出每层的最后一个结点:\n");
PrintLastInEachLevel(T);
DestroyBiTree(&T);
printf("\n清除二叉树后,树空否?%d(1:是 0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));
i=Root(T);
if(!i)
printf("树空,无根\n");
getchar();
getchar();
return 0;
}
Status InitBiTree(BiTree *T)
{
*T = NULL;
return OK;
}
void CreateBiTree(BiTree *T)
{
TElemType ch;
scanf("%c", &ch);
if (ch == '#')
(*T) = NULL;
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
if (!*T)
exit(OVERFLOW);
(*T)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
void DestroyBiTree(BiTree *T)
{
if (*T)
{
if ((*T)->lchild)
DestroyBiTree(&(*T)->lchild);
if ((*T)->rchild)
DestroyBiTree(&(*T)->rchild);
free(*T);
*T = NULL;
}
}
Status BiTreeEmpty(BiTree T)
{
if (!T)
return TRUE;
else
return FALSE;
}
TElemType Root(BiTree T)
{
if (!T)
return Nil;
else
return T->data;
}
void visit(BiTNode *p)
{
if (p)
printf("%c ", p->data);
}
int BiTreeDepth(BiTree T)
{
if (!T)
return 0;
int i, j;
if (T->lchild)
i = BiTreeDepth(T->lchild);
else
i = 0;
if (T->rchild)
j = BiTreeDepth(T->rchild);
else
j = 0;
return i > j ? i+1 : j+1;
}
int BiTreeDepthNonRecursion(BiTree T)
{
if (!T)
return 0;
queue<BiTNode *> Q;
BiTNode *p;
BiTNode *back;
int level = 0;
Q.push(T);
back = Q.back();
while (!Q.empty())
{
p = Q.front();
Q.pop();
if (p->lchild)
Q.push(p->lchild);
if (p->rchild)
Q.push(p->rchild);
if (p == back)
{
level++;
if (!Q.empty())
back = Q.back();
}
}
return level;
}
int BiTreeDepthNonRecursion2(BiTree T)
{
BiTNode *Q[MAXSIZE];
int level = 0;
int last = 0;
int front = -1;
int rear = -1;
BiTNode *p;
Q[++rear] = T;
last = rear;
while (front < rear)
{
p = Q[++front];
if (p->lchild)
Q[++rear] = p->lchild;
if (p->rchild)
Q[++rear] = p->rchild;
if (front == last)
{
level++;
if (front < rear)
last = rear;
}
}
return level;
}
void PreOrderTraverse(BiTree T)
{
if (!T)
return;
visit(T);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
void PreOrderNonRecursion(BiTree T)
{
if (!T)
return;
stack<BiTNode *> S;
BiTNode *p;
p = T;
while (p || !S.empty())
{
while (p)
{
S.push(p);
visit(p);
p = p->lchild;
}
if (!S.empty())
{
p = S.top();
S.pop();
p = p->rchild;
}
}
}
void InOrderTraverse(BiTree T)
{
if (!T)
return;
InOrderTraverse(T->lchild);
visit(T);
InOrderTraverse(T->rchild);
}
void InOrderNonRecursion(BiTree T)
{
if (!T)
return;
stack<BiTNode *> S;
BiTNode *p;
p = T;
while (p || !S.empty())
{
while (p)
{
S.push(p);
p = p->lchild;
}
if (!S.empty())
{
p = S.top();
S.pop();
visit(p);
p = p->rchild;
}
}
}
void PostOrderTraverse(BiTree T)
{
if (!T)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
visit(T);
}
void PostOrderNonRecurion(BiTree T)
{
if (!T)
return;
stack<BiTNode *> S;
BiTNode *p;
BiTNode *r;
p = T;
r = NULL;
while (p || !S.empty())
{
while (p)
{
S.push(p);
p = p->lchild;
}
if (!S.empty())
{
p = S.top();
if (p->rchild && p->rchild != r)
{
p = p->rchild;
S.push(p);
p = p->lchild;
}
else
{
S.pop();
visit(p);
r = p;
p = NULL;
}
}
}
}
void LevelOrderTraverse(BiTree T)
{
if (!T)
return;
queue<BiTNode *> Q;
BiTNode *p;
Q.push(T);
while (!Q.empty())
{
p = Q.front();
Q.pop();
visit(p);
if (p->lchild)
Q.push(p->lchild);
if (p->rchild)
Q.push(p->rchild);
}
}
void PrintLastInEachLevel(BiTree T)
{
if (!T)
return;
queue<BiTNode *> Q;
BiTNode *p;
BiTNode *back;
Q.push(T);
back = Q.back();
while (!Q.empty())
{
p = Q.front();
Q.pop();
if (p->lchild)
Q.push(p->lchild);
if (p->rchild)
Q.push(p->rchild);
if (p == back)
{
visit(p);
if (!Q.empty())
back = Q.back();
}
}
}
void PrintLevelOrderByLevel(BiTree T)
{
if (!T)
return;
queue<BiTNode *> Q;
BiTNode *p;
BiTNode *back;
Q.push(T);
back = Q.back();
while (!Q.empty())
{
p = Q.front();
Q.pop();
visit(p);
if (p->lchild)
Q.push(p->lchild);
if (p->rchild)
Q.push(p->rchild);
if (p == back)
{
putchar('\n');
if (!Q.empty())
back = Q.back();
}
}
}