某二叉树,其 先序: {1,2,4,7,3,5,6} 中序:{4,7,2,1,5,3,6} (1)根据提供的先序和中序,使用BinaryTree.java实现二叉树,并输出二叉树的三种遍历顺序,高度、结点数; (2)画出二叉树
时间: 2024-10-22 17:08:09 浏览: 29
举例讲解C语言程序中对二叉树数据结构的各种遍历方式
首先,让我们根据给出的先序遍历序列和中序遍历序列重建这棵二叉树。二叉搜索树的特性是,左子树的所有节点值小于根节点,右子树的所有节点值大于根节点。所以我们可以利用这个规则来构建。
(1)在`BinaryTree.java`中,我们首先需要创建Node类表示二叉树节点:
```java
public class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
```
接着,我们可以创建一个函数来根据先序和中序遍历来构建二叉树:
```java
public Node buildTreeUtil(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
// ... (这里编写递归代码来构建树)
}
public void printPreorder(Node node) {
// ... (这里编写前序遍历的打印代码)
}
public void printInorder(Node node) {
// ... (这里编写中序遍历的打印代码)
}
public void printPostorder(Node node) {
// ... (这里编写后序遍历的打印代码)
}
```
然后调用这些函数:
```java
int[] preorder = {1, 2, 4, 7, 3, 5, 6};
int[] inorder = {4, 7, 2, 1, 5, 3, 6};
// 获取先序遍历长度和中序遍历开始位置
int preLen = preorder.length;
int inStart = binarySearch(inorder, preorder[0]);
// 构建树并获取高度和结点数
Node root = buildTreeUtil(preorder, inorder, 0, inStart, inEnd);
int height = getHeight(root);
int count = countNodes(root);
System.out.println("前序遍历:");
printPreorder(root);
System.out.println("中序遍历:");
printInorder(root);
System.out.println("后序遍历:");
printPostorder(root);
System.out.println("高度: " + height);
System.out.println("结点数: " + count);
```
注意,这里假设`binarySearch`是一个辅助函数用于查找数组中特定元素的位置,以及`getHeight`和`countNodes`用于计算树的高度和节点总数。
至于(2),由于这是一个文本环境,无法直接绘制二叉树。你可以参考线图的方式描述二叉树结构,例如:
- 先序遍历结果表明根是1,左子树包含2和4(4在先序遍历中紧随1之后,说明它是左孩子),右子树有7、3、5和6。
- 中序遍历表明4是左子树的根,1在其左边,2在其内部,右子树按顺序排列为5、3、6。
按照以上信息,树可以大致描绘为:
```
1
/ \
2 4
/ \ / \
7 3 5 6
```
完成上述代码后,运行它会得到相应的遍历顺序、高度和节点数。
阅读全文