1，二叉樹的種類
滿二叉樹
除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)的二叉樹。
完全二叉樹
一個深度為k的有n個節(jié)點(diǎn)的二叉樹，對樹中的節(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號，如果編號為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹中編號為i的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。
二叉搜索樹
二叉搜索樹(Binary Search Tree)，又名二叉排序樹(Binary Sort Tree)。
二叉搜索樹是具有有以下性質(zhì)的二叉樹：
若左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值均小于或等于它的根節(jié)點(diǎn)的值。
若右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值均大于或等于它的根節(jié)點(diǎn)的值。
左、右子樹也分別為二叉搜索樹。
平衡二叉搜索樹
平衡二叉搜索樹的任何結(jié)點(diǎn)的左子樹和右子樹高度最多相差1。，并且左右兩個子樹都是一棵平衡二叉樹。
容器map、set、multimap、multiset的底層原理都是平衡二叉搜索樹
所以map中key和set中的元素都是有序的
unordered map和unordered set的底層原理為哈希表
2，存儲方式
分為鏈?zhǔn)酱鎯途€式存儲
鏈?zhǔn)酱鎯?/h3>
鏈?zhǔn)酱鎯Ψ绞骄陀弥羔?br>
線式存儲
（用的少了解即可）
順序存儲的方式就是用數(shù)組。
線式存儲時，有一點(diǎn)i，他的左孩子下標(biāo)為2i+1，他的右孩子下標(biāo)為2i+2
3，二叉樹的遍歷
分為深度優(yōu)先搜索和廣度優(yōu)先搜索
深度優(yōu)先搜索
分為前序遍歷、中序遍歷、后續(xù)遍歷
寫法可以分為遞歸法和迭代法
遞歸的底層原理是棧
確定遞歸函數(shù)的參數(shù)和返回值
確定終止條件
確定單層遞歸的邏輯
迭代法就是模擬遞歸的過程，因?yàn)檫f歸的底層原理為棧，所以迭代法用棧展示
面試簡單的可能需要寫出簡單的非遞歸代碼
前序遍歷（遞歸法、迭代法）
中左右
遞歸法：
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
vec.push_back(cur->val); // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
迭代法：
因?yàn)槟M棧的過程，前序遍歷是中左右，但是棧是先進(jìn)后出的，所以入棧順序?yàn)橛易笾?/p>
訪問順序和處理順序相同（后續(xù)遍歷也是如此，所以稍作改動就可以變?yōu)楹罄m(xù)遍歷）
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); // 中
st.pop();
result.push_back(node->val);
if (node->right) st.push(node->right); // 右（空節(jié)點(diǎn)不入棧）
if (node->left) st.push(node->left); // 左（空節(jié)點(diǎn)不入棧）
}
return result;
}
};
中序遍歷（遞歸法、迭代法）
左中右
遞歸法：
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
traversal(cur->left, vec); // 左
vec.push_back(cur->val); // 中
traversal(cur->right, vec); // 右
}
迭代法：
訪問順序和處理順序不同，所以代碼和前后續(xù)遍歷不同
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) { // 指針來訪問節(jié)點(diǎn)，訪問到最底層
st.push(cur); // 將訪問的節(jié)點(diǎn)放進(jìn)棧
cur = cur->left; // 左
} else {
cur = st.top(); // 從棧里彈出的數(shù)據(jù)，就是要處理的數(shù)據(jù)（放進(jìn)result數(shù)組里的數(shù)據(jù)）
st.pop();
result.push_back(cur->val); // 中
cur = cur->right; // 右
}
}
return result;
}
};
后序遍歷（遞歸法、迭代法）
左右中
遞歸法：
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
vec.push_back(cur->val); // 中
}
迭代法：
訪問順序和處理順序相同
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if (root == NULL) return result;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->left) st.push(node->left); // 相對于前序遍歷，這更改一下入棧順序 （空節(jié)點(diǎn)不入棧）
if (node->right) st.push(node->right); // 空節(jié)點(diǎn)不入棧
}
reverse(result.begin(), result.end()); // 將結(jié)果反轉(zhuǎn)之后就是左右中的順序了
return result;
}
};
廣度優(yōu)先搜索
層次遍歷（迭代法、遞歸法）
借助一個隊(duì)列，保存每一層的節(jié)點(diǎn)
隊(duì)列記錄當(dāng)前層的元素個數(shù)，彈出時按隊(duì)列里儲存的個數(shù)彈出
迭代法：文章來源：http://www.zghlxwxcb.cn/news/detail-642411.html
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 這里一定要使用固定大小size，不要使用que.size()，因?yàn)閝ue.size是不斷變化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
遞歸法：文章來源地址http://www.zghlxwxcb.cn/news/detail-642411.html
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth)
{
if (cur == nullptr) return;
if (result.size() == depth) result.push_back(vector<int>());
result[depth].push_back(cur->val);
order(cur->left, result, depth + 1);
order(cur->right, result, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
return result;
}
};
4，二叉樹的定義
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
到了這里，關(guān)于【二叉樹】1-5，理論基礎(chǔ)、前中后序遍歷的遞歸法和迭代法、層序遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
