JAVA中以先根次序非递归遍历二叉树的程序
时间: 2023-06-02 22:04:30 浏览: 73
以下是JAVA中以先根次序非递归遍历二叉树的程序:
```
public void preOrderTraversal(Node root) {
if (root == null) return;
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node curr = stack.pop();
System.out.print(curr.val + " ");
if (curr.right != null) stack.push(curr.right);
if (curr.left != null) stack.push(curr.left);
}
}
```
该程序使用栈实现先根次序非递归遍历二叉树。具体来说,程序首先将根节点入栈,然后循环执行以下操作:弹出栈顶节点并输出其值,将其右儿子(如果有)入栈,将其左儿子(如果有)入栈。由于先入栈左儿子,再入栈右儿子,所以在下次循环时会先访问左子树。这样,就可以实现以先根次序遍历二叉树的效果。
相关问题
JAVA中以先根次序非递归遍历二叉树
可以使用栈来实现二叉树的先根次序非递归遍历,具体的实现方法是:先将根节点入栈,然后开始循环,如果栈不为空,则弹出栈顶元素,访问该节点,并依次将其右子节点和左子节点入栈。重复执行这个循环,直到栈为空。这样就完成了二叉树的先根次序非递归遍历。
递归遍历二叉树的设计思想 非递归遍历二叉树的设计思想 不少20000字
二叉树是一种重要的数据结构,在许多算法中都有广泛的应用。二叉树的遍历是指按照某种规则依次访问二叉树中的所有节点。常用的遍历方法有前序遍历、中序遍历和后序遍历。在本文中,我们将介绍递归遍历二叉树和非递归遍历二叉树的设计思想。
一、递归遍历二叉树的设计思想
递归遍历二叉树的基本思想是将二叉树的节点拆分成两个部分:根节点和子树。对于每个节点,我们先访问它的根节点,然后分别对其左右子树进行递归遍历。具体实现过程如下:
1. 前序遍历
前序遍历的顺序是先访问根节点,然后访问左子树,最后访问右子树。代码实现如下:
```
void preOrder(TreeNode* root) {
if(root == NULL) return;
cout << root->val << " "; // 访问根节点
preOrder(root->left); // 递归遍历左子树
preOrder(root->right); // 递归遍历右子树
}
```
2. 中序遍历
中序遍历的顺序是先访问左子树,然后访问根节点,最后访问右子树。代码实现如下:
```
void inOrder(TreeNode* root) {
if(root == NULL) return;
inOrder(root->left); // 递归遍历左子树
cout << root->val << " "; // 访问根节点
inOrder(root->right); // 递归遍历右子树
}
```
3. 后序遍历
后序遍历的顺序是先访问左子树,然后访问右子树,最后访问根节点。代码实现如下:
```
void postOrder(TreeNode* root) {
if(root == NULL) return;
postOrder(root->left); // 递归遍历左子树
postOrder(root->right); // 递归遍历右子树
cout << root->val << " "; // 访问根节点
}
```
递归遍历二叉树的优点是代码简洁明了,易于理解。然而,递归遍历二叉树的缺点是可能会导致栈溢出问题。当二叉树的高度很大时,递归遍历可能会占用大量的系统栈空间,导致程序崩溃。因此,我们需要使用非递归遍历二叉树的方法来避免这个问题。
二、非递归遍历二叉树的设计思想
非递归遍历二叉树的基本思想是使用栈来模拟递归遍历的过程。在递归遍历二叉树时,系统会自动为每个递归函数分配一段栈空间,用于保存函数的局部变量和返回地址。而在非递归遍历二叉树时,我们需要手动维护一个栈来存储访问过的节点。具体实现过程如下:
1. 前序遍历
前序遍历的非递归实现可以使用一个栈来保存节点。首先将根节点入栈,然后进入循环,将栈顶节点弹出并输出,然后将右子树入栈,最后将左子树入栈。这样就可以按照前序遍历的顺序遍历二叉树。代码实现如下:
```
void preOrder(TreeNode* root) {
stack<TreeNode*> s;
if(root != NULL) s.push(root); // 根节点入栈
while(!s.empty()) {
TreeNode* node = s.top(); // 取出栈顶节点
s.pop();
cout << node->val << " "; // 输出节点值
if(node->right != NULL) s.push(node->right); // 右子树入栈
if(node->left != NULL) s.push(node->left); // 左子树入栈
}
}
```
2. 中序遍历
中序遍历的非递归实现也可以使用一个栈来保存节点。首先将根节点入栈,然后进入循环,如果栈不为空或者当前节点不为空,就执行以下步骤:将当前节点的左子树依次入栈,取出栈顶节点并输出,将当前节点指向其右子树。这样就可以按照中序遍历的顺序遍历二叉树。代码实现如下:
```
void inOrder(TreeNode* root) {
stack<TreeNode*> s;
TreeNode* node = root;
while(!s.empty() || node != NULL) {
if(node != NULL) { // 当前节点不为空,将左子树入栈
s.push(node);
node = node->left;
} else { // 当前节点为空,取出栈顶节点并输出
node = s.top();
s.pop();
cout << node->val << " ";
node = node->right; // 将当前节点指向其右子树
}
}
}
```
3. 后序遍历
后序遍历的非递归实现需要使用两个栈来保存节点。首先将根节点入栈1,然后进入循环,从栈1取出一个节点,将该节点的左右子树分别入栈1,然后将该节点入栈2。重复以上步骤,直到栈1为空。然后依次从栈2中取出节点并输出。这样就可以按照后序遍历的顺序遍历二叉树。代码实现如下:
```
void postOrder(TreeNode* root) {
stack<TreeNode*> s1, s2;
if(root != NULL) s1.push(root); // 根节点入栈1
while(!s1.empty()) {
TreeNode* node = s1.top(); // 取出栈顶节点
s1.pop();
s2.push(node); // 将节点入栈2
if(node->left != NULL) s1.push(node->left); // 左子树入栈1
if(node->right != NULL) s1.push(node->right); // 右子树入栈1
}
while(!s2.empty()) {
TreeNode* node = s2.top(); // 取出栈顶节点并输出
s2.pop();
cout << node->val << " ";
}
}
```
非递归遍历二叉树的优点是可以避免栈溢出问题,而且效率比递归遍历要高。因此,在实际的程序设计中,我们更加倾向于使用非递归遍历二叉树的方法。
总结
本文介绍了递归遍历二叉树和非递归遍历二叉树的设计思想。递归遍历二叉树的基本思想是将二叉树的节点拆分成根节点和子树,然后对每个节点进行递归遍历。非递归遍历二叉树的基本思想是使用栈来模拟递归遍历的过程,依次访问每个节点。在实际的程序设计中,我们可以根据具体的需求选择适合的遍历方式。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)