一、二叉樹的基本概念
每個(gè)結(jié)點(diǎn)最多有兩棵子樹，左子樹和右子樹，次序不可以顛倒。
性質(zhì)：
1. 非空二叉樹的第n層上至多有2^(n-1)個(gè)元素。
2. 深度為h的二叉樹至多有2^h-1個(gè)結(jié)點(diǎn)。
完全二叉樹：除了最大的層次即成為一顆滿二叉樹且層次最大那層所有的結(jié)點(diǎn)均向左靠齊，即集中在左面的位置上，不能有空位置。
對(duì)于完全二叉樹，設(shè)一個(gè)結(jié)點(diǎn)為i則其父節(jié)點(diǎn)為i/2，2i為左子節(jié)點(diǎn)，2i+1為右子節(jié)點(diǎn)。
滿二叉樹：所有終端都在同一層次，且非終端結(jié)點(diǎn)的度數(shù)為2。
在滿二叉樹中若其深度為h，則其所包含的結(jié)點(diǎn)數(shù)必為2^h-1。
二、存儲(chǔ)結(jié)構(gòu)
1.通常以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)（主流）
struct TreeNode {
datatype val;
TreeNode left,right;
TreeNode(datatype x) : val(x), left(NULL), right(NULL) {}
};
2.也有用數(shù)組的順序結(jié)構(gòu)存儲(chǔ)（非主流：速度較快，占有空間大）
struct TreeNode {
datatype val;
int left, int right;
TreeNode(datatype x) : val(x), left(NULL), right(NULL) {}
};
三、二叉樹的遍歷
遍歷即將樹的所有結(jié)點(diǎn)訪問且僅訪問一次。按照根節(jié)點(diǎn)位置的不同分為前序遍歷，中序遍歷，后序遍歷。
前序遍歷：根節(jié)點(diǎn)->左子樹->右子樹
中序遍歷：左子樹->根節(jié)點(diǎn)->右子樹
后序遍歷：左子樹->右子樹->根節(jié)點(diǎn)
總結(jié)：就是遍歷時(shí) 根節(jié)點(diǎn) 的位置不同。
例如：求下面樹的三種遍歷順序
前序:abdfegc
中序:dfebgac
后序:fedgbca
四、練習(xí)題LeetCode105 Construct Binary Tree from Preorder and Inorder Traversal
題目：給定一棵樹的前序遍歷和中序遍歷序列，構(gòu)建這棵樹。
注意：可以假定樹中不存在重復(fù)的值。
分析：
1. 前序遍歷序列第一個(gè)點(diǎn)是根結(jié)點(diǎn)x
2. 中序遍歷序列中找到這個(gè)點(diǎn)x的下標(biāo)
3. 中序遍歷序列中的x的左邊序列對(duì)應(yīng)左子樹
4. 中序遍歷序列中的x的右邊序列對(duì)應(yīng)右子樹
AC代碼：
class Solution {
public:
TreeNode* help(vector<int>& preorder, vector<int>& inorder, int fromp, int fromi, int size) {
if(size == 0) return 0;
TreeNode *root = new TreeNode(preorder[fromp]);
int i;
for(i = fromi; inorder[i] != preorder[fromp]; ++i)
;
root->left = help(preorder, inorder, fromp + 1, fromi, i - fromi);
root->right = help(preorder, inorder, fromp + 1 + i - fromi, i + 1, size - 1 - i + fromi);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return help(preorder, inorder, 0, 0, (unsigned int)preorder.size());
}
};
這里比較糾結(jié)的是遞歸的fromp和fromi，需要細(xì)心的思考。這里給出一個(gè)遞歸的樣例，假設(shè)樹是我們的這個(gè)例子，即給出的前序遍歷和中序遍歷序列的順序?yàn)椋?br>
前序:abdfegc
中序:dfebgac
函數(shù)調(diào)用的順序如下：
('-'：表示深度，HELP函數(shù)，結(jié)點(diǎn)類型，結(jié)點(diǎn)值)：
HELP(Pre, In, 0, 0, 7) root a
-HELP(Pre, In, 1, 0, 5) left b
--HELP(Pre, In, 2, 0, 3) left d
---HELP(Pre, In, 3, 0, 0) left NULL
---HELP(Pre, In, 3, 1, 2) right e
----HELP(Pre, In, 4, 1, 1) left f
-----HELP(Pre, In, 5, 1, 0) left NULL
-----HELP(Pre, In, 5, 2, 0) right NULL
----HELP(Pre, In, 5, 3, 0) right NULL
--HELP(Pre, In, 5, 4, 1) right g
---HELP(Pre, In, 6, 4, 0) left NULL
---HELP(Pre, In, 6, 5, 0) right NULL
-HELP(Pre, In, 6, 6, 1) right c
--HELP(Pre, In, 7, 6, 0) left NULL
--HELP(Pre, In, 7, 7, 0) right NULL
