二叉树的递归
1.二叉树递归遍历
二叉树的递归序
递归序过程:
- 两个注释1之间的代码代表第一次来到一个节点的时候,会判断一下这个节点是否为空;
- 来到这个节点的左树去遍历。
- 遍历完第二次回到本函数,进行两个注释2之间进行操作,两个注释2之间可以进行某些操作也可以不进行某些操作,但是一定会返回本函数。
- 来到这个节点的右树去遍历。
- 遍历完第三次回到本函数,进行两个注释3之间进行操作,两个注释3之间可以进行某些操作也可以不进行某些操作,但是一定会返回本函数。
- 本函数结束,返回。
void traversal(TreeNode *root) {
if (root == nullptr) {
return;
}
traversal(root->left);
traversal(root->right);
}
例:进行下棵树的递归序
用递归方法进行二叉树的遍历,每个节点都会返回三次,可能每次返回的时候可能什么都没干,但一定会回到这个节点的。在递归序的基础上可以加工出二叉树的三种遍历。
①二叉树的先序遍历
对递归序第一次来到一个节点时打印,第2、3次来到一个节点什么都不做,产生的就是先序遍历。
void preOrderTraversal(TreeNode *root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
traversal(root->left);
traversal(root->right);
}
②二叉树的中序遍历
对递归序第二次来到一个节点时打印,第2、3次来到一个节点什么都不做,产生的就是先序遍历。
void midOrderTraversal(TreeNode *root) {
if (root == nullptr) {
return;
}
traversal(root->left);
cout << root->val << " ";
traversal(root->right);
}
③二叉树的后续遍历
对递归序第三次来到一个节点时打印,第2、3次来到一个节点什么都不做,产生的就是先序遍历。
void posOrderTraversal(TreeNode *root) {
if (root == nullptr) {
return;
}
traversal(root->left);
traversal(root->right);
cout << root->val << " ";
}
2.二叉树的非递归遍历
任何递归都能改成非递归,递归遍历就是系统帮你压栈,非递归就是自己压栈。
①二叉树的先序遍历
非递归的先序遍历过程为每次进行如下操作:
- 从栈中弹出一个节点cur
- 打印(处理)cur
- 如果cur有右节点,先将右节点压栈;如果cur有左节点,再将左节点压栈。
- 重复上述行为。
代码为:
void preOrderTraversal(TreeNode *root) {
if (root == nullptr) return;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode *node = st.top();
st.pop();
cout << node->val << " ";
if (root->right) {
st.push(root->right);
}
if (root->left) {
st.push(root->left);
}
}
}
②二叉树的后序遍历
非递归的中序遍历过程先准备两个栈,一个压栈,一个收集栈。为每次进行如下操作:
- 从栈中弹出一个节点cur
- cur放入收集栈
- 如果cur有左节点,先将左节点压栈;如果cur有右节点,再将右节点压栈。
- 重复上述行为。
整个过程结束之后,将收集栈节点弹出,便是后续遍历。
void posOrderTraversal(TreeNode *root) {
stack<TreeNode*> st1;
stack<TreeNode*> st2;
if (root == nullptr) return;
st1.push(root);
while (!st.empty()) {
TreeNode *node = st.top();
st.pop();
st2.push(node);
if (node->left) {
st1.push(node->left);
}
if (node->right) {
st1.push(node->right);
}
}
while (!st2.empty()) {
TreeNode *node = st2.top();
st2.pop();
cout << node->val << " ";
}
}
③中序遍历
非递归的中序遍历过程是每棵子树进行如下操作:
- 整棵树的左边界进栈。
- 依次弹出节点的过程中打印(操作),对弹出节点的右树周而复始。
代码如下:
void midOrderTraversal(TreeNode *root) {
if (root == nullptr) {
return;
}
stack<TreeNode*> st;
TreeNode *node = root;
while (!st.empty() || node) {
if (node) {
st.push(node);
node = node->left;
} else {
node = st.top();
st.pop();
cout << node->val << " ";
node = node->right;
}
}
}
3.二叉树的层序遍历
void traversal(TreeNode *root) {
queue<TreeNode*> que;
if (root == nullptr) {
return nullptr;
}
que.push(root);
while (!que.empty()) {
TreeNode *node;
node = st.top();
st.pop();
cout << node->val << " ";
if (node->left) {
que.push(node->left);
}
if (node->right) {
que.push(node->right);
}
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)