一． 实验目的
将树的基本操作C语言实现，主要考察树的先序，中序，后序和层次遍历。
二.主要内容
本文所使用的二叉树如图：
显然
先序：ABCDEGF
中序：CBEGDFA
后序：CGEFDBA
层次：ABCDEFG
BiTree.h内容
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
typedef char TElemType; typedef int Status; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; Status PreCreateBiTree(BiTree &T);//先序输入二叉树 Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e)); Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType e)); Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); Status Visit(TElemType e); Status GetDepth(BiTree T); Status CountNode(BiTree T,int &d); |
主要函数：
① 先序创建二叉树
注意创建的时候如果没有左右子树要输入空格
输入：ABC_ _DE_G_ _F_ _ _
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Status PreCreateBiTree(BiTree &T) { char ch; ch=getchar(); if(ch==' ')T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(OVERFLOW); T->data=ch; PreCreateBiTree(T->lchild); PreCreateBiTree(T->rchild); } return OK; } |
② 先序遍历（递归算法）
|
1 2 3 4 5 6 7 8 9 |
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; } |
③ 中序遍历（递归算法）
|
1 2 3 4 5 6 7 8 9 |
Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType e)) { if(T){ InOrderTraverse2(T->lchild,Visit); Visit(T->data); InOrderTraverse2(T->rchild,Visit); } return OK; } |
④ 中序遍历（非递归算法）
注意此处需要包含C++STL头文件include<stack>
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e)) { stack<BiTree>S; BiTree p; S.push(T); while(!S.empty()){ while(p=S.top())S.push(p->lchild); p=S.top(); S.pop(); if(!S.empty()){ p=S.top(); S.pop(); if(!Visit(p->data))return ERROR; S.push(p->rchild); } return OK; } } |
⑤ 后序遍历（递归算法）
|
1 2 3 4 5 6 7 8 9 10 |
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) { if(T){ PostOrderTraverse(T->lchild,Visit); PostOrderTraverse(T->rchild,Visit); Visit(T->data); } return OK; } |
⑥ 层次遍历（使用QUEUE）
可以包含STL<queue>或者定义一个数组，使用循环队列即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)) { BiTree p; BiTNode *Q[100]; int front,rear; front=rear=-1; rear++; Q[rear]=T; while(front!=rear){ front=(front+1)%100; p=Q[front]; Visit(p->data); if(p->lchild!=NULL){ rear=(rear+1)%100; Q[rear]=p->lchild; } if(p->rchild!=NULL){ rear=(rear+1)%100; Q[rear]=p->rchild; } } return OK; } |
⑦ Visit函数此处使用的是输出
|
1 2 3 4 5 |
Status Visit(TElemType e) { printf("%c ",e); return OK; } |
⑧ 计算树的节点数
|
1 2 3 4 5 6 7 8 9 |
Status CountNode(BiTree T,int &d) { if(T){ d++; CountNode(T->lchild,d); CountNode(T->rchild,d); } return OK; } |
⑨ 计算树的深度
|
1 2 3 4 5 6 7 8 9 10 11 |
Status GetDepth(BiTree T) { int hl,hr; if(T==NULL)return 0; else{ hl=GetDepth(T->lchild); hr=GetDepth(T->rchild); if(hl>hr)return hl+1; else return hr+1; } } |
Main函数：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
int main() { printf("16软件工程 徐奕 E21614061\n"); printf("Create\n"); BiTree T; PreCreateBiTree(T); printf("先序PreTraverse:\n"); PreOrderTraverse(T,Visit); printf("\n中序InTraverse:\n"); InOrderTraverse2(T,Visit); printf("\n后序PostTraverse:\n"); PostOrderTraverse(T,Visit); printf("\nLevelTraverse:\n"); LevelOrderTraverse(T,Visit); printf("\n"); CountNode(T,d); printf("\n节点数:%d\n",d); printf("树的深度:%d\n",GetDepth(T)); system("pause"); return 0; } |
实验小结
1. 遍历函数可以写成递归和非递归，递归函数更加简洁。
2. 层次遍历需要使用队列，可以包含C++STL<queue>或者定义一个数组，使用循环队列即可。注意每次判断时要把队列的头赋值给临时变量P，左右子树从队尾插入。
3.先序创建树时，要注意创建的时候如果没有左右子树要输入空格
输入：ABC_ _DE_G_ _F_ _ _
