实验目的:掌握二叉树的构建及遍历操作。 实验内容:按先序遍历的顺序构建的二叉树实现先序、中序和后序遍历,并输出对应的遍历序列,节点要用字母表示。 实验要求: 1、构建一个二叉链表存储结构的二叉树。 2、基于上述构建的二叉树进行先序、中序和后序遍历操作。用Java实现
时间: 2023-11-22 16:54:22 浏览: 146
以下是Java实现的代码:
```java
class TreeNode {
char val;
TreeNode left;
TreeNode right;
TreeNode(char val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class BinaryTree {
private TreeNode root;
public BinaryTree(char[] arr) {
root = buildTree(arr, 0);
}
private TreeNode buildTree(char[] arr, int i) {
if (i >= arr.length || arr[i] == '#') {
return null;
}
TreeNode node = new TreeNode(arr[i]);
node.left = buildTree(arr, 2 * i + 1);
node.right = buildTree(arr, 2 * i + 2);
return node;
}
public void preOrderTraversal() {
preOrderTraversal(root);
System.out.println();
}
private void preOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.val + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
public void inOrderTraversal() {
inOrderTraversal(root);
System.out.println();
}
private void inOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.left);
System.out.print(node.val + " ");
inOrderTraversal(node.right);
}
public void postOrderTraversal() {
postOrderTraversal(root);
System.out.println();
}
private void postOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(node.val + " ");
}
public static void main(String[] args) {
char[] arr = {'A', 'B', 'C', 'D', 'E', '#', 'F', '#', '#', 'G', 'H'};
BinaryTree tree = new BinaryTree(arr);
System.out.println("Pre-order traversal: ");
tree.preOrderTraversal();
System.out.println("In-order traversal: ");
tree.inOrderTraversal();
System.out.println("Post-order traversal: ");
tree.postOrderTraversal();
}
}
```
在这个例子中,我们首先定义了一个 `TreeNode` 类来表示二叉树的节点。节点具有一个值和两个子节点(左节点和右节点)。
然后,我们定义了 `BinaryTree` 类来表示整个二叉树。我们使用先序遍历的方式来构造二叉树,即从根节点开始,先访问根节点,然后递归构建左子树和右子树。
在 `BinaryTree` 类中,我们实现了三种不同的遍历方式:先序遍历、中序遍历和后序遍历。我们使用递归的方式来遍历整个二叉树,并将遍历结果输出到控制台上。在 `main` 方法中,我们创建了一个二叉树,并使用三种不同的遍历方式来输出遍历结果。
以上就是二叉树的构建及遍历操作的Java实现。
阅读全文