多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > php開源 > php教程 > 樹 二叉樹 多叉樹

樹 二叉樹 多叉樹

來源:程序員人生   發布時間:2015-04-10 08:38:20 閱讀次數:3048次

本文先介紹了樹的概念,然后給出了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; }


 

生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 拍拍拍无挡视频免费全程1000 | 在线播放免费人成毛片乱码 | 他添的我好湿好爽视频 | 亚洲理论a中文字幕在线 | 精品视频中文字幕 | 在线亚洲精品自拍 | 最新国产福利在线 | 久草午夜| 成人区精品一区二区不卡亚洲 | 亚洲精品不卡视频 | 毛片破处 | 亚洲国产一区二区三区最新 | 青草超级碰碰在线视频 | www.黄色免费网站 | 亚洲精品一区二区三区网址 | 国内视频精品 | 视频网站免费观看 | 亚洲黄色色图 | 狂野欧美性猛交xxxx乱大交 | 精品视频一区二区三区四区五区 | 色尼玛亚洲综合 | 波多野结衣午夜 | 亚洲xxx视频| 欧美操片 | 国产又黄又爽又色的免费 | 亚洲欧美日韩中文字幕久久 | 国产精品视频分类一区 | 欧美巨大黑人精品videos人妖 | 龙口护士门91午夜国产在线 | 国产精品亚洲欧美大片在线看 | 国产乱码亚洲精品一区二区 | 69视频在线是免费观看 | 福利片 在线 | 国产高清一区二区 | 偷拍区自拍区 | 欧美第一区 | 欧美一级α片 | 国产亚洲精品久久久久91网站 | 天堂精品 | 羞羞色院91蜜桃在线观看 | 亚洲国产成人久久笫一页 |