C语言中二叉树的常见操作是什么
C语言中二叉树的常见操作是什么
这篇文章主要讲解了“C语言中二叉树的常见操作是什么”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“C语言中二叉树的常见操作是什么”吧！
一、基本概念
每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。
性质：
1、非空二叉树的第n层上至多有2^(n-1)个元素。
2、深度为h的二叉树至多有2^h-1个结点。
满二叉树：所有终端都在同一层次，且非终端结点的度数为2。
在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。
完全二叉树：除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。
对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。
二、存储结构
顺序存储：
将数据结构存在一块固定的数组中。
#defineLENGTH100typedefchardatatype;typedefstructnode{datatypedata;intlchild,rchild;intparent;}Node;Nodetree[LENGTH];intlength;introot;
虽然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。
链式存储：
typedefchardatatype;typedefstructBinNode{datatypedata;structBinNode*lchild;structBinNode*rchild;}BinNode;typedefBinNode*bintree;//bintree本身是个指向结点的指针
三、二叉树的遍历
遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点
例如：求下面树的三种遍历
前序遍历：abdefgc
中序遍历：debgfac
后序遍历：edgfbca
四、遍历的实现
递归实现(以前序遍历为例，其他的只是输出的位置稍有不同)
voidpreorder(bintreet){if(t){printf("%c",t->data);preorder(t->lchild);preorder(t->rchild);}}
非递归的实现
因为当遍历过根节点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。数量确定，以顺序栈存储。
#defineSIZE100typedefstructseqstack{bintreedata[SIZE];inttag[SIZE];//为后续遍历准备的inttop;//top为数组的下标}seqstack;voidpush(seqstack*s,bintreet){if(s->top==SIZE){printf("thestackisfull\n");}else{s->top++;s->data[s->top]=t;}}bintreepop(seqstack*s){if(s->top==-1){returnNULL;}else{s->top--;returns->data[s->top+1];}}
1、前序遍历
voidpreorder_dev(bintreet){seqstacks;s.top=-1;//因为top在这里表示了数组中的位置，所以空为-1if(!t){printf("thetreeisempty\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、中序遍历
voidmidorder(bintreet){seqstacks;s.top=-1;if(!t){printf("thetreeisempty!\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、后序遍历
因为后序遍历最后还要要访问根结点一次，所以要访问根结点两次。采取夹标志位的方法解决这个问题。
这段代码非常纠结，对自己有信心的朋友可以尝试独立写一下。反正我是写了很长时间。逻辑不难，我画了一张逻辑图：
代码：
voidpostorder_dev(bintreet){seqstacks;s.top=-1;if(!t){printf("thetreeisempty!\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、层次遍历：即每一层从左向右输出
元素需要储存有先进先出的特性，所以选用队列存储。
队列的定义：
#defineMAX1000typedefstructseqqueue{bintreedata[MAX];intfront;intrear;}seqqueue;voidenter(seqqueue*q,bintreet){if(q->rear==MAX){printf("thequeueisfull!\n");}else{q->data[q->rear]=t;q->rear++;}}bintreedel(seqqueue*q){if(q->front==q->rear){returnNULL;}else{q->front++;returnq->data[q->front-1];}}
遍历实现
voidlevel_tree(bintreet){seqqueueq;bintreetemp;q.front=q.rear=0;if(!t){printf("thetreeisempty\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、利用前序遍历的结果生成二叉树
//递归调用，不存点，想的时候只关注于一个点，因为还会回来的，不要跟踪程序运行，否则容易多加循环voidcreatetree(bintree*t){datatypec;if((c=getchar())=='#')*t=NULL;else{*t=(bintree)malloc(sizeof(BinNode));(*t)->data=c;createtree(&(*t)->lchild);createtree(&(*t)->rchild);}}
6、二叉树的查找
bintreesearch_tree(bintreet,datatypex){if(!t){returnNULL;}if(t->data==x){returnt;}else{if(!search_tree(t->lchild,x)){returnsearch_tree(t->rchild,x);}returnt;}}
7、统计结点个数
intcount_tree(bintreet){if(t){return(count_tree(t->lchild)+count_tree(t->rchild)+1);}return0;}
8、比较两个树是否相同
intis_equal(bintreet1,bintreet2){if(!t1&&!t2){//都为空就相等return1;}if(t1&&t2&&t1->data==t2->data){//有一个为空或数据不同就不判断了if(is_equal(t1->lchild,t2->lchild))if(is_equal(t1->rchild,t2->rchild)){return1;}}return0;}
9、求二叉树的深度
inthight_tree(bintreet){inth,left,right;if(!t){return0;}left=hight_tree(t->lchild);right=hight_tree(t->rchild);h=(left>right?left:right)+1;returnh;}
感谢各位的阅读，以上就是“C语言中二叉树的常见操作是什么”的内容了，经过本文的学习后，相信大家对C语言中二叉树的常见操作是什么这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是恰卡编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！
