Java实现 编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两棵二叉树,并判断这两棵二叉树是否相等。
时间: 2023-11-23 18:01:08 浏览: 75
代码实现如下:
```
import java.util.Arrays;
public class BinaryTree {
private Node root;
public void buildTree(int[] preOrder, int[] inOrder) {
root = build(preOrder, inOrder);
}
private Node build(int[] preOrder, int[] inOrder) {
if (preOrder.length == 0 || inOrder.length == 0) {
return null;
}
int rootValue = preOrder[0];
Node root = new Node(rootValue);
int rootIndex = 0;
for (int i = 0; i < inOrder.length; i++) {
if (inOrder[i] == rootValue) {
rootIndex = i;
break;
}
}
root.left = build(Arrays.copyOfRange(preOrder, 1, rootIndex + 1),
Arrays.copyOfRange(inOrder, 0, rootIndex));
root.right = build(Arrays.copyOfRange(preOrder, rootIndex + 1, preOrder.length),
Arrays.copyOfRange(inOrder, rootIndex + 1, inOrder.length));
return root;
}
public boolean equals(BinaryTree other) {
return equals(root, other.root);
}
private boolean equals(Node node1, Node node2) {
if (node1 == null && node2 == null) {
return true;
}
if (node1 == null || node2 == null) {
return false;
}
if (node1.value != node2.value) {
return false;
}
return equals(node1.left, node2.left) && equals(node1.right, node2.right);
}
private static class Node {
private int value;
private Node left;
private Node right;
public Node(int value) {
this.value = value;
}
}
}
```
其中,buildTree方法根据先序遍历和中序遍历构建二叉树,equals方法判断两棵二叉树是否相等。实现时需要注意的是,先序遍历的第一个元素是根节点,通过在中序遍历中找到根节点的位置,可以将左子树和右子树的元素分别取出来,再递归构建左子树和右子树。
阅读全文