数据结构之树
【摘要】
一、二叉树
二叉树是一棵树，其中每个节点都不能有多余两个儿子。
二叉树的一个性质是平均二叉树的深度要比N小的多，分析表明，这个平均深度为O(),对于特殊类型的二叉树，即二叉查找树，其深度的平均值O（logN）
二、二叉查找树
对于树中的每个节点X，它的左子树中所有的关键字值小于X的关键字，而它的右子树中所有的关键字...
一、二叉树
二叉树是一棵树，其中每个节点都不能有多余两个儿子。
二叉树的一个性质是平均二叉树的深度要比N小的多，分析表明，这个平均深度为O(![sqrt[]{N}](https://res-hd.hc-cdn.cn/ecology/9.3.187/v2_resources/ydcomm/libs/images/loading.gif)
),对于特殊类型的二叉树，即二叉查找树，其深度的平均值O（logN）
二、二叉查找树
对于树中的每个节点X，它的左子树中所有的关键字值小于X的关键字，而它的右子树中所有的关键字值大于X的关键字值。
三、二叉树的遍历
前序遍历（DLR）
前序遍历也叫做先根遍历，可记做根左右。
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
（1）访问根结点
（2）前序遍历左子树
（3）前序遍历右子树
注意的是：遍历左右子树时仍然采用前序遍历方法。
中序遍历（LDR）
中序遍历也叫做中根遍历，可记做左根右。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：
若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树。
注意的是：遍历左右子树时仍然采用中序遍历方法。
后序遍历（LRD）
后序遍历也叫做后根遍历，可记做左右根。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。即：
若二叉树为空则结束返回，否则：
（1）后序遍历左子树。
（2）后序遍历右子树。
（3）访问根结点。
注意的是：遍历左右子树时仍然采用后序遍历方法。
层次遍历
按照从上至下，从左至右的顺序遍历二叉树。
-
#include<stdio.h>
-
#include<stdlib.h>
-
#define N 9
-
int a[]={3,2,5,8,4,7,6,9,10};
-
-
//二叉树的结点类型；
-
typedef struct tree
-
{
-
int data;
-
struct tree *lchild;
-
struct tree *rchild;
-
}BitTree;
-
-
//在二叉排序树中插入查找关键字可以；
-
void Inserter(BitTree *bt,int key)
-
{
-
BitTree *parent; //表示双亲结点；
-
BitTree *head = bt;
-
BitTree *p=(BitTree *)malloc(sizeof(BitTree));
-
p->data=key; //保存结点数据；
-
p->lchild=p->rchild=NULL; //左右子树置空；
-
-
//查找需要添加的父结点，这个父结点是度为0的结点；
-
while(head)
-
{
-
parent=head;
-
if(key<head->data) //若关键字小于结点的数据；
-
head=head->lchild; //在左子树上查找；
-
else //若关键字大于结点的数据；
-
head=head->rchild; //在右子树上查找；
-
}
-
//判断添加到左子树还是右子树；
-
if(key<parent->data) //小于父结点；
-
parent->lchild=p; //添加到左子树；
-
else //大于父结点；
-
parent->rchild=p; //添加到右子树；
-
}
-
-
//n个数据在数组data[]中；
-
BitTree *Createer(BitTree *bt,int data[],int n)
-
{
-
int i=0;
-
bt=(BitTree *)malloc(sizeof(BitTree));
-
bt->data=data[0];
-
bt->lchild=bt->rchild=NULL;
-
for( i=1;i<n;i++)
-
Inserter(bt,data[i]);
-
return bt;
-
}
-
-
-
-
//前序遍历；
-
void PreOrder(BitTree *bt)
-
{
-
if(bt)
-
{
-
printf("%d ",bt->data);
-
PreOrder(bt->lchild);
-
PreOrder(bt->rchild);
-
}
-
}
-
//中序遍历；
-
void InOrder(BitTree *bt)
-
{
-
if(bt)
-
{
-
InOrder(bt->lchild);
-
printf("%d ",bt->data);
-
InOrder(bt->rchild);
-
}
-
}
-
void PostOrder(BitTree *bt){ //后序遍历
-
if(bt){
-
PostOrder(bt->lchild);
-
PostOrder(bt->rchild);
-
printf("%d ",bt->data);
-
}
-
}
-
//删除结点；
-
void Deleteer(BitTree *bt,int key)
-
{
-
BitTree *L,*LL; //在删除左右子树都有的结点时使用；
-
BitTree *p=bt;
-
BitTree *parent=bt;
-
int child=0; //0表示左子树，1表示右子树；
-
if(!bt) //如果排序树为空，则退出；
-
return ;
-
while(p) //二叉排序树有效；
-
{
-
if(p->data==key)
-
{
-
if(!p->lchild&&!p->rchild) //叶结点(左右子树都为空)；
-
{
-
if(p==bt) //被删除的结点只有根结点；
-
free(p);
-
else if(child==0)
-
{
-
parent->lchild=NULL; //设置父结点左子树为空；
-
free(p); //释放结点空间；
-
}
-
else //父结点为右子树；
-
{
-
parent->rchild=NULL; //设置父结点右子树为空；
-
free(p); //释放结点空间；
-
}
-
}
-
-
else if(!p->lchild) //左子树为空，右子树不为空；
-
{
-
if(child==0) //是父结点的左子树；
-
parent->lchild=p->rchild;
-
else //是父结点的右子树；
-
parent->rchild=p->rchild;
-
free(p); //释放被删除的结点；
-
}
-
-
else if(!p->rchild) //右子树为空，左子树不为空；
-
{
-
if(child==0) //是父结点的左子树；
-
parent->lchild=p->lchild;
-
else //是父结点的右子树；
-
parent->rchild=p->lchild;
-
free(p); //释放被删除的结点；
-
}
-
-
else
-
{
-
LL=p; //保存左子树的结点；
-
L=p->rchild; //从当前结点的右子树进行查找；
-
if(L->lchild) //左子树不为空；
-
{
-
LL=L;
-
L=L->lchild; //查找左子树；
-
p->data=L->data; //将左子树的数据保存到被删除结点；
-
LL->lchild=L->lchild; //设置父结点的左子树指针为空；
-
for(;L->lchild;L=L->lchild);
-
L->lchild=p->lchild;
-
p->lchild=NULL;
-
}
-
else
-
{
-
p->data=L->data;
-
LL->rchild=L->rchild;
-
}
-
}
-
p=NULL;
-
}
-
-
else if(key<p->data) //需删除记录的关键字小于结点的数据；
-
{
-
//要删除的结点p是parent的左子树；
-
child=0; //标记在当前结点左子树；
-
parent=p;//保存当前结点作为父结点；
-
p=p->lchild; //查找左子树；
-
}
-
-
else //需删除记录的关键字大于结点的数据；
-
{
-
//要删除的结点p是parent的右子树；
-
child=1; //标记在当前结点右子树查找；
-
parent=p; //保存当前结点作为父结点；
-
p=p->rchild; //查找右子树；
-
}
-
}
-
}
-
-
int maxDepth(BitTree* root) {
-
if (root == NULL) {
-
return 0;
-
}
-
else {
-
int maxLeft = maxDepth(root->lchild), maxRight = maxDepth(root->rchild);
-
if (maxLeft > maxRight) {
-
return 1 + maxLeft;
-
}
-
else {
-
return 1 + maxRight;
-
}
-
}
-
}
-
-
int main(void)
-
{
-
BitTree *bt; //保存二叉排序树根结点；
-
int i=0;
-
int maxdepth=0;
-
-
printf("数组数据为:\n");
-
for(i=0;i<N;i++)
-
printf("%d ",a[i]);
-
printf("\n\n");
-
-
bt=Createer(bt,a,N);
-
-
printf("遍历后的二叉排序树为(前序遍历输出):\n");
-
PreOrder(bt);
-
printf("\n\n");
-
printf("遍历后的二叉排序树为(中序遍历输出):\n");
-
InOrder(bt);
-
printf("\n\n");
-
printf("遍历后的二叉排序树为(后序遍历输出):\n");
-
PostOrder(bt);
-
printf("\n\n\n");
-
maxdepth=maxDepth(bt);
-
printf("二叉树的深度 %d\n",maxdepth);
-
printf(" **将数据8插入到二叉树中**\n\n");
-
printf("插入后的二叉树为(中序遍历输出):\n");
-
Inserter(bt,8);
-
PreOrder(bt);
-
printf("\n\n\n");
-
-
printf(" **将数据5从二叉树中删除**\n\n");
-
printf("删除后的二叉树为(中序遍历输出):\n");
-
Deleteer(bt,5); //删除拥有左右子树的结点有问题；
-
PreOrder(bt);
-
printf("\n");
-
return 0;
-
}
文章来源: xintiaobao.blog.csdn.net，作者：心跳包，版权归原作者所有，如需转载，请联系作者。
原文链接：xintiaobao.blog.csdn.net/article/details/89841463
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）