目錄：
- 一、樹的存盤結構
- （一）雙親表示法
- （二）孩子鏈表表示法（帶雙親的孩子鏈表-parent）
- （三）樹的二叉鏈表（孩子-兄弟）存盤表示法
- 二、森林與二叉樹的轉換
- （一）將樹轉換成二叉樹
- （二）將二叉樹轉換成樹
- （三）將森林轉換成二叉樹
- （四）將二叉樹轉換成森林
- 三、樹和森林的遍歷
- （一）樹的遍歷（不討論中序）
- （二）森林的遍歷（不討論后序）
一、樹的存盤結構
（一）雙親表示法
實作： 定義結構陣列來存盤樹的結點，每個結點含有兩個域：
資料域：存放結點本身資訊
雙親域：指示本結點的雙親結點在陣列中的位置
特點： 找雙親容易，找孩子難
#define MAX_TREE_SIZE 100
typedef struct PTNode
{//結點結構
ElemType data;
int parent;//保存雙親位置
}PTNode;
typedef struct
{//定義樹結構
PTNode nodes[MAX_TREE_SIZE];
int r, n;//根的位置和結點數
}PTree;
（二）孩子鏈表表示法（帶雙親的孩子鏈表-parent）
//孩子鏈表表示法的型別描述
typedef struct CTNode
{
int child;
struct CTNode* nextchild;
}*ChildPtr;
//雙親結點結構
typedef struct
{
ElemType data;
int parent;//保存雙親位置
ChildPtr firstchild;//孩子鏈的頭指標
}CTBox;
//樹結構
typedef struct
{
CTBox nodes[MAX_TREE_SIZE];
int n, r;//結點數和根結點的位置
}CTree;
（三）樹的二叉鏈表（孩子-兄弟）存盤表示法
/*樹的二叉鏈表型別描述*/
typedef struct CSNode
{
ElemType data;
struct CSNode* firstchild, * nextsibling;
}CSNode,*CSTree;
二、森林與二叉樹的轉換
（一）將樹轉換成二叉樹
加線： 在兄弟之間加一條連線
抹線： 對每個結點，除了其最左邊孩子外，去除其與其余孩子之間的關系
旋轉： 以樹的根結點為軸心，將整樹順時針旋轉45度，
樹轉換成的二叉樹，根結點的右子樹一定為空
（二）將二叉樹轉換成樹
加線： 若p結點是雙親結點的左孩子，則將P的右孩子，右孩子的右孩子·····沿著分支找到的所有右孩子，都與p的雙親用線連起來
抹線： 抹掉原二叉樹中雙親與右孩子之間的連線
調整： 將結點按層次排列，形成樹的結構
（三）將森林轉換成二叉樹
1、將各棵樹分別轉換成二叉樹
2、將每棵樹的根結點用線連接起來
3、以第一棵樹的根結點為二叉樹的根，再以根結點為核心，順時針旋轉，構成二叉樹形結構
（四）將二叉樹轉換成森林
抹線： 將二叉樹中根結點與其右孩子連線，以及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立二叉樹
還原： 將孤立的二叉樹還原成樹
三、樹和森林的遍歷
遍歷： 按照一定規律走遍樹的各個頂點，且使每個頂點僅被訪問一次，即找一個完整而有規律的走法，以得到樹中所有結點的一個線性排列
（一）樹的遍歷（不討論中序）
常用方法：
1、先根（序）遍歷：先訪問樹的根結點，然后依次先根遍歷根的每棵子樹
2、后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結點
3、按層次遍歷：先訪問第一層上的結點，然后依次遍歷第二層，·····，第N層的結點，
（二）森林的遍歷（不討論后序）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/200456.html
標籤：其他