树 二叉树 多叉树

本文先介绍了树的概念,然后给出了2叉树和多叉树的实现源码实例。

1、树的概念

树(本质上就使用了递归来定义的,递归就是堆栈利用,因此树离不开递归和堆栈):树是n个点的有限结合。n=0时是空树,n=1时有且唯一1个结点叫做根,n>1,其余的结点被分成m个互不相交的子集,每个子集又是1棵树。

森林

2叉树

满2叉树 深度为k,结点个数是2的k次方⑴的2叉树。
完全2叉树 深度为k,结点为n,当且仅当每个结点的编号与对应的满2叉树完全1致。

顺序存储:访问方便
链式存储:删除方便

2叉排序树:对每个结点的值都大于其左子结点,都小于其右子结点。

遍历:将非线性结构通过线性的方式表访问。利用于不同需求。
典型的有先生成2叉排序树,然后中序遍历,就实现了从小到达的输出。

前序遍历:先打印,然后左递归,最后右递归。
中序遍历:先左递归,然后打印,最后右递归。
后序遍历:先左递归,然后右递归,最后打印。
层次遍历:利用队列。左,右顺次放入队列。先左子出栈打印然后访问其子,如果存在左右顺次放入栈。然后右子出栈打印如果存在子,类推……

 

2、2叉树

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
//构造2叉树:左子树不大于根,右子树大于根。
int constructTree(int data[],int num,int tree[])
{
tree[1] = data[1];
for (int i=2;i<9;i++)
{
int j=1;
while(tree[j]!=0)
{
if (data[i]<=tree[j])//下1级2的k次方⑴(从1开始)
{
j=j*2;
}
else
{
j=j*2+1;
}
}
tree[j] = data[i];
}
for (int i=0;i<20;i++)
{
printf("%d ",tree[i]);
}
printf("
");
return 0;
}
//遍历2叉树:递归
//相对与根的位置,分为中序遍历,前序遍历,后序遍历。

//后序遍历
void ergodic1(int data[],int pos)
{
//不等于0也就是存在,那末就要寻觅左右
if (data[pos*2]!=0)//左存在则遍历
{
printf("%d ",data[pos*2]);
ergodic1(data,pos*2);
}
if (data[pos*2+1]!=0)//右存在则遍历
{
printf("%d ",data[pos*2+1]);
ergodic1(data,pos*2+1);
}
}

//中序遍历
void ergodic2(int data[],int pos)
{

//不等于0也就是存在,那末就要寻觅左右
if (data[pos*2]!=0)//左存在则遍历
{
ergodic2(data,pos*2);
}
if (data[pos]!=0)
{
printf("%d ",data[pos]);
}
if (data[pos*2+1]!=0)//右存在则遍历
{
ergodic2(data,pos*2+1);
}
}
//后序遍历
void ergodic3(int data[],int pos)
{
//不等于0也就是存在,那末就要寻觅左右
if (data[pos*2]!=0)//左存在则遍历
{
ergodic3(data,pos*2);
printf("%d ",data[pos*2]);
}
if (data[pos*2+1]!=0)//右存在则遍历
{
ergodic3(data,pos*2+1);
printf("%d ",data[pos*2+1]);
}
}

int main()
{
int data[100] = {0,6,3,9,2,5,7,8,4,2};
int num = 9;
int tree[100] = {0};
constructTree(data,num,tree);

ergodic1(tree,0);
printf("
");
ergodic2(tree,0);
printf("
");
ergodic3(tree,0);
printf("
");
}

 

3、多叉树-寻觅共同的先人

//寻觅共同的先人

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct ST_TREE TREE;
struct ST_TREE {
int deep;
char name[200];
int nextNum;
int next[200];
TREE *father;
};
void tree_init(TREE *tree)
{
tree->deep = 0;//头结点
memset(tree->name,0,200);
tree->nextNum = 0;
memset(tree->next,0,200);
tree->father = NULL;
}

void tree_insert(TREE *tree0,TREE *tree)
{
tree->father = tree0;
tree->deep = tree0->deep+1;
tree0->next[tree0->nextNum++]=(int)tree;
}
// TREE *tree_getChild(TREE *tree0,int no)
// {
// return (TREE *)tree0->next[no];
// }

//单独设立头结点
TREE header;

TREE *getChild(TREE *father,char *name)
{

TREE *current = father;
if (strcmp(name,"")==0)
{
return current;
}
//特别注意在递归的进程中,不能混淆不同层变量的值。此处不管current怎样变,每次循环都要来源于原来的current,也就是后来的f
int num = current->nextNum;
TREE *f = current;
for (int i=0;i<num;i++)
{
current = (TREE *)f->next[i];
if (strcmp(name,current->name)==0)
{
return current;
}
else
{
TREE *c = getChild(current,name);
if (c)
{
return c;
}
}
}
return NULL;
}

void insertPC(char *fatherName,char *sonName)
{
TREE *f = getChild(&header,fatherName);
if(f)
{
TREE *son = (TREE *)malloc(sizeof(TREE));
tree_init(son);
strcat(son->name,sonName);
tree_insert(f,son);
}
else
{
insertPC("",fatherName);//插入头结点
insertPC(fatherName,sonName);
}
}

//寻觅共同的先人:比较深度
TREE *getAncestor(char *a,char *b)
{
TREE *aTree = getChild(&header,a);
TREE *bTree = getChild(&header,b);
while(true)
{
if (aTree->father==NULL || bTree->father==NULL)
{
break;
}
// if (strcmp(aTree->name,"")==0 || strcmp(aTree->name,"")==0)
// {
// break;
// }
if(aTree->deep>bTree->deep)
{
aTree = aTree->father;
}
else if(bTree->deep>aTree->deep)
{
bTree = bTree->father;
}
else
{
if (strcmp(aTree->father->name,bTree->father->name)!=0)
{
aTree = aTree->father;
bTree = bTree->father;
}
else
{
return aTree->father;
}
}
}
return NULL;
}

int main(void)
{
tree_init(&header);
insertPC("a","b");
insertPC("b","d");
insertPC("a","c");
insertPC("c","e");
insertPC("e","f");

// TREE *t = getChild(&header,"f");
// printf("%s",t->name);

TREE *ancestor = getAncestor("d","f");
printf("%s",ancestor->name);

return 0;
}

 

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 树 二叉树 多叉树

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡