二叉樹的種類
?二叉樹的種類網(wǎng)上介紹的很多,這里簡(jiǎn)單用幾張圖描述一下县爬。
注意:二叉樹每個(gè)結(jié)點(diǎn)最多只有兩棵子樹阳啥,這意味著任意結(jié)點(diǎn)的度小于等于2。子樹有左右之分财喳;某個(gè)結(jié)點(diǎn)只有一個(gè)孩子時(shí)察迟,它位于左邊和右邊組成的是不同的樹斩狱。
滿二叉樹
?除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹。很顯然扎瓶,按照這個(gè)定義所踊,上面的圖示二叉樹就不是滿二叉樹。
完全二叉樹
1.滿二叉樹一定是完全二叉樹概荷,完全二叉樹不一定是滿二叉樹
- 某結(jié)點(diǎn)的度如果為1秕岛,則它只有左孩子
3.葉子結(jié)點(diǎn)只能出現(xiàn)在最后兩層(考慮樹2)
4.相同結(jié)點(diǎn)的樹中,完全二叉樹的深度最小
斜數(shù)(特殊的鏈表)
如果一棵二叉樹只有左孩子误证,則稱該樹為左斜樹继薛,類似的如果只有右孩子,就稱為右斜樹雷厂,他們統(tǒng)稱為斜樹惋增。這時(shí)候樹就演化成了鏈表。樹的深度就是樹的結(jié)點(diǎn)個(gè)數(shù)改鲫。
二叉搜索樹
二叉搜索樹是一個(gè)有序樹。
·若它的左子樹不空林束,則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值像棘;
·若它的右子樹不空,則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值壶冒;
·它的左缕题、右子樹也分別為二叉排序樹
平衡二叉搜索樹
左右兩個(gè)子樹的高度差不超過1的二叉搜索樹。
之前的map的底層實(shí)現(xiàn)就是平衡二叉搜索樹胖腾,但是unordered_map的底層實(shí)現(xiàn)是用哈希表烟零,所以map的時(shí)間復(fù)雜度是logn,而unordred_map不是咸作,unordered_map時(shí)間復(fù)雜度不穩(wěn)定锨阿,平均為O(c),取決于哈希函數(shù)记罚。極端情況下可能為O(n)
存儲(chǔ)方式
鏈?zhǔn)酱鎯?chǔ)
數(shù)組存儲(chǔ)
父節(jié)點(diǎn)的數(shù)組下表是i墅诡,那么它的左孩子就是i * 2 + 1,右孩子就是 i * 2 + 2桐智。(一般使用鏈表末早,這個(gè)看看就好了)
怎么建立一個(gè)二叉樹
先看一下怎么定義一個(gè)二叉樹
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
};
遞歸
struct TreeNode* CreateTree(vector<int>num, int n, int start)
{
if (num[start] == 0)
{
return NULL;
}
// 根
TreeNode *root = new TreeNode;
root->val = num[start];
root->left = NULL;
root->right = NULL;
// 左子樹
int lnode = 2 * start + 1;
int rnode = 2 * start + 2;
if (lnode > n - 1)
{
root->left = NULL;
}
else
{
root->left = CreateTree(num, n, lnode);
}
if (rnode > n - 1)
{
root->right = NULL;
}
else
{
root->right = CreateTree(num, n, rnode);
}
return root;
}
二叉樹的遍歷方式
1.深度優(yōu)先遍歷:先往深走,遇到葉子節(jié)點(diǎn)再往回走说庭。
2.廣度優(yōu)先遍歷:一層一層的去遍歷然磷。
·深度優(yōu)先遍歷
先序遍歷(遞歸法,迭代法)
中序遍歷(遞歸法刊驴,迭代法)
后序遍歷(遞歸法姿搜,迭代法)
·廣度優(yōu)先遍歷
層次遍歷(迭代法)
這里前中后序遍歷,其實(shí)指的就是中間節(jié)點(diǎn)的遍歷順序。
先序遍歷:中左右
中序遍歷:左中右
后序遍歷:左右中
遞歸求解先中后序遍歷
1.先序
void tree(TreeNode* root, vector<int>& vec)
{
if (root== NULL) return;
vec.push_back(cur->val); // 中
tree(root->left, vec); // 左
tree(root->right, vec); // 右
}
- 中序
void tree(TreeNode* root, vector<int>& vec)
{
if (root== NULL) return;
tree(root->left, vec); // 左
vec.push_back(root->val); // 中
tree(root->right, vec); // 右
}
3.后序
void tree(TreeNode* root, vector<int>& vec)
{
if (root== NULL) return;
tree(root->left, vec); // 左
tree(root->right, vec); // 右
vec.push_back(root->val); // 中
}
迭代法求二叉樹
這里需要用到棧痪欲,還不清楚的可以看一下我的另一篇淺談棧與隊(duì)列悦穿。
vector<int> pre(TreeNode* root)
{
stack<TreeNode*> qwe;
vector<int> result;
qwe.push(root);
while (!qwe.empty())
{
TreeNode* node = qwe.top(); // 中
qwe.pop();
if (node != NULL) result.push_back(node->val);
else
continue;
qwe.push(node->right); // 右
qwe.push(node->left); // 左
}
return result;
}
層序遍歷
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;
}