#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULL 0
typedef char TElemType;
typedef int Status;//用作函数值类型,表示函数结构状态
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针 (成员变量也可以是指向结构体自身的指针)
} BiTNode, *BiTree;//*Bitree是指向结点结构体的指针类型
//以下是建立二叉树存储结构
Status CreateBiTree(BiTree &T) {
char 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);//遍历访问根结点的右子树
}
return OK;
} // CreateBiTree
void PreOrder (BiTree T)
{ // 先序遍历二叉树
if (T) {
printf("%4c",T->data); // 访问结点
PreOrder(T->lchild);//遍历访问根结点的左子树
PreOrder(T->rchild); //遍历访问根结点的右子树
}}
void InOrder (BiTree T)
{ // 中序遍历二叉树
if (T) {
InOrder(T->lchild);//遍历访问根结点的左子树
printf("%4c",T->data);
InOrder(T->rchild);//遍历访问根结点的右子树
}
}
void PostOrder (BiTree T)
{ // 后序遍历二叉树
if(T){
PostOrder(T->lchild);// 遍历访问根结点的左子树
PostOrder(T->rchild);//遍历访问根结点的右子树
printf("%4c",T->data);
}
}
int BiTreeDeep(BiTree T) {
if(T == NULL)
return 0;
else {
int LTreedeep = BiTreeDeep(T->lchild);
int RTreedeep = BiTreeDeep(T->rchild);
return (LTreedeep > RTreedeep ? LTreedeep : RTreedeep)+1;
}
if(T->lchild ==NULL&& T->rchild == NULL){
return 1;
}
}
int main()
{
BiTree T;
T=NULL;//建立空二叉树
printf("\n 请按先序次序输入各结点的值,以#表示空树:\n");
CreateBiTree(T);
printf("二叉树已建立完毕!\n");
printf("\n 先序遍历:");
PreOrder(T);
printf("\n 中序遍历:");
InOrder(T);
printf("\n 后序遍历:");
PostOrder(T);
int i = BiTreeDeep(T);
printf("\n二叉树深度:%d",i);
return 0;
}
实验结果输出