C++ 二叉树的基本操作
实验五：二叉树的基本操作
- （1）输入字符序列，建立二叉链表。
- （2）先序、中序、后序遍历二叉树:递归算法。
- （3）中序遍历二叉树:非递归算法。（最好也能实现先序、后序非递归算法）
- （4）求二叉树的高度 。
- （5）求二叉树的叶子个数。
- （6）借助队列实现二叉树的层次遍历。
- （7）在主函数中设计一个简单的菜单，分别调试上述算法。
源码
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define LIST_INT_SIZE 100
#define LISTINCREMENT 10
int dep, count = 0;
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//建立二叉树
Status CreateBiTree(BiTree &T)
{
char ch;
getchar();
scanf("%c", &ch);
if (ch == ' ' || ch == '\n')
{
T = NULL;
return ERROR;
}
else
{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ch;
printf("请输入%c的左孩子：", T->data);
CreateBiTree(T->lchild);
printf("请输入%c的右孩子：", T->data);
CreateBiTree(T->rchild);
return OK;
}
}
//主菜单
void print()
{
printf("\n菜单如下：\n");
printf("1 . 输入字符序列，建立二叉链表\n");
printf("2 . 先序、中序、后序遍历二叉树:递归算法\n");
printf("3 . 先序、中序、后序遍历二叉树:非递归算法\n");
printf("4 . 求二叉树的高度 \n");
printf("5 . 求二叉树的叶子个数\n");
printf("6 . 借助队列实现二叉树的层次遍历\n");
printf("0 . EXIT\n请选择操作序号：");
}
//先序、中序、后序遍历二叉树:递归算法
void print2()
{
printf("\n递归算法遍历二叉树，菜单如下：\n");
printf("1.先根遍历\n");
printf("2.中序遍历\n");
printf("3.后续遍历\n");
printf("0.退出\n");
printf("请输入二级菜单选择:");
}
Status Visit(BiTree T)
{
if (T)
{
printf("%c ", T->data);
return OK;
}
}
Status PrintElement(TElemType e)
{
printf(" %c ", e);
return OK;
}
//先序
Status PreOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
{
if (T)
{
if (Visit(T->data))
if (PreOrderTraverse(T->lchild, Visit))
if (PreOrderTraverse(T->rchild, Visit))
return OK;
return ERROR;
}
else
return OK;
}
//中序
Status MidOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
{
if (T)
{
if (MidOrderTraverse(T->lchild, Visit))
if (Visit(T->data))
if (MidOrderTraverse(T->rchild, Visit))
return OK;
return ERROR;
}
else
return OK;
}
//后序
Status LastOrderTraverse(BiTree T, Status (*Visit)(TElemType e))
{
if (T)
{
if (LastOrderTraverse(T->lchild, Visit))
if (LastOrderTraverse(T->rchild, Visit))
if (Visit(T->data))
return OK;
return ERROR;
}
else
return OK;
}
//求树的叶子的个数,和打印出叶子
Status LeafNumTree(BiTree T)
{
int lnum, rnum;
if (T != NULL)
{
if (T->lchild == NULL && T->rchild == NULL)
return 1;
else
{
lnum = LeafNumTree(T->lchild);
rnum = LeafNumTree(T->rchild);
return lnum + rnum;
}
}
return 0;
}
//求二叉树的高度
Status BiTreeDepth(BiTree T)
{
int l, r;
if (T)
{
l = BiTreeDepth(T->lchild);
r = BiTreeDepth(T->rchild);
if (l >= r)
dep += l;
else dep += r;
}
else
return 1;
}
//先序、中序、后序遍历二叉树:非递归算法
void print3()
{
printf("\n非递归算法遍历二叉树，菜单如下：\n");
printf("1.先根遍历\n");
printf("0.退出\n");
printf("请输入二级菜单选择:");
}
typedef struct QueueNode
{
BiTree e;
struct QueueNode *next;
} QueueNode, *QueuePtr; //定义队列结点结构
typedef struct
{
QueuePtr front;
QueuePtr rear;
} LinkQueue;
//栈的顺序存储表示
typedef struct
{
BiTNode *base; //栈底指针
BiTNode *top; //栈顶指针
int stacksize; //当前已分配的存储空间
} SqStack;
//初始化一个带头结点的队列
void InitQueue(LinkQueue &q)
{
q.front = q.rear = (QueuePtr)malloc(sizeof(QueueNode));
q.front->next = NULL;
}
//入队列
void enqueue(LinkQueue &q, BiTree p)
{
QueuePtr s;
int first = 1;
s = (QueuePtr)malloc(sizeof(QueueNode));
s->e = p;
s->next = NULL;
q.rear->next = s;
q.rear = s;
}
//出队列
void dequeue(LinkQueue &q, BiTree &p)
{
char data;
QueuePtr s;
s = q.front->next;
p = s->e ;
data = p->data;
q.front->next = s->next;
if (q.rear == s)
q.rear = q.front;
free(s);
printf("%c\t", data);
}
//判断队列是否为空
Status queueempty(LinkQueue q)
{
if (q.front->next == NULL)
return 1;
return 0;
}
//按层次遍历树中结点
void Traverse(BiTree T)
{
LinkQueue q;
BiTree p;
InitQueue(q);
p = T;
enqueue(q, p);
while (queueempty(q) != 1)
{
dequeue(q, p);
if (p->lchild != NULL)
enqueue(q, p->lchild);
if (p->rchild != NULL)
enqueue(q, p->rchild);
}
printf("\n");
}
//建立一个空栈
void InitStack(SqStack &S)
{
S.base = (BiTree)malloc(LIST_INT_SIZE * sizeof(BiTNode));
if (!S.base)
exit(OVERFLOW );//存储分配失败
S.top = S.base;
S.stacksize = LIST_INT_SIZE;
}
//压入栈
void Push(SqStack & S, BiTree p)
{
if (S.top - S.base >= S.stacksize) //满栈，追加存储结构
{
S.base = (BiTree)realloc(S.base, (S.stacksize + LISTINCREMENT) * sizeof(BiTNode));
if (!S.base) exit(OVERFLOW ); //存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += LISTINCREMENT;
}
*(++S.top) = *p;
}
//退出栈
bool Pop(SqStack &S, BiTree &p)
{
if ( S.top == S.base)
{
printf("空栈\n");
return false;
}
p = (BiTree)malloc( sizeof(BiTNode));
*p = *S.top;
--S.top;
return true;
}
//判断是否是空栈
bool StackEmpty(SqStack &S)
{
if ( S.top == S.base)
return true;
else
return false ;
}
Status InOrderTraverAndCountLeaf(BiTree &T, Status(* Vist)(TElemType e))
{
int j = 0, count = 0;
BiTree p;
p = (BiTNode *)malloc( sizeof(BiTNode)); //关键一步
p = T;
SqStack s;
InitStack(s);
while (p || !StackEmpty(s))
{
if (p)
{
Push(s, p); //如果p为非空，将p压入栈
if (!(p->lchild) && !(p->rchild))
++count;//记录叶子节点数
p = p->lchild;
}//if
else
{
Pop(s, p); //如果p为空，则p退栈
Vist(p->data);
p = p->rchild;
}//else
}//while
return count;
}
int main()
{
int n, ncase;
int count;
bool f, f1, f2, f3;
BiTree T;
TElemType e;
print();
while (scanf("%d", &n) != EOF)
{
f = true;
switch (n)
{
case 1:
printf("输入空格或回车表示此结点为空结束\n请输入头结点：");
if (CreateBiTree(T))
printf("二叉树建立成功!\n");
else
printf("二叉树建立失败!\n");
break;
case 2:
print2();
while (scanf("%d", &ncase) != EOF)
{
f1 = true;
switch (ncase)
{
case 1:
printf("先序遍历顺序为：");
if (PreOrderTraverse(T, PrintElement))
printf("先序遍历成功!\n");
else
printf("先序遍历失败!\n");
break;
case 2:
printf("中序遍历顺序为：");
if (MidOrderTraverse(T, PrintElement))
printf("中序遍历成功!\n");
else
printf("中序遍历失败!\n");
break;
case 3:
printf("后序遍历顺序为：");
if (LastOrderTraverse(T, PrintElement))
printf("后序遍历成功!\n");
else
printf("后序遍历失败!\n");
break;
case 0:
f1 = false;
break;
default :
printf("输入错误，请重新输入!\n");
}
if (!f1)
break;
print2();
}
break;
case 3:
print3();
while (scanf("%d", &ncase) != EOF)
{
f2 = true;
switch (ncase)
{
case 1:
InOrderTraverAndCountLeaf(T, PrintElement);
break;
case 0:
f2 = false;
break;
default :
printf("输入错误，请重新输入!\n");
}
if (!f2)
break;
print3();
}
break;
case 4:
dep = 0;
BiTreeDepth(T);
printf("二叉树的高度为：%d\n", dep - 1);
break;
case 5:
count = LeafNumTree(T);
printf("二叉树的叶子个数为：%d\n", count);
break;
case 6:
printf("按层次遍历的顺序为:\n");
Traverse(T);
printf("\n");
break;
case 0:
f = false;
break;
default:
printf("输入错误，请重新输入!\n");
break;
}
if (!f)
{
printf("退出程序...\n");
break;
}
print();
}
return 0;
}