本文主要是對(duì)數(shù)據(jù)結(jié)構(gòu)中非線性結(jié)構(gòu) 樹(shù) 的學(xué)習(xí)和總結(jié)咆爽。
樹(shù)的定義
專業(yè)定義:
1.有且只有一個(gè)稱為根的節(jié)點(diǎn)
2.有若干個(gè)互不相交的子樹(shù),這些子樹(shù)本身也是一棵樹(shù)
通俗的定義:
1.樹(shù)由節(jié)點(diǎn)和邊組成
2.每一個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)但可以有多個(gè)子節(jié)點(diǎn)
3.當(dāng)有一個(gè)節(jié)點(diǎn)例外捶箱,該節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn),該節(jié)點(diǎn)稱為根節(jié)點(diǎn)
專業(yè)術(shù)語(yǔ):
節(jié)點(diǎn) 父節(jié)點(diǎn) 子節(jié)點(diǎn) 子孫 堂兄弟
深度:從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)的層數(shù)稱之為深度啤咽。 根節(jié)點(diǎn)是第一層
葉子節(jié)點(diǎn):沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)
非終端節(jié)點(diǎn): 實(shí)際就是非葉子節(jié)點(diǎn)
度: 子節(jié)點(diǎn)的個(gè)數(shù)稱為度
樹(shù)的分類
- 一般樹(shù): 任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)都不受限制讳癌。
- 二叉樹(shù):任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)最多兩個(gè),且子節(jié)點(diǎn)的個(gè)數(shù)不可更改茴她。
1. 一般二叉樹(shù)
2. 滿二叉樹(shù):在不增加樹(shù)的層數(shù)的前提下寻拂,無(wú)法再添加一個(gè)節(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)。
3. 完全二叉樹(shù):如果只是刪除了滿二叉樹(shù)最低存最右邊的若干個(gè)連續(xù)節(jié)點(diǎn)丈牢,這樣形成的二叉樹(shù)就是完全二叉樹(shù)祭钉。 - 森林:n個(gè)互不相交的樹(shù)的集合。
樹(shù)的存儲(chǔ)
二叉樹(shù)的存儲(chǔ)
連續(xù)存儲(chǔ)【完全二叉樹(shù)】
1. 優(yōu)點(diǎn): 查找某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)(也包括有沒(méi)有子節(jié)點(diǎn))赡麦。
2. 缺點(diǎn):耗用內(nèi)存空間過(guò)大朴皆。
鏈試存儲(chǔ)
1. 優(yōu)點(diǎn):耗用內(nèi)存空間小。
一般樹(shù)的存儲(chǔ)
1.雙親表示法: 求父節(jié)點(diǎn)方便泛粹。
代碼結(jié)構(gòu)定義
//樹(shù)的雙親表示法節(jié)點(diǎn)結(jié)構(gòu)的定義
#define MAX_TREE_SIZE 100
typedef int ElemType;
typedef struct PTNode {
ElemType data; //節(jié)點(diǎn)數(shù)據(jù)
int parent; //雙親位置
}PTNode;
typedef struct {
PTNode nodes[MAX_TREE_SIZE];
int r; //根的位置
int n; //節(jié)點(diǎn)數(shù)目
}PTree;
上面的樹(shù)存儲(chǔ)結(jié)構(gòu)圖根據(jù)某個(gè)節(jié)點(diǎn)的parent指針找到它的雙親節(jié)點(diǎn)遂铡,所用的時(shí)間復(fù)雜度為O(1),索引到parent的值為-1,表示找到了樹(shù)節(jié)點(diǎn)的根晶姊。如果我們要知道某個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)扒接,就的遍歷整個(gè)樹(shù)結(jié)構(gòu)了。
下面是改進(jìn)后的樹(shù)結(jié)構(gòu)存儲(chǔ)圖,可以比較方便的求出某個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)钾怔。
改進(jìn)過(guò)后的樹(shù)存儲(chǔ)結(jié)構(gòu)碱呼,沒(méi)法表示樹(shù)結(jié)構(gòu)中兄弟之間的關(guān)系?
如下是改進(jìn)過(guò)后最終的樹(shù)結(jié)構(gòu)存儲(chǔ)圖:
2.孩子表示法:求子節(jié)點(diǎn)方便宗侦, 求父節(jié)點(diǎn)麻煩愚臀。存儲(chǔ)結(jié)構(gòu)如下:
3.雙親孩子表示法:求父節(jié)點(diǎn)和子節(jié)點(diǎn)都很方便
代碼結(jié)構(gòu)如下:
#define MAX_TREE_SIZE 100
typedef char ElemType;
//孩子節(jié)點(diǎn)
typedef struct CTNode {
int child; //孩子節(jié)點(diǎn)的下標(biāo)
struct CTNode *next;//指向下一個(gè)孩子節(jié)點(diǎn)的指針
} *ChildPtr;
typedef struct {
ElemType data; //存放在樹(shù)中的節(jié)點(diǎn)的數(shù)據(jù)
int parent; //存放雙親的下標(biāo)
ChildPtr firstchild; //指向第一個(gè)孩子的指針
}CTBox;
//樹(shù)結(jié)構(gòu)
typedef struct {
CTBox nodes[MAX_TREE_SIZE]; //節(jié)點(diǎn)數(shù)組
int r, n;
};
4.二叉樹(shù)表示法:把一個(gè)普通樹(shù)轉(zhuǎn)化成二叉樹(shù)來(lái)存儲(chǔ)
具體轉(zhuǎn)換方法(把一個(gè)普通樹(shù)轉(zhuǎn)化成二叉樹(shù)):設(shè)法保證任意一個(gè)節(jié)點(diǎn)的左指針域指向他的第一個(gè)孩子,右指針域指向他的下一個(gè)兄弟矾利,只要能滿足此條件就能把一個(gè)普通的樹(shù)轉(zhuǎn)換成二叉樹(shù)姑裂,一個(gè)普通樹(shù)轉(zhuǎn)換成二叉樹(shù)一定沒(méi)有右子樹(shù)。
森林的存儲(chǔ)
先把森林轉(zhuǎn)化為二叉樹(shù)男旗,再存儲(chǔ)二叉樹(shù)
樹(shù)的操作
遍歷
先序遍歷【先訪問(wèn)根節(jié)點(diǎn)】: 先訪問(wèn)根節(jié)點(diǎn)舶斧,再先序訪問(wèn)左子樹(shù),再先序訪問(wèn)右子樹(shù)
中序遍歷【中間訪問(wèn)根節(jié)點(diǎn)】:中序遍歷左子樹(shù)察皇,再訪問(wèn)根節(jié)點(diǎn)茴厉,再中序遍歷右子樹(shù)
后序遍歷【最后訪問(wèn)根節(jié)點(diǎn)】:先中序遍歷左子樹(shù),中序遍歷右子樹(shù)什荣,再訪問(wèn)根節(jié)點(diǎn)
已知兩種遍歷序列求原始二叉樹(shù)
通過(guò)先序和中序或者中序和后序我們可以還原出原始二叉樹(shù)矾缓,但 `通過(guò)先序和后序是無(wú)法還原出原始的二叉樹(shù)`
換種說(shuō)法:只有通過(guò)先序和中序,或通過(guò)中序和后序稻爬,我們才可以唯一的確定一個(gè)二叉樹(shù)而账。
應(yīng)用
1. 樹(shù)是數(shù)據(jù)庫(kù)中數(shù)據(jù)組織一種重要的形式
2. 操作系統(tǒng)子父進(jìn)程的關(guān)系本身就是一棵樹(shù)
3. 面向?qū)ο笳Z(yǔ)言中類的繼承關(guān)系
4. 赫夫曼樹(shù)
樹(shù)的遍歷相關(guān)算法的實(shí)現(xiàn)(C語(yǔ)言)
#include <stdio.h>
#include <stdlib.h>
//定義二叉樹(shù)的節(jié)點(diǎn)
struct BTNode {
int data; //存放二叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)域
struct BTNode *pLchild; //指向左孩子結(jié)點(diǎn)的指針
struct BTNode *pRchild; //指向右孩子結(jié)點(diǎn)的指針
};
//創(chuàng)建一顆二叉樹(shù),返回頭結(jié)點(diǎn)的指針
struct BTNode *CreateBTree(void);
//先序遍歷二叉樹(shù)
void PreTraverseBTree(struct BTNode *pT);
//中序遍歷二叉樹(shù)
void InTraverseBTee(struct BTNode *pT);
//后續(xù)遍歷二叉樹(shù)
void PostTraverseBTree(struct BTNode *pT);
struct BTNode *CreateBTree(void)
{
struct BTNode * pA = (struct BTNode*)malloc(sizeof(struct BTNode));
struct BTNode * pB = (struct BTNode*)malloc(sizeof(struct BTNode));
struct BTNode * pC = (struct BTNode*)malloc(sizeof(struct BTNode));
struct BTNode * pD = (struct BTNode*)malloc(sizeof(struct BTNode));
struct BTNode * pE = (struct BTNode*)malloc(sizeof(struct BTNode));
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';
pA->pLchild = pB;
pA->pRchild = pC;
pB->pLchild = pB->pRchild = NULL;
pC->pLchild = pD;
pC->pRchild = NULL;
pD->pLchild = NULL;
pD->pRchild = pE;
pE->pLchild = pE->pRchild = NULL;
return pA;
}
void PreTraverseBTree(struct BTNode *pT) {
//先訪問(wèn)根節(jié)點(diǎn) 再先序訪問(wèn)左子樹(shù) 再先序訪問(wèn)右子樹(shù)
if (pT == NULL)
{
return;
}
printf("%c\n", pT->data);
PreTraverseBTree(pT->pLchild);
PreTraverseBTree(pT->pRchild);
}
void InTraverseBTee(struct BTNode *pT) {
//先訪問(wèn)根節(jié)點(diǎn) 再先序訪問(wèn)左子樹(shù) 再先序訪問(wèn)右子樹(shù)
if (pT == NULL)
{
return;
}
InTraverseBTee(pT->pLchild);
printf("%c\n", pT->data);
InTraverseBTee(pT->pRchild);
}
void PostTraverseBTree(struct BTNode *pT) {
//先訪問(wèn)根節(jié)點(diǎn) 再先序訪問(wèn)左子樹(shù) 再先序訪問(wèn)右子樹(shù)
if (pT == NULL)
{
return;
}
PostTraverseBTree(pT->pLchild);
PostTraverseBTree(pT->pRchild);
printf("%c\n", pT->data);
}
int main() {
struct BTNode *pT = CreateBTree();
printf("先序遍歷\n");
PreTraverseBTree(pT);
printf("中序遍歷\n");
InTraverseBTee(pT);
printf("后序遍歷\n");
PostTraverseBTree(pT);
return 0;
}