一、節(jié)點的度和樹的度
- 節(jié)點的度：節(jié)點擁有的子樹數(shù)目稱為節(jié)點的度绣版，葉子節(jié)點的度為0胶台。
- 樹的度：樹內(nèi)各節(jié)點的度的最大值。
二杂抽、樹的深度和高度
- 節(jié)點n[i]的深度：從根節(jié)點到n[i]節(jié)點的唯一路徑長诈唬，即節(jié)點n[i]所在的層次(根節(jié)點為0層)。
- 樹的深度：樹中節(jié)點最大的層次缩麸。
- 節(jié)點n[i]的高度：從n[i]到葉子節(jié)點的最長路徑長铸磅，葉子節(jié)點的高度為0。
- 樹的高度：為根的高度
三杭朱、樹的遍歷方式
說明：遍歷方式都是相對于父節(jié)點而言的愚屁。
1.前序遍歷
父節(jié)點 => 左孩子 => 右孩子
image.png
2.中序遍歷
左孩子 => 父節(jié)點 =>右孩子
image.png
3.后序遍歷
左孩子 => 右孩子 => 父節(jié)點
image.png
四、二叉樹
每個節(jié)點最多只能有兩個節(jié)點痕檬。
image.png
五霎槐、完全二叉樹
設二叉樹的深度為k，除第k層外梦谜，其他各層(0 ~ k-1)的節(jié)點數(shù)都達到最大個數(shù)丘跌，第k層所有節(jié)點都連續(xù)集中在最左邊袭景。
image.png
六、滿二叉樹
如果二叉樹的層數(shù)為k闭树，且節(jié)點總數(shù)為2^(k+1) - 1耸棒，則該二叉樹就是滿二叉樹。
image.png
七报辱、二叉查找樹(Binary Search Tree与殃，BST)
左子樹上的值都小于父節(jié)點的值，右子樹上的值都大于或等于父節(jié)點的值碍现。（中序遍歷有序）
image.png
八幅疼、平衡的二叉查找樹(AVL樹)
一棵AVL樹是每個節(jié)點的左子樹和右子樹的高度最多差1的二叉查找樹。
平衡因子 = |左子樹高度 - 右子樹高度|
image.png
九昼接、總結
本章內(nèi)容只是簡單介紹了樹的一些基本概念以及一些常見的樹爽篷，關于AVL樹，紅黑樹慢睡，B樹逐工，B+樹等等會以獨立的篇章詳細說明。
