今天特別的興奮，起床也起得特別的早。在走之前我把電腦開了，那當(dāng)然是為了做服務(wù)器，我不知道我開學(xué)后能不能夠這樣做，因?yàn)榧依锏囊恍┮蛩亍２贿^只要能為大家服務(wù)我已經(jīng)很開心了，而且也一種強(qiáng)激的幸福感，這種幸福并不是一般的家庭幸福。我為堅(jiān)持做下去的，我也常常問一些網(wǎng)友關(guān)于這件事，他們都說只有你自己可以就行了，他們都支持我堅(jiān)持做下去。好吧，說遠(yuǎn)了離題了，我說說今天的補(bǔ)課吧。
今天的課程也令我吃了一驚，是講數(shù)據(jù)結(jié)構(gòu)里的樹。為什么隊(duì)列和堆棧都沒有講就直接講樹呢？會不會太快了一點(diǎn)，而且我們剛放完假有些人都沒有集中精神到課堂來。不過我會相信老師的選擇的，應(yīng)該有他的理由。那么就來講講樹的一些基本概念，大家都知道樹是數(shù)據(jù)結(jié)構(gòu)里的非線性結(jié)構(gòu)之一，和之前說的鏈表是完全不同的，鏈表就只有前驅(qū)和后繼結(jié)點(diǎn)，但樹就不是了，他可以有很多的結(jié)點(diǎn)，稱為分支結(jié)點(diǎn)，而且他的分支結(jié)點(diǎn)又可以有分支結(jié)點(diǎn)。因?yàn)闃浣佑|到的概念太多了，只好自己看一下書才行。樹運(yùn)用得很廣范，像我們操作系統(tǒng)里文件管理就是了，多級的目錄。二級目錄就像樹的子樹，而且子樹里可能還有很多的子樹，越往下就越多級。
我們來試試定義一個樹的結(jié)構(gòu)，一般樹都分得很隨意，所有我們這里也隨便畫一個樹來說一下?？磮D第十三天圖一我們看到圓圈就代表一個結(jié)點(diǎn)，而且頂?shù)哪莻€就是根結(jié)點(diǎn)，往下的就是子結(jié)點(diǎn)。子結(jié)點(diǎn)的上一個就是父結(jié)點(diǎn)，同一級的結(jié)點(diǎn)左右都是為兄弟結(jié)點(diǎn)。我們按照這樣的結(jié)構(gòu)定義一個，如下：
struct tree
{
int data;
struct tree *next; /*右兄弟結(jié)點(diǎn)*/
struct tree *pre; /*左兄弟結(jié)點(diǎn)*/
struct tree *up; /*父結(jié)點(diǎn)*/
struct tree *down; /*子結(jié)點(diǎn)*/
};
下面來看看如何建立一棵樹。
struct tree *p,*r;
r=(struct tree *)malloc(sizeof(struct tree)); /*建立根結(jié)點(diǎn)空間*/
r->data=3; /*根結(jié)點(diǎn)賦值*/
r->next=r->pre=r->up=NULL;
p=(struct tree *)malloc(sizeof(struct tree)); /*建立第二個結(jié)點(diǎn)*/
r->down=p; /*根結(jié)點(diǎn)的子結(jié)點(diǎn)連向新的子結(jié)點(diǎn)*/
p->data=5; /*子結(jié)點(diǎn)賦值*/
p->pre=NULL;
p->next=(struct tree *)malloc(sizeof(struct tree));
p->next->data=2;
p->next->pre=p;
:
:
:
因?yàn)榻Y(jié)點(diǎn)多而無規(guī)律性，所有這種建立方法是不能采用的，現(xiàn)在只是拿出來研究一下一棵樹是如何建立起來的。
現(xiàn)在說說另一種樹“二叉樹”。因?yàn)槎鏄渑c一般的樹結(jié)構(gòu)比較，二叉樹在結(jié)構(gòu)上更規(guī)范和更有確定性，因此，應(yīng)用也比樹更為廣泛。二叉樹與樹不同，首先二叉樹可以為空，空的二叉樹沒有結(jié)點(diǎn)；另外，在二叉樹中，結(jié)點(diǎn)的子樹是有序的，分左、右兩棵子二叉樹。
今天的課程也令我吃了一驚，是講數(shù)據(jù)結(jié)構(gòu)里的樹。為什么隊(duì)列和堆棧都沒有講就直接講樹呢？會不會太快了一點(diǎn)，而且我們剛放完假有些人都沒有集中精神到課堂來。不過我會相信老師的選擇的，應(yīng)該有他的理由。那么就來講講樹的一些基本概念，大家都知道樹是數(shù)據(jù)結(jié)構(gòu)里的非線性結(jié)構(gòu)之一，和之前說的鏈表是完全不同的，鏈表就只有前驅(qū)和后繼結(jié)點(diǎn)，但樹就不是了，他可以有很多的結(jié)點(diǎn)，稱為分支結(jié)點(diǎn)，而且他的分支結(jié)點(diǎn)又可以有分支結(jié)點(diǎn)。因?yàn)闃浣佑|到的概念太多了，只好自己看一下書才行。樹運(yùn)用得很廣范，像我們操作系統(tǒng)里文件管理就是了，多級的目錄。二級目錄就像樹的子樹，而且子樹里可能還有很多的子樹，越往下就越多級。
我們來試試定義一個樹的結(jié)構(gòu)，一般樹都分得很隨意，所有我們這里也隨便畫一個樹來說一下?？磮D第十三天圖一我們看到圓圈就代表一個結(jié)點(diǎn)，而且頂?shù)哪莻€就是根結(jié)點(diǎn)，往下的就是子結(jié)點(diǎn)。子結(jié)點(diǎn)的上一個就是父結(jié)點(diǎn)，同一級的結(jié)點(diǎn)左右都是為兄弟結(jié)點(diǎn)。我們按照這樣的結(jié)構(gòu)定義一個，如下：
struct tree
{
int data;
struct tree *next; /*右兄弟結(jié)點(diǎn)*/
struct tree *pre; /*左兄弟結(jié)點(diǎn)*/
struct tree *up; /*父結(jié)點(diǎn)*/
struct tree *down; /*子結(jié)點(diǎn)*/
};
下面來看看如何建立一棵樹。
struct tree *p,*r;
r=(struct tree *)malloc(sizeof(struct tree)); /*建立根結(jié)點(diǎn)空間*/
r->data=3; /*根結(jié)點(diǎn)賦值*/
r->next=r->pre=r->up=NULL;
p=(struct tree *)malloc(sizeof(struct tree)); /*建立第二個結(jié)點(diǎn)*/
r->down=p; /*根結(jié)點(diǎn)的子結(jié)點(diǎn)連向新的子結(jié)點(diǎn)*/
p->data=5; /*子結(jié)點(diǎn)賦值*/
p->pre=NULL;
p->next=(struct tree *)malloc(sizeof(struct tree));
p->next->data=2;
p->next->pre=p;
:
:
:
因?yàn)榻Y(jié)點(diǎn)多而無規(guī)律性，所有這種建立方法是不能采用的，現(xiàn)在只是拿出來研究一下一棵樹是如何建立起來的。
現(xiàn)在說說另一種樹“二叉樹”。因?yàn)槎鏄渑c一般的樹結(jié)構(gòu)比較，二叉樹在結(jié)構(gòu)上更規(guī)范和更有確定性，因此，應(yīng)用也比樹更為廣泛。二叉樹與樹不同，首先二叉樹可以為空，空的二叉樹沒有結(jié)點(diǎn)；另外，在二叉樹中，結(jié)點(diǎn)的子樹是有序的，分左、右兩棵子二叉樹。