// 二叉树的遍历与应用算法的设计与实现.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
return 0;
}
//节点动态生成，可以充分利用存储空间
#include
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 10//存储空间初始分配量
#define STACK_INCREAMENT 2//存储空间分配增量
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char TElemType;
//二叉树的二叉链表存储结构
struct BiTNode
{
char data;//节点中的数据的类型
BiTNode lchild, *rchild;//左右孩子指针,指向节点自身
};
typedef BiTNode *BiTree;
/**************************************栈的操作****************************************/
//栈的顺序存储结构
struct SqStack
{
BiTree base;//栈底指针
BiTree *top;//栈顶指针
int stacksize;//当前已分配的存储空间
};
//构造一个空栈S-------------------------《数据结构》P47
void InitStack(SqStack &S)
{
S.base = (BiTree)malloc(STACK_INIT_SIZE*sizeof(BiTree));
if (!S.base)
exit(OVERFLOW);//存储空间分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
//若栈S为空，则返回TRUE，若栈S不空则返回FALSE
Status StackEmpty(SqStack S)
{
if (S.base == S.top)
return TRUE;
else
return FALSE;
}
//插入元素e为新的栈顶元素（入栈）
void Push(SqStack &S, BiTree e)
{
if (S.top - S.base >= S.stacksize)//栈满，追加存储空间
{
S.base = (BiTree*)realloc(S.base, (S.stacksize + STACK_INCREAMENT)*sizeof(BiTree));
if (!S.base)
exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACK_INCREAMENT;
}
//插入栈顶元素
(S.top) = e;
S.top++;//栈顶指针指向下一个
}
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK（出栈）
Status Pop(SqStack &S, BiTree &e)
{
if (S.top == S.base)
return ERROR;
else
e = *(--S.top);
return OK;
}
/****************************************栈的操作部分END****************************************/
/*****************************************二叉树的操作部分****************************************/
//构造一个空的二叉树T
void InitBiTree(BiTree &T)
{
T = NULL;
}
//二叉树T存在，销毁二叉树T
void DestroyBiTree(BiTree &T)
{
if (T)
{
if (T->lchild)
DestroyBiTree(T->lchild);//销毁左孩子子树
if (T->rchild)
DestroyBiTree(T->rchild);//销毁右孩子子树
free(T);//释放根节点
T = NULL;
}
}
//构造二叉链表表示的二叉树T--------------------------------《数据结构》P131
//按照先序次序输入二叉树中节点的值，空格字符表示空树
void CreateBiTree(BiTree &T)
{
char h;//节点的数据的类型
scanf_s("%c", &h);
if (h == ' ')
T = NULL;
else
{
T = (BiTree)malloc(sizeof(BiTNode));
if (!T)
exit(OVERFLOW);
T->data = h;
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
}
//先序遍历中的（*visit函数），也就是一个输出函数
Status PrintElement(TElemType &e)
{
printf("%c", e);
return OK;
}
//用递归算法先序遍历二叉树
int 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;
}
}
//用递归算法中序遍历二叉树
int InOrderTraverse(BiTree T, Status(*Visit)(TElemType &e))
{
if (T)//二叉树不空
{
if (InOrderTraverse(T->lchild, Visit))//遍历左子树
{
if (Visit(T->data))//访问根结点
{
if (InOrderTraverse(T->rchild, Visit))//遍历右子树
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
}
//用递归算法后序遍历二叉树
int PostOrderTraverse(BiTree T, Status(*Visit)(TElemType &e))
{
if (T)//二叉树不空
{
if (PostOrderTraverse(T->lchild, Visit))//遍历左子树
{
if (PostOrderTraverse(T->rchild, Visit))//遍历右子树
{
if (Visit(T->data))//访问根结点
{
return OK;
}
}
}
return ERROR;
}
else
{
return OK;
}
}
//按照层次遍历二叉树
int front = 0, rear = 1;
void LevelOrderTraverse(BiTNode *T)
{
BiTNode *q[100];
q[0] = T;
while (front
{
if (q[front])
{
printf("%c", q[front]->data);
q[rear++] = q[front]->lchild;
q[rear++] = q[front]->rchild;
front++;
}
else
{
front++;
}
}
}
//二叉树T存在，返回T的深度
int BiTreeDepth(BiTree T)
{
int i, j;
if (!T)
return 0;
if (T->lchild)
i = BiTreeDepth(T->lchild);//i为左子树的深度
else
i = 0;
if (T->rchild)
j = BiTreeDepth(T->rchild);
else
j = 0;
return i>j ? i + 1 : j + 1;//T的深度为其左右子树中的大者加1
}
//统计二叉树中结点的个数（先序）
int CountNode(BiTree T)
{
static int count = 0;
if (!T) count = 0;
else{
count = CountNode(T->lchild) + CountNode(T->rchild) + 1;
}
return count;
}
////统计二叉树中叶子结点的个数（先序）
//int CountLeaf(BiTree T, Status(*Visit)(TElemType &e))
//{
//int count = 0;
//if (T)
//{
//if ((!T->lchild) && (!T->rchild))
//{
//count++;
//}
//
//}
//else
//{
//CountLeaf(T->lchild, Visit);
//CountLeaf(T->rchild, Visit);
//}
//return count;
//}
//递归统计二叉树中叶子结点的个数（先序）
int CountLeaf(BiTree &T)
{
if (T == NULL)
{
return 0;
}
else if (T->lchild == NULL && T->rchild == NULL)
{
return 1;
}
else
{
return (CountLeaf(T->lchild) + CountLeaf(T->rchild));
}
}
//递归法将二叉树的左右子树互换
void Exchange(BiTree &T, Status(*Visit)(TElemType &e))
{
BiTNode *temp;
if (T)
{
Exchange(T->lchild, PrintElement);
Exchange(T->rchild, PrintElement);
temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
}
}
int main()
{
BiTree T;
InitBiTree(T);
printf("\n构造空的二叉树后,树的深度=%d\n", BiTreeDepth(T));
printf("\n请按照先序的次序输入二叉树（如：ab三个空格表示以a为根节点，b为左子树的二叉树）:\n");
CreateBiTree(T);//建立二叉树T
printf("\n建立二叉树后，树的深度为：%d\n", BiTreeDepth(T));
printf("先序递归遍历二叉树：");
PreOrderTraverse(T, PrintElement);
printf("\n中序递归遍历二叉树：");
InOrderTraverse(T, PrintElement);
printf("\n后序递归遍历二叉树：");
PostOrderTraverse(T, PrintElement);
printf("\n层序递归遍历二叉树：");
LevelOrderTraverse(T);
printf("\n\n二叉树中结点的个数：%d\n", CountNode(T));
CountNode(T);
printf("\n二叉树中叶子结点的个数：%d\n", T);
CountLeaf(T);
printf("\n左右子树交换：%d\n", T);
Exchange(T, PrintElement);
system("pause");
}
