《数据结构（C语言版）》二叉树的实现
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟民 编著
数据结构（C语言版）
以下是本人对该紫皮书第六章树和二叉树中二叉树代码实现，按递归方式先序和后序遍历了二叉树，用非递归的栈实现了中序遍历，用队列实现了层次遍历，并且额外补充了二叉树的复制、计算二叉树的深度、计算二叉树结点总数、计算二叉树叶子结点总数等算法
话不多说上运行结果
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译，会帮你自动调整缩进）
代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
typedef BiTNode* SElemType;
/*用栈实现非递归的遍历二叉树算法*/
#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACKINCREMENT 10//存储空间分配增量
typedef struct
{
SElemType* base;
SElemType* top;
int stacksize;//当前已分配的存储空间，以元素为单位
}SqStack;//用栈实现树的非递归遍历
Status InitStack(SqStack& S);//初始化一个空栈
Status StackEmpty(SqStack S);//判断栈是否为空
Status Push(SqStack& S, SElemType e);//顺序栈的入栈
Status Pop(SqStack& S, SElemType& e);//顺序栈的出栈
/*用队列实现二叉树的层次遍历算法*/
typedef BiTNode* QElemType;
typedef struct QNode
{
QElemType data;
struct QNode* next;
}QNode, * QueuePtr;
typedef struct
{
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
Status InitQueue(LinkQueue& Q);//链队列的初始化
Status EnQueue(LinkQueue& Q, QElemType e);//入队
Status DeQueue(LinkQueue& Q, QElemType& e);//出队
Status QueueEmpty(LinkQueue Q);//队列是否为空
Status CreatBiTree(BiTree& T);//按先序遍历序列建立二叉树的二叉链表
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e));//递归方式实现前序遍历
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e));//用非递归方式--栈实现中序遍历
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e));//递归方式实现后序遍历
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType));//用队列实现二叉树层次遍历
Status PrintElement(TElemType e);//打印二叉树元素
Status CopyBiTree(BiTree T, BiTree& NewT);//复制二叉树
int Depth(BiTree T);//计算树的深度
int NodeCount(BiTree T);//计算二叉树结点总数
int LeafCount(BiTree T);//计算二叉树叶子结点总数
int main()
{
BiTree T, Same_T;
CreatBiTree(T);
printf("前序遍历结果为：");
PreOrderTraverse(T, PrintElement);
printf("\n中序遍历结果为：");
InOrderTraverse(T, PrintElement);
printf("\n后序遍历结果为：");
PostOrderTraverse(T, PrintElement);
CopyBiTree(T, Same_T);
printf("\n复制后的树按前序遍历后的结果为：");
PreOrderTraverse(Same_T, PrintElement);
printf("\n树的深度为：%d", Depth(T));
printf("\n树的结点总数为：%d", NodeCount(T));
printf("\n数的叶子结点总数为：%d", LeafCount(T));
return 0;
}
Status CreatBiTree(BiTree& T)//按先序遍历序列建立二叉树的二叉链表
{
char ch;
scanf("%c", &ch);
if (ch == '#')
{
T = NULL;
}
else
{
if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))
{
exit(OVERFLOW);
}
T->data = ch;
CreatBiTree(T->lchild);
CreatBiTree(T->rchild);
}
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 InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))//用非递归方式--栈实现中序遍历
{
SqStack S;
InitStack(S);
BiTNode* p = T;
BiTNode* q = NULL;
while (p || !StackEmpty(S))
{
if (p)//如果是根节点
{
Push(S, p);//先入栈
p = p->lchild;//访问它的左子树
}
else//如果左子树为空
{
Pop(S, q);
Visit(q->data);
p = q->rchild;
}
}
return OK;
}
Status 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;
}
}
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType))//用队列实现二叉树层次遍历
{
BiTNode* p;
LinkQueue qu;
InitQueue(qu);
EnQueue(qu, T);
while (!QueueEmpty(qu))
{
DeQueue(qu, p);
Visit(p->data);
if (p->lchild)//有左孩子则进队
{
EnQueue(qu, p->lchild);
}
if (p->rchild)//有右孩子则进队
{
EnQueue(qu, p->rchild);
}
}
return OK;
}
Status PrintElement(TElemType e)//打印二叉树元素
{
printf("%c ", e);
return OK;
}
Status CopyBiTree(BiTree T, BiTree& NewT)//复制二叉树
{
if (T == NULL)
{
NewT = NULL;
return OK;
}
else
{
NewT = (BiTNode*)malloc(sizeof(BiTNode));
NewT = new BiTNode;
NewT->data = T->data;
CopyBiTree(T->lchild, NewT->lchild);
CopyBiTree(T->rchild, NewT->rchild);
}
}
int Depth(BiTree T)//计算树的深度
{
int m = 0;
int n = 0;
if (T == NULL)
{
return 0;
}
else
{
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m > n)
{
return m + 1;
}
else
{
return n + 1;
}
}
}
int NodeCount(BiTree T)//计算二叉树结点总数
/*
如果是空树，则结点个数为0
否则，结点个数=左子树的结点个数+右子树的结点个数+1
*/
{
if (T == NULL)
{
return 0;
}
else
{
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
}
int LeafCount(BiTree T)//计算二叉树叶子结点总数
/*
如果是空树，则叶子结点个数为0
否则，叶子结点个数=左子树叶子结点个数+右子树叶子结点个数
这里不用+1，因为子树的根节点一定不是叶子结点
*/
{
if (T == NULL)
{
return 0;
}
if (T->lchild == NULL && T->rchild == NULL)//如果是叶子结点返回1
{
return 1;
}
else
{
return LeafCount(T->lchild) + LeafCount(T->rchild);
}
}
Status InitStack(SqStack& S)//初始化一个空栈
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)
{
exit(OVERFLOW);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)//判断栈是否为空
{
if (S.top == S.base)
{
return TRUE;
}
else
{
return FALSE;
}
}
Status Push(SqStack& S, SElemType e)//顺序栈的入栈
{
if (S.top - S.base >= S.stacksize)
{
SElemType* New_ptr = (SElemType*)realloc(S.base, ((S.stacksize) + STACKINCREMENT) * sizeof(SElemType));
if (!New_ptr)
{
exit(OVERFLOW);
}
S.base = New_ptr;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(SqStack& S, SElemType& e)//顺序栈的出栈
{
if (S.top == S.base)
{
return ERROR;
}
e = *--S.top;
return OK;
}
Status InitQueue(LinkQueue& Q)//链队列的初始化
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front)
{
exit(OVERFLOW);
}
Q.front->next = NULL;
return OK;
}
Status EnQueue(LinkQueue& Q, QElemType e)//入队
{
QNode* p = (QueuePtr)malloc(sizeof(QNode));
if (!p)
{
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue& Q, QElemType& e)//出队
{
if (Q.front == Q.rear)
{
return ERROR;
}
QNode* p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)//注意这里要考虑到,当队列中最后一个元素被删后，队列尾指针也丢失了，因此需对队尾指针重新复制(指向头结点)
{
Q.rear = Q.front;
}
free(p);
return OK;
}
Status QueueEmpty(LinkQueue Q)//队列是否为空
{
if (Q.front == Q.rear)
{
return TRUE;
}
return FALSE;
}
