清華大學(xué)計(jì)算機(jī)系列教材? ?累計(jì)發(fā)行超400萬(wàn)冊(cè)

嚴(yán)蔚敏 吳偉民 編著

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）?

以下是本人對(duì)該紫皮書第六章樹和二叉樹中二叉樹代碼實(shí)現(xiàn)，按遞歸方式先序和后序遍歷了二叉樹，用非遞歸的棧實(shí)現(xiàn)了中序遍歷，用隊(duì)列實(shí)現(xiàn)了層次遍歷，并且額外補(bǔ)充了二叉樹的復(fù)制、計(jì)算二叉樹的深度、計(jì)算二叉樹結(jié)點(diǎn)總數(shù)、計(jì)算二叉樹葉子結(jié)點(diǎn)總數(shù)等算法

話不多說上運(yùn)行結(jié)果

（貌似專欄把我縮進(jìn)吃了，懶得加了，另外建議用visual studio編譯，會(huì)幫你自動(dòng)調(diào)整縮進(jìn)）??

代碼如下

#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;

/*用棧實(shí)現(xiàn)非遞歸的遍歷二叉樹算法*/

#define STACK_INIT_SIZE 100//存儲(chǔ)空間初始分配量

#define STACKINCREMENT 10//存儲(chǔ)空間分配增量

typedef struct

{

SElemType* base;

SElemType* top;

int stacksize;//當(dāng)前已分配的存儲(chǔ)空間，以元素為單位

}SqStack;//用棧實(shí)現(xiàn)樹的非遞歸遍歷

Status InitStack(SqStack& S);//初始化一個(gè)空棧

Status StackEmpty(SqStack S);//判斷棧是否為空

Status Push(SqStack& S, SElemType e);//順序棧的入棧

Status Pop(SqStack& S, SElemType& e);//順序棧的出棧

/*用隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷算法*/

typedef BiTNode* QElemType;

typedef struct QNode

{

QElemType data;

struct QNode* next;

}QNode, * QueuePtr;

typedef struct

{

QueuePtr front;//隊(duì)頭指針

QueuePtr rear;//隊(duì)尾指針

}LinkQueue;

Status InitQueue(LinkQueue& Q);//鏈隊(duì)列的初始化

Status EnQueue(LinkQueue& Q, QElemType e);//入隊(duì)

Status DeQueue(LinkQueue& Q, QElemType& e);//出隊(duì)

Status QueueEmpty(LinkQueue Q);//隊(duì)列是否為空

Status CreatBiTree(BiTree& T);//按先序遍歷序列建立二叉樹的二叉鏈表

Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e));//遞歸方式實(shí)現(xiàn)前序遍歷

Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e));//用非遞歸方式--棧實(shí)現(xiàn)中序遍歷

Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e));//遞歸方式實(shí)現(xiàn)后序遍歷

Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType));//用隊(duì)列實(shí)現(xiàn)二叉樹層次遍歷

Status PrintElement(TElemType e);//打印二叉樹元素

Status CopyBiTree(BiTree T, BiTree& NewT);//復(fù)制二叉樹

int Depth(BiTree T);//計(jì)算樹的深度

int NodeCount(BiTree T);//計(jì)算二叉樹結(jié)點(diǎn)總數(shù)

int LeafCount(BiTree T);//計(jì)算二叉樹葉子結(jié)點(diǎn)總數(shù)

int main()

{

BiTree T, Same_T;

CreatBiTree(T);

printf("前序遍歷結(jié)果為：");

PreOrderTraverse(T, PrintElement);

printf("\n中序遍歷結(jié)果為：");

InOrderTraverse(T, PrintElement);

printf("\n后序遍歷結(jié)果為：");

PostOrderTraverse(T, PrintElement);

CopyBiTree(T, Same_T);

printf("\n復(fù)制后的樹按前序遍歷后的結(jié)果為：");

PreOrderTraverse(Same_T, PrintElement);

printf("\n樹的深度為：%d", Depth(T));

printf("\n樹的結(jié)點(diǎn)總數(shù)為：%d", NodeCount(T));

printf("\n數(shù)的葉子結(jié)點(diǎn)總數(shù)為：%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))//遞歸方式實(shí)現(xiàn)前序遍歷

{

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))//用非遞歸方式--棧實(shí)現(xiàn)中序遍歷

{

SqStack S;

InitStack(S);

BiTNode* p = T;

BiTNode* q = NULL;

while (p || !StackEmpty(S))

{

if (p)//如果是根節(jié)點(diǎn)

{

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))//遞歸方式實(shí)現(xiàn)后序遍歷

{

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))//用隊(duì)列實(shí)現(xiàn)二叉樹層次遍歷

{

BiTNode* p;

LinkQueue qu;

InitQueue(qu);

EnQueue(qu, T);

while (!QueueEmpty(qu))

{

DeQueue(qu, p);

Visit(p->data);

if (p->lchild)//有左孩子則進(jìn)隊(duì)

{

EnQueue(qu, p->lchild);

}

if (p->rchild)//有右孩子則進(jìn)隊(duì)

{

EnQueue(qu, p->rchild);

}

}

return OK;

}

Status PrintElement(TElemType e)//打印二叉樹元素

{

printf("%c ", e);

return OK;

}

Status CopyBiTree(BiTree T, BiTree& NewT)//復(fù)制二叉樹

{

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)//計(jì)算樹的深度

{

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)//計(jì)算二叉樹結(jié)點(diǎn)總數(shù)

/*

如果是空樹，則結(jié)點(diǎn)個(gè)數(shù)為0

否則，結(jié)點(diǎn)個(gè)數(shù)=左子樹的結(jié)點(diǎn)個(gè)數(shù)+右子樹的結(jié)點(diǎn)個(gè)數(shù)+1

*/

{

if (T == NULL)

{

return 0;

}

else

{

return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;

}

}

int LeafCount(BiTree T)//計(jì)算二叉樹葉子結(jié)點(diǎn)總數(shù)

/*

如果是空樹，則葉子結(jié)點(diǎn)個(gè)數(shù)為0

否則，葉子結(jié)點(diǎn)個(gè)數(shù)=左子樹葉子結(jié)點(diǎn)個(gè)數(shù)+右子樹葉子結(jié)點(diǎn)個(gè)數(shù)

這里不用+1，因?yàn)樽訕涞母?jié)點(diǎn)一定不是葉子結(jié)點(diǎn)

*/

{

if (T == NULL)

{

return 0;

}

if (T->lchild == NULL && T->rchild == NULL)//如果是葉子結(jié)點(diǎn)返回1

{

return 1;

}

else

{

return LeafCount(T->lchild) + LeafCount(T->rchild);

}

}

Status InitStack(SqStack& S)//初始化一個(gè)空棧

{

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)//鏈隊(duì)列的初始化

{

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)//入隊(duì)

{

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)//出隊(duì)

{

if (Q.front == Q.rear)

{

return ERROR;

}

QNode* p = Q.front->next;

e = p->data;

Q.front->next = p->next;

if (Q.rear == p)//注意這里要考慮到,當(dāng)隊(duì)列中最后一個(gè)元素被刪后，隊(duì)列尾指針也丟失了，因此需對(duì)隊(duì)尾指針重新復(fù)制(指向頭結(jié)點(diǎn))

{

Q.rear = Q.front;

}

free(p);

return OK;

}

Status QueueEmpty(LinkQueue Q)//隊(duì)列是否為空

{

if (Q.front == Q.rear)

{

return TRUE;

}

return FALSE;

}