程序员人生 网站导航

树 二叉树 多叉树

栏目:php教程时间:2015-04-10 08:38:20

本文先介绍了树的概念,然后给出了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; }


 

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐