实验目的:掌握二叉树的构建及遍历操作。 实验内容:按先序遍历的顺序“ABDGCEF”构建的二叉树实现先序、中序和后序遍历,并输出对应的遍历序列。 实验要求: 1、构建一个二叉链表存储结构的二叉树。 2、基于上述构建的二叉树进行先序、中序和后序遍历操作。用Java实现
时间: 2023-11-22 17:53:42 浏览: 93
实验代码如下:
```java
// 定义二叉树节点类
class TreeNode {
char data;
TreeNode left;
TreeNode right;
public TreeNode(char data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree {
// 先序遍历
public static void preOrder(TreeNode node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
// 中序遍历
public static void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
// 后序遍历
public static void postOrder(TreeNode node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data + " ");
}
public static void main(String[] args) {
// 构建二叉树
TreeNode root = new TreeNode('A');
root.left = new TreeNode('B');
root.right = new TreeNode('C');
root.left.left = new TreeNode('D');
root.left.right = new TreeNode('G');
root.right.left = new TreeNode('E');
root.right.right = new TreeNode('F');
// 先序遍历并输出
System.out.print("先序遍历:");
preOrder(root);
System.out.println();
// 中序遍历并输出
System.out.print("中序遍历:");
inOrder(root);
System.out.println();
// 后序遍历并输出
System.out.print("后序遍历:");
postOrder(root);
System.out.println();
}
}
```
输出结果为:
```
先序遍历:A B D G C E F
中序遍历:D B G A E C F
后序遍历:D G B E F C A
```
阅读全文