樹 二叉樹 多叉樹
來源：程序員人生 發(fā)布時(shí)間：2015-04-10 08:38:20 閱讀次數(shù)：3053次
本文先介紹了樹的概念，然后給出了2叉樹和多叉樹的實(shí)現(xiàn)源碼實(shí)例。
1、樹的概念
樹（本質(zhì)上就使用了遞歸來定義的，遞歸就是堆棧利用，因此樹離不開遞歸和堆棧）：樹是n個(gè)點(diǎn)的有限結(jié)合。n=0時(shí)是空樹，n=1時(shí)有且唯一1個(gè)結(jié)點(diǎn)叫做根，n>1，其余的結(jié)點(diǎn)被分成m個(gè)互不相交的子集，每個(gè)子集又是1棵樹。
森林
2叉樹
滿2叉樹 深度為k，結(jié)點(diǎn)個(gè)數(shù)是2的k次方⑴的2叉樹。
完全2叉樹 深度為k，結(jié)點(diǎn)為n，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)與對(duì)應(yīng)的滿2叉樹完全1致。
順序存儲(chǔ)：訪問方便
鏈?zhǔn)酱鎯?chǔ)：刪除方便
2叉排序樹：對(duì)每個(gè)結(jié)點(diǎn)的值都大于其左子結(jié)點(diǎn)，都小于其右子結(jié)點(diǎn)。
遍歷：將非線性結(jié)構(gòu)通過線性的方式表訪問。利用于不同需求。
典型的有先生成2叉排序樹，然后中序遍歷，就實(shí)現(xiàn)了從小到達(dá)的輸出。
前序遍歷：先打印，然后左遞歸，最后右遞歸。
中序遍歷：先左遞歸，然后打印，最后右遞歸。
后序遍歷：先左遞歸，然后右遞歸，最后打印。
層次遍歷：利用隊(duì)列。左，右順次放入隊(duì)列。先左子出棧打印然后訪問其子，如果存在左右順次放入棧。然后右子出棧打印如果存在子，類推……
2、2叉樹
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
//構(gòu)造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級(jí)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叉樹：遞歸
//相對(duì)與根的位置，分為中序遍歷，前序遍歷，后序遍歷。
//后序遍歷
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;//頭結(jié)點(diǎn)
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];
// }
//單獨(dú)設(shè)立頭結(jié)點(diǎn)
TREE header;
TREE *getChild(TREE *father,char *name)
{
TREE *current = father;
if (strcmp(name,"")==0)
{
return current;
}
//特別注意在遞歸的進(jìn)程中，不能混淆不同層變量的值。此處不管current怎樣變，每次循環(huán)都要來源于原來的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);//插入頭結(jié)點(diǎn)
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;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
