C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】
本文实例讲述了C语言二叉树常见操作。分享给大家供大家参考,具体如下:
一、基本概念
每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒。
性质:
1、非空二叉树的第n层上至多有2^(n-1)个元素。
2、深度为h的二叉树至多有2^h-1个结点。
满二叉树:所有终端都在同一层次,且非终端结点的度数为2。
在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1。
完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置。
对于完全二叉树,设一个结点为i则其父节点为i/2,2i为左子节点,2i+1为右子节点。
二、存储结构
顺序存储:
将数据结构存在一块固定的数组中。
#define LENGTH 100 typedef char datatype; typedef struct node{ datatype data; int lchild,rchild; int parent; }Node; Node tree[LENGTH]; int length; int root;
虽然在遍历速度上有一定的优势,但因所占空间比较大,是非主流二叉树。二叉树通常以链式存储。
链式存储:
typedef char datatype; typedef struct BinNode{ datatype data; struct BinNode* lchild; struct BinNode* rchild; }BinNode; typedef BinNode* bintree; //bintree本身是个指向结点的指针
三、二叉树的遍历
遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历,中序遍历,后序遍历。
前序遍历:根节点->左子树->右子树
中序遍历:左子树->根节点->右子树
后序遍历:左子树->右子树->根节点
例如:求下面树的三种遍历
前序遍历:abdefgc
中序遍历:debgfac
后序遍历:edgfbca
四、遍历的实现
递归实现(以前序遍历为例,其他的只是输出的位置稍有不同)
void preorder(bintree t){ if(t){ printf("%c ",t->data); preorder(t->lchild); preorder(t->rchild); } }
非递归的实现
因为当遍历过根节点之后还要回来,所以必须将其存起来。考虑到后进先出的特点,选用栈存储。数量确定,以顺序栈存储。
#define SIZE 100 typedef struct seqstack{ bintree data[SIZE]; int tag[SIZE]; //为后续遍历准备的 int top; //top为数组的下标 }seqstack; void push(seqstack *s,bintree t){ if(s->top == SIZE){ printf("the stack is full\n"); }else{ s->top++; s->data[s->top]=t; } } bintree pop(seqstack *s){ if(s->top == -1){ return NULL; }else{ s->top--; return s->data[s->top+1]; } }
1、前序遍历
void preorder_dev(bintree t){ seqstack s; s.top = -1; //因为top在这里表示了数组中的位置,所以空为-1 if(!t){ printf("the tree is empty\n"); }else{ while(t || s.stop != -1){ while(t){ //只要结点不为空就应该入栈保存,与其左右结点无关 printf("%c ",t->data); push(&s,t); t= t->lchild; } t=pop(&s); t=t->rchild; } } }
2、中序遍历
void midorder(bintree t){ seqstack s; s.top = -1; if(!t){ printf("the tree is empty!\n"); }else{ while(t ||s.top != -1){ while(t){ push(&s,t); t= t->lchild; } t=pop(&s); printf("%c ",t->data); t=t->rchild; } } }
3、后序遍历
因为后序遍历最后还要要访问根结点一次,所以要访问根结点两次。采取夹标志位的方法解决这个问题。
这段代码非常纠结,对自己有信心的朋友可以尝试独立写一下。反正我是写了很长时间。逻辑不难,我画了一张逻辑图:
代码:
void postorder_dev(bintree t){ seqstack s; s.top = -1; if(!t){ printf("the tree is empty!\n"); }else{ while(t || s.top != -1){ //栈空了的同时t也为空。 while(t){ push(&s,t); s.tag[s.top] = 0; //设置访问标记,0为第一次访问,1为第二次访问 t= t->lchild; } if(s.tag[s.top] == 0){ //第一次访问时,转向同层右结点 t= s.data[s.top]; //左走到底时t是为空的,必须有这步! s.tag[s.top]=1; t=t->rchild; }else { while (s.tag[s.top] == 1){ //找到栈中下一个第一次访问的结点,退出循环时并没有pop所以为其左子结点 t = pop(&s); printf("%c ",t->data); } t = NULL; //必须将t置空。跳过向左走,直接向右走 } } } }
4、层次遍历:即每一层从左向右输出
元素需要储存有先进先出的特性,所以选用队列存储。
队列的定义:
#define MAX 1000 typedef struct seqqueue{ bintree data[MAX]; int front; int rear; }seqqueue; void enter(seqqueue *q,bintree t){ if(q->rear == MAX){ printf("the queue is full!\n"); }else{ q->data[q->rear] = t; q->rear++; } } bintree del(seqqueue *q){ if(q->front == q->rear){ return NULL; }else{ q->front++; return q->data[q->front-1]; } }
遍历实现
void level_tree(bintree t){ seqqueue q; bintree temp; q.front = q.rear = 0; if(!t){ printf("the tree is empty\n"); return ; } enter(&q,t); while(q.front != q.rear){ t=del(&q); printf("%c ",t->data); if(t->lchild){ enter(&q,t->lchild); } if(t->rchild){ enter(&q,t->rchild); } } }
5、利用前序遍历的结果生成二叉树
//递归调用,不存点,想的时候只关注于一个点,因为还会回来的,不要跟踪程序运行,否则容易多加循环 void createtree(bintree *t){ datatype c; if((c=getchar()) == '#') *t = NULL; else{ *t = (bintree)malloc(sizeof(BinNode)); (*t)->data = c; createtree(&(*t)->lchild); createtree(&(*t)->rchild); } }
6、二叉树的查找
bintree search_tree(bintree t,datatype x){ if(!t){ return NULL; } if(t->data == x){ return t; }else{ if(!search_tree(t->lchild,x)){ return search_tree(t->rchild,x); } return t; } }
7、统计结点个数
int count_tree(bintree t){ if(t){ return (count_tree(t->lchild)+count_tree(t->rchild)+1); } return 0; }
8、比较两个树是否相同
int is_equal(bintree t1,bintree t2){ if(!t1 && !t2){ //都为空就相等 return 1; } if(t1 && t2 && t1->data == t2->data){ //有一个为空或数据不同就不判断了 if(is_equal(t1->lchild,t2->lchild)) if(is_equal(t1->rchild,t2->rchild)){ return 1; } } return 0; }
9、求二叉树的深度
int hight_tree(bintree t){ int h,left,right; if(!t){ return 0; } left = hight_tree(t->lchild); right = hight_tree(t->rchild); h = (left>right?left:right)+1; return h; }
希望本文所述对大家C语言程序设计有所帮助。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04