• 樹的表示：（法1）結(jié)構(gòu)+鏈表

*優(yōu)點：結(jié)構(gòu)統(tǒng)一，易于處理；

*缺點：結(jié)構(gòu)的統(tǒng)一會造成空間上的浪費，比如3n個指針域，實際只需n-1個指針域；

• 樹的表示：（法2）兒子-兄弟表示法（二叉樹）

*形式：1個結(jié)點2個指針，分別指向第1個兒子和下1個兄弟；

*優(yōu)點：結(jié)構(gòu)統(tǒng)一，且空間浪費不大[為2n-(n-1)];

*二叉樹在樹的研究中是最重要且最主要的樹；

• 二叉樹的定義

typedef struct TNode *Position; typedef Position BinTree;/*二叉樹類型*/ struct TNode /*樹結(jié)點定義*/ {ElementType Data; /*結(jié)點數(shù)據(jù)*/BinTree Left; /*指向左子樹*/BinTree Right; /*指向右子樹*/ };

*度為2的樹，且該樹有左右之分；

*特殊的二叉樹：

斜二叉樹：左斜或右斜，一條直線的鏈；

完美二叉樹（滿二叉樹）：所有結(jié)點皆滿；

完全二叉樹：（類似于滿二叉樹）上至下，左至右編號，且允許不滿，且必須從右邊開始缺子樹；

• 二叉樹的重要性質(zhì)：

*二叉樹第i層的最大結(jié)點數(shù)：2^(i-1);

*深度為K的二叉樹的最大結(jié)點總數(shù)(完美二叉樹）：[2^k]-1;

*n0:葉結(jié)點的個數(shù)，n1:度為1的非葉結(jié)點的個數(shù)，n2：度為2的非葉結(jié)點的個數(shù)，滿足：n0=n2+1;

• 二叉樹的操作集：

（1）判斷BT是否為空；

（2）按順序遍歷；

*先序遍歷：根、左子樹、右子樹

*中序遍歷：左子樹、根、右子樹

*后序遍歷：左子樹、右子樹、根

*層次遍歷：從上到下、從左到右

（3）創(chuàng)建一個二叉樹；

• 二叉樹的存儲結(jié)構(gòu)：

（1）完全二叉樹（從上到下、從左到右編號）【數(shù)組存儲】：

*非根節(jié)點的父結(jié)點的序號為i/2往下取整；

*結(jié)點的左孩子：2i；(若2i<=n)

*結(jié)點的右孩子：2i+1;(若2i+1<=n)

(2)一般的二叉樹

（可以采用上面這種順序結(jié)構(gòu)，但是會造成空間的浪費）【數(shù)組存儲】

（鏈表存儲一般二叉樹，避免浪費空間）【鏈表存儲】

?

轉(zhuǎn)載于:https://www.cnblogs.com/Bran-don/p/10452834.html

總結(jié)

以上是生活随笔為你收集整理的数据结构-树（上）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。