树的后根遍历
时间: 2023-06-22 22:26:30 浏览: 48
树的后根遍历(也称为后序遍历)是一种二叉树遍历方式,它的遍历顺序是先访问左子树,再访问右子树,最后访问根节点。具体实现方式可以使用递归或者栈来完成。递归实现的后序遍历代码如下:
```java
public void postOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.print(root.val + " ");
}
```
在递归实现中,如果当前节点为空,直接返回。否则,先递归遍历左子树,再递归遍历右子树,最后输出当前节点的值。
相关问题
java三叉树中根遍历
在Java中,三叉树的根遍历可以通过递归或者使用栈来实现。下面是两种实现方法:
1. 递归实现根遍历:
```java
class InThreadedBinaryTree {
// 定义树的节点
class Node {
int data;
Node left, middle, right;
public Node(int item) {
data = item;
left = middle = right = null;
}
}
Node root;
// 根遍历
public void rootTraversal(Node node) {
if (node != null) {
System.out.print(node.data + " ");
rootTraversal(node.left);
rootTraversal(node.middle);
rootTraversal(node.right);
}
}
public static void main(String[] args) {
InThreadedBinaryTree tree = new InThreadedBinaryTree();
// 构建三叉树
tree.root = tree.new Node(1);
tree.root.left = tree.new Node(3);
tree.root.middle = tree.new Node(2);
tree.root.right = tree.new Node(4);
tree.root.left.left = tree.new Node(6);
tree.root.left.middle = tree.new Node(7);
tree.root.left.right = tree.new Node(9);
tree.root.middle.left = tree.new Node(1);
tree.root.middle.middle = tree.new Node(2);
tree.root.middle.right = tree.new Node(3);
tree.root.right.left = tree.new Node(8);
// 执行根遍历
tree.rootTraversal(tree.root);
}
}
```
2. 使用栈实现根遍历:
```java
import java.util.Stack;
class InThreadedBinaryTree {
// 定义树的节点
class Node {
int data;
Node left, middle, right;
public Node(int item) {
data = item;
left = middle = right = null;
}
}
Node root;
// 根遍历
public void rootTraversal(Node node) {
if (node == null)
return;
Stack<Node> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
Node currNode = stack.pop();
System.out.print(currNode.data + " ");
if (currNode.right != null)
stack.push(currNode.right);
if (currNode.middle != null)
stack.push(currNode.middle);
if (currNode.left != null)
stack.push(currNode.left);
}
}
public static void main(String[] args) {
InThreadedBinaryTree tree = new InThreadedBinaryTree();
// 构建三叉树
tree.root = tree.new Node(1);
tree.root.left = tree.new Node(3);
tree.root.middle = tree.new Node(2);
tree.root.right = tree.new Node(4);
tree.root.left.left = tree.new Node(6);
tree.root.left.middle = tree.new Node(7);
tree.root.left.right = tree.new Node(9);
tree.root.middle.left = tree.new Node(1);
tree.root.middle.middle = tree.new Node(2);
tree.root.middle.right = tree.new Node(3);
tree.root.right.left = tree.new Node(8);
// 执行根遍历
tree.rootTraversal(tree.root);
}
}
```
c++树的先根遍历代码
以下是C++实现树的先根遍历的代码:
```c++
#include<iostream>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
void preOrder(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
preOrder(root);
return 0;
}
```
输出结果为:1 2 4 5 3 6 7