二叉树先序,中序和后序遍历算法怎么用非递归的写,代码是什么
时间: 2024-06-01 11:12:16 浏览: 14
1. 二叉树先序遍历非递归算法:
先序遍历的顺序是:根节点 -> 左子树 -> 右子树
非递归算法的实现:
1.1. 创建一个栈,将根节点压入栈中
1.2. 当栈不为空时,弹出栈顶元素,访问该节点
1.3. 如果该节点的右子树不为空,将右子树压入栈中
1.4. 如果该节点的左子树不为空,将左子树压入栈中
1.5. 重复步骤1.2 ~ 1.4,直到栈为空
代码如下:
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
cout << node->val << " ";
if (node->right) s.push(node->right);
if (node->left) s.push(node->left);
}
}
2. 二叉树中序遍历非递归算法:
中序遍历的顺序是:左子树 -> 根节点 -> 右子树
非递归算法的实现:
2.1. 创建一个栈,将根节点压入栈中
2.2. 当栈不为空时,如果当前节点不为空,将当前节点压入栈中,并将当前节点设置为左子树
2.3. 如果当前节点为空,弹出栈顶元素,访问该节点,并将当前节点设置为右子树
2.4. 重复步骤2.2 ~ 2.3,直到栈为空
代码如下:
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s;
TreeNode* cur = root;
while (!s.empty() || cur != NULL) {
if (cur != NULL) {
s.push(cur);
cur = cur->left;
}
else {
TreeNode* node = s.top();
s.pop();
cout << node->val << " ";
cur = node->right;
}
}
}
3. 二叉树后序遍历非递归算法:
后序遍历的顺序是:左子树 -> 右子树 -> 根节点
非递归算法的实现:
3.1. 创建两个栈s1和s2,将根节点压入s1中
3.2. 当s1不为空时,弹出栈顶元素,将该节点压入s2中
3.3. 如果该节点的左子树不为空,将左子树压入s1中
3.4. 如果该节点的右子树不为空,将右子树压入s1中
3.5. 重复步骤3.2 ~ 3.4,直到s1为空
3.6. 将s2中的节点依次弹出并访问
代码如下:
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* node = s1.top();
s1.pop();
s2.push(node);
if (node->left) s1.push(node->left);
if (node->right) s1.push(node->right);
}
while (!s2.empty()) {
TreeNode* node = s2.top();
s2.pop();
cout << node->val << " ";
}
}