今日份分享：将树的基本操作C语言实现，主要考察树的先序，中序，后序和层次遍历方法

二叉树如图：

先序：ABCDEGF

中序：CBEGDFA

后序：CGEFDBA

层次：ABCDEFG

BiTree.h：

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_ _ _

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

② 先序遍历（递归算法）

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

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

⑤ 后序遍历（递归算法）

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>或者定义一个数组，使用循环队列即可。

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函数此处使用的是输出

Status Visit(TElemType e){printf("%c ",e);return OK;}

⑧ 计算树的节点数

Status CountNode(BiTree T,int &d){if(T){d++;CountNode(T->lchild,d);CountNode(T->rchild,d);}return OK;}

⑨ 计算树的深度

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函数：

int main(){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_ _ _

————

希望对大家有帮助，有什么C/C++学习上的问题也可以来和我交流！

写在最后：对于准备学习C/C++编程的小伙伴，如果你想更好的提升你的编程核心能力（内功）不妨从现在开始！

编程学习书籍分享：

编程学习视频分享：

整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）

欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！

对于C/C++感兴趣可以关注小编在后台私信我：【编程交流】一起来学习哦！可以领取一些C/C++的项目学习视频资料哦！已经设置好了关键词自动回复，自动领取就好了！