C++ 二叉树

一 树的概念

二 二叉树

满二叉树:

定义:

1
2
3
除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。

国内教程定义:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。

最后一层的节点个数等于其他层数节点个数之和+1,假设第k层,最后一层的节点个数即2*(k-1)

完全二叉树:

定义:

1
2
3
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边。

完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

二叉树的遍历

非递归写法

前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> his;
vector<int> res;
TreeNode *t = root, *dummy = new TreeNode(0);
his.push(dummy);
while(!his.empty()){
while(t){
res.push_back(t->val);
his.push(t);
t = t->left;
}
t = his.top()->right;
his.pop();
}
return res;
}
};

容易理解的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode *> st;
if(root==nullptr)
return res;
st.push(root);
while(!st.empty())
{
TreeNode* ptr = st.top();
res.push_back(ptr->val);
st.pop();
if(ptr->right)
st.push(ptr->right);
if(ptr->left)
st.push(ptr->left);
}
return res;
}
};

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
top = stack.pop() #此时左子树遍历完成
res.append(top.val) #将父节点加入列表
cur = top.right #遍历右子树
return res

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
cur = root
while stack or cur:
while cur:
res.append(cur.val)
stack.append(cur)
cur = cur.right #先将右节点压栈
top = stack.pop() #此时该节点的右子树已经全部遍历完
cur = top.left #对左子树遍历
return res[::-1] #结果翻转

统一形式

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res; //保存结果
stack<TreeNode*> st; //调用栈
if(root!=nullptr) st.push(root); //首先介入root节点
while(!st.empty()){
TreeNode *t = st.top();
st.pop(); //访问过的节点弹出
if(t!=nullptr){
if(t->right) st.push(t->right); //右节点先压栈,最后处理
if(t->left) st.push(t->left);
st.push(t); //当前节点重新压栈(留着以后处理),因为先序遍历所以最后压栈
st.push(nullptr); //在当前节点之前加入一个空节点表示已经访问过了
}else{ //空节点表示之前已经访问过了,现在需要处理除了递归之外的内容
res.push_back(st.top()->val); //st.top()是nullptr之前压栈的一个节点,也就是上面st.push(t)中的那个t
st.pop(); //处理完了,第二次弹出节点(彻底从栈中移除)
}
}
return res;
}
};
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2019-2022 guoben
  • PV: UV:

微信