java用顺序表创建树
时间: 2024-05-14 22:14:31 浏览: 10
Java中可以使用顺序表来创建树。
1. 首先,定义一个节点类Node,包含节点值和节点在顺序表中的下标。
```java
class Node {
int value;
int index;
}
```
2. 定义顺序表ArrayList,并初始化一个根节点。
```java
ArrayList<Node> tree = new ArrayList<Node>();
Node root = new Node();
root.value = 1;
root.index = 0;
tree.add(root);
```
3. 按照树的层次遍历顺序,逐个添加节点到顺序表中。例如,添加节点2、3、4,其中2是根节点的左子节点,3是根节点的右子节点,4是2的左子节点。
```java
Node node2 = new Node();
node2.value = 2;
node2.index = 1;
tree.add(node2);
Node node3 = new Node();
node3.value = 3;
node3.index = 2;
tree.add(node3);
Node node4 = new Node();
node4.value = 4;
node4.index = 3;
tree.add(node4);
root.left = node2;
root.right = node3;
node2.left = node4;
```
4. 根据节点在顺序表中的下标,可以快速找到节点的父节点、兄弟节点、左右子节点等信息。例如,节点4的父节点是节点2,兄弟节点是节点3,左子节点为空,右子节点为空。
```java
Node node4 = tree.get(3);
Node parent4 = tree.get((node4.index - 1) / 2);
Node leftChild4 = null;
Node rightChild4 = null;
if (node4.index * 2 + 1 < tree.size()) {
leftChild4 = tree.get(node4.index * 2 + 1);
}
if (node4.index * 2 + 2 < tree.size()) {
rightChild4 = tree.get(node4.index * 2 + 2);
}
```
通过顺序表创建树可以快速查找节点的信息,同时也方便进行树的遍历等操作。