当前位置: 首页 > 最新文章 > 正文

知识分享:数据结构—树的基本操作!主要遍历及其代码示例

今日份分享:将树的基本操作C语言实现,主要考察树的先序,中序,后序和层次遍历方法二叉树如图:先序:ABCDEGF中序:CBEGDFA后序:CGEFDBA层次:ABCDEFGBiTree.h:typedef char TElemType;typedef int Status;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*r

admin

今日份分享:将树的基本操作C语言实现,主要考察树的先序,中序,后序和层次遍历方法二叉树如图:先序:ABCDEGF中序:CBEGDFA后序:CGEFDBA层次:ABCDEFGBiTree.h:typedef char TElemType;typedef int Status;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;Status PreCreateBiTree;//先序输入二叉树Status PreOrderTraverse;Status InOrderTraverse1;Status InOrderTraverse2;Status PostOrderTraverse;Status LevelOrderTraverse;Status Visit;Status GetDepth;Status CountNode;主要函数:① 先序创建二叉树注意创建的时候如果没有左右子树要输入空格输入:ABC_ _DE_G_ _F_ _ _Status PreCreateBiTree{char ch;ch=getchar();ifT=NULL;else{if(!)exit;T->data=ch;PreCreateBiTree;PreCreateBiTree;}return OK;}② 先序遍历Status PreOrderTraverse{if{ifififreturn OK;return ERROR;}else return OK;}③ 中序遍历Status InOrderTraverse2{if{InOrderTraverse2;Visit;InOrderTraverse2;}return OK;}④ 中序遍历注意此处需要包含C++STL头文件includeStatus InOrderTraverse1{stackS;BiTree p;S.push;while(!注意每次判断时要把队列的

今日份分享:将树的基本操作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++的项目学习视频资料哦!已经设置好了关键词自动回复,自动领取就好了!


上一篇: installing snap snap-store(installing snap snap-store) 下一篇:酒吧里常说的“红方、黑方、蓝方”,到底是什么?
返回顶部