樹的存盤結構
一 雙親表示法
使用一維陣列,每個元素有兩個域,資料域和父結點索引域
資料結構定義:
#define size 10
typedef struct
{
char data;
int parent;
} Node;
Node slist[size];
圖示:
特點:
找父結點容易，找結點 的孩子麻煩，需遍歷整張表，
二 孩子鏈表表示法
使用一維陣列存盤樹中所有節點,每個元素有兩個域資料域和第一個孩子節點的指標域
孩子節點也有兩個域分別是自身對應的索引域以及下一個孩子節點的指標域
資料結構定義:
# define MAXND 20
typedef struct bnode
{int child;
struct bnode *next;
}node,*childlink;
typedef struct
{
char data;
childlink hp;
}headnode;
headnode link[MAXND];
圖示:
特點:
查找子節點方便,查找父結點困難
雙親孩子表示法
為了接查找父結點困難的問題,可以在陣列元素中增加一個域存盤父結點的索引
資料結構定義:
# define MAXND 20
typedef struct bnode
{
int child;
struct bnode *next;
}node,*childlink;
typedef struct{
char data;
int parent; childlink hp;
}headnode;
headnode link[MAXND];
圖示:
三 孩子兄弟表示法(二叉鏈表表示法)
使用鏈表存盤樹中的節點,鏈表中每個元素有三個域分別為第一個孩子指標域,資料域,下一個兄弟指標域
節點組成:
資料結構定義:
Typedef struct tnode
{
int data;
struct tnode *son,*brother;
}*Tree;
圖示:
特點:
-
資料結構定義與二叉樹的二叉鏈表表示法安全相同,但是指標所表示的含義是不同的
-
查找父結點需遍歷鏈表
樹/森林與二叉樹之間的轉換
一般樹轉換二叉樹
轉換方法:
- 個兄弟節點之間添加連線
- 對任一節點,除最左孩子之外,抹掉該節點與其他子節點的各枝(取消連線)
- 以根節點為中心,將連線順時針轉45度
圖示:
一棵樹的孩子兄弟鏈表示法與將該樹轉為二叉樹后的二叉鏈表表示法存盤結構完全相同,僅節點中指標含義不同
設有以下樹(左),并將其轉換為二叉樹(右):
使用孩子兄弟表示法存盤以上樹得到存盤結構如圖(左)
使用二叉鏈表表示法存盤轉換后的二叉樹得到結構如圖(右)
森林轉換二叉樹
轉換方法:
- 將每棵樹轉換為對應的二叉樹
- 將第一步得到的各二叉樹的根節點看作是兄弟節點,加連線,以最左側根節點作為中心將根節點連線順時針旋轉45度
圖示:
二叉樹還原為一般樹
明確:根節點沒有右孩子的二叉樹可轉為一般樹
還原方法:
- 從根節點起
- 當前節點的左孩子和左孩子右枝上的所有節點作為當前節點的孩子節點
- 重復第一步
也是樹轉二叉樹的逆運算即以根節點為中心所有節點逆時針旋轉45度
圖示:
二叉樹還原為森林
明確:根節點有右孩子的二叉樹可轉為森林
還原方法:
- 根節點右枝上的每一個節點作為一個的根節點
- 將拆開后的二叉樹按
二叉樹還原為一般樹的方法轉換為一般樹
也是森林轉二叉樹的逆運算
圖示:
樹的遍歷
先序遍歷:先訪問根節點,然后依次先序遍歷根的每個子樹
后序遍歷:先依次遍歷每棵子樹,最后訪問根節點
層次遍歷:從上到下從左到右依次遍歷所有節點
由于子節點個數不確定所以沒有無法實作中序遍歷
示例:
上圖對應的遍歷順序
先序:ABCDE
后序:BDCEA
層次:ABCED
樹的遍歷結果與轉為二叉樹后的遍歷結果對應關系
樹 => 二叉樹
先序 == 先序
后序 == 中序
森林的遍歷
先序遍歷:依次使用先序遍歷森林中每棵樹
中序遍歷:對每棵樹按照先子后根的方式遍歷每個節點
之所以叫中序: 因為 樹的后序==樹轉二叉樹的中序
示例:
上圖對應的遍歷順序
先序:ABCDEFGHJI
中序:BCDAFEJHIG
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/45342.html
標籤：其他
上一篇：東華大學2020年程式設計競賽（同步賽） G Gaming with Mia
下一篇：冒泡排序演算法-詳解