父節點表示法：

通過前面的介紹可以發現,樹中除根節點之外的每個節點都有一個父節點。為了記錄樹中節點與節點之間的父子關系，可以為每個節點增加一個parent域，用來記錄該節點的父節點。對于如下圖所示的數，可以用一個表(數組)來保存它。

下表記錄示范樹

數組索引

data

parent

0

A

-1

1

B

0

2

C

0

3

D

0

4

E

1

5

F

3

6

G

3

7

H

4

8

I

4

9

J

4

10

K

6

...

...

...

由此可見，只要用一個數組節點來保存樹里的每個節點，并讓每個節點都記錄它的父節點在數組中的索引位置即可。下面的程序實現了父節點表示法的樹：

import java.util.ArrayList;

import java.util.List;

/**

* @see 父節點表示法

* @author wb

*

* @param

*/

public class TreeParent {

public class Node {

T data;

int parent;

Node(){

}

Node(T data){

this.data = data;

}

Node(T data, int parent){

this(data);

this.parent = parent;

}

public String toString(){

return "TreeParent$Node[data = " + data + ", parent = " + parent + "]";

}

}

private final int DEFAULT_TREE_SIZE = 100;

private int treeSize = 0; //相當于容量吧

//用來記錄樹中所有的節點

private Node[] nodes;

//用來記錄樹中節點的個數

private int nodeNums;

/**

* 三種構造方法

*/

@SuppressWarnings("unchecked")

public TreeParent(){

treeSize = DEFAULT_TREE_SIZE;

nodes = new Node[treeSize];

}

public TreeParent(E element){

this();

nodes[0] = new Node(element, -1);

nodeNums ++;

}

@SuppressWarnings("unchecked")

public TreeParent(E element, int initSize){

treeSize = initSize;

nodes = new Node[treeSize];

nodes[0] = new Node(element, -1);

nodeNums ++;

}

//判斷樹是否為空

public boolean isEmpty(){

return nodes[0] == null;

}

//返回根節點

public Node root(){

return nodes[0];

}

/**

* 為指定節點添加子節點

* @param element : 數據元素

* @param parent ： 某節點(要添加子節點的節點)

*/

public void addNode(E element, Node> parent){

//找到nodes數組中第一個為null的位置并將新的節點添加到該位置

for(int i = 0; i < treeSize; i ++){

if(nodes[i] == null){

Node newNode = new Node(element, pos(parent));

nodes[i] = newNode;

nodeNums ++;

return;

}

}

throw new RuntimeException("該樹已滿，無法添加新節點！");

}

/**

* 返回指定節點的父節點

* @param node：某指定節點

* @return：返回指定節點的父節點

*/

public Node parent(Node> node){

return nodes[node.parent];

}

/**

* 返回指定節點(非葉子節點)的所有子節點

* @param node：指定節點(非葉子節點)

* @return：所有子節點

*/

public List> childen(Node> node){

List> list = new ArrayList>();

int indexParen = pos(node);

for(int i = 0; i < treeSize; i ++){

if(nodes[i] != null && nodes[i].parent == indexParen){

list.add(nodes[i]);

}

}

return list;

}

/**

* @see :deep of this tree

* @return：返回該樹的深度

*/

public int deep(){

int max = 0;

for(int i = 0; i < treeSize && nodes[i] != null; i ++){

//初始化本節點的層次

int def = 1;

//

int pindex = nodes[i].parent;

while(pindex != -1 && nodes[pindex] != null){

//

pindex = nodes[pindex].parent;

def ++;

}

if(max < def){

max = def;

}

}

return max;

}

/**

* 根據指定節點返回在節點數組中的索引位置

* @param parent:指定節點

* @return：返回指定在節點數組中的索引位置

*/

public int pos(Node> parent) {

for(int i = 0; i < treeSize; i ++){

if(parent == nodes[i]){

return i;

}

}

return -1;

}

}從上面的程序可以看出，定義樹節點時增加了一個parent域。該parent域用于保存該節點的父節點在數組中的位置索引，通過這種方法即可記錄樹中節點之間的父子關系。使用這種父節點表示法來存儲樹時，添加節點時將新節點的parent域的值設為其父節點在數組中的索引即可。下面是測試代碼：

import java.util.List;

import com.yc.tree.TreeParent;

public class TreeParentTest {

public static void main(String[] args) {

TreeParent tree = new TreeParent("root");

System.out.println("此時樹的深度為： " + tree.deep());

System.out.println();

TreeParent.Node root = tree.root();

tree.addNode("節點1", root);

tree.addNode("節點2", root);

System.out.println("此時樹的深度為： " + tree.deep());

System.out.println();

List.Node> list = tree.childen(root);

System.out.println( "根節點的第一個子節點為：" + list.get(0));

//為根節點的第一個子節點添加子節點

tree.addNode("節點3", list.get(0));

System.out.println( "此時樹的深度為： " + tree.deep());

}

}

測試結果為：

通過上面的介紹可以發現，父節點表示法的特點是，每個節點都記錄了它的父節點以至于可以快速的找到其父節點，但如果要去找每個節點的所有子節點就比較麻煩，程序要遍歷整個節點數組(盡管遍歷很快？？)。

總結

以上是生活随笔為你收集整理的java树父节点_Java基础 - 树的实现（一）父节点表示法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。