樹
- 節(jié)點(diǎn)的高度=節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最大路徑（邊數(shù)）
- 節(jié)點(diǎn)的深度=根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)所經(jīng)歷的邊的個(gè)數(shù)
- 節(jié)點(diǎn)的層數(shù)=節(jié)點(diǎn)的深度+1
- 樹的高度=根節(jié)點(diǎn)的高度
二叉樹
二叉樹笙纤，顧名思義，每個(gè)節(jié)點(diǎn)最多有兩個(gè)“叉”了讨，也就是兩個(gè)子節(jié)點(diǎn)，分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。
滿二叉樹
葉子節(jié)點(diǎn)全都在最底層，除了葉子節(jié)點(diǎn)之外见妒，每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)，這種二叉樹就叫作滿二叉樹甸陌。
完全二叉樹
葉子節(jié)點(diǎn)都在最底下兩層须揣，最后一層的葉子節(jié)點(diǎn)都靠左排列，并且除了最后一層钱豁，其他層的節(jié)點(diǎn)個(gè)數(shù)都要達(dá)到最大耻卡，這種二叉樹叫作完全二叉樹。
如何表達(dá)（或者存儲(chǔ)）一顆二叉樹寥院？
- 一種是基于指針或者引用的二叉鏈?zhǔn)酱鎯?chǔ)法
- 一種是基于數(shù)組的順序存儲(chǔ)法
二叉樹的遍歷
- 前序遍歷是指劲赠，對(duì)于樹中的任意節(jié)點(diǎn)來說涛目，先打印這個(gè)節(jié)點(diǎn)秸谢，然后再再打印它的左子樹，最后打印它的右子樹霹肝。
- 中序遍歷是指估蹄，對(duì)于樹中的任意節(jié)點(diǎn)來說，先打印它的左子樹沫换，然后再打印它本身臭蚁，最后打印它的右子樹。
- 后序遍歷是指，對(duì)于樹中的任意節(jié)點(diǎn)來說垮兑，先打印它的左子樹冷尉，然后再打印它的右子樹，最后打印這個(gè)節(jié)點(diǎn)本身系枪。
偽代碼
前序遍歷的遞推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍歷的遞推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍歷的遞推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
代碼
void preOrder(Node* root) {
if (root == null) return;
print root // 此處為偽代碼雀哨，表示打印 root 節(jié)點(diǎn)
preOrder(root->left);
preOrder(root->right);
}
void inOrder(Node* root) {
if (root == null) return;
inOrder(root->left);
print root // 此處為偽代碼，表示打印 root 節(jié)點(diǎn)
inOrder(root->right);
}
void postOrder(Node* root) {
if (root == null) return;
postOrder(root->left);
postOrder(root->right);
print root // 此處為偽代碼私爷，表示打印 root 節(jié)點(diǎn)
}
