您好,登錄后才能下訂單哦!
一、樹(shù)
樹(shù)與線性表、棧、隊(duì)列等線性結(jié)構(gòu)不同,樹(shù)是一種非線性結(jié)構(gòu)。
一棵樹(shù)只有一個(gè)根節(jié)點(diǎn),如果一棵樹(shù)有了多個(gè)根節(jié)點(diǎn),那它已經(jīng)不再是一棵樹(shù)了,而是多棵樹(shù)的集合,也被稱為森林。
二、樹(shù)的父節(jié)點(diǎn)表示法
樹(shù)中除根節(jié)點(diǎn)之外每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn),為了記錄樹(shù)中節(jié)點(diǎn)與節(jié)點(diǎn)之間的父子關(guān)系,可以為每個(gè)節(jié)點(diǎn)增加一個(gè)parent域,用以記錄該節(jié)點(diǎn)的父節(jié)點(diǎn)。
package com.ietree.basic.datastructure.tree; import java.util.ArrayList; import java.util.List; /** * Created by ietree * 2017/4/30 */ public class TreeParent<E> { public static class Node<T> { T data; // 保存其父節(jié)點(diǎn)的位置 int parent; public Node() { } public Node(T data) { this.data = data; } public Node(T data, int parent) { this.data = 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; // 使用一個(gè)Node[]數(shù)組來(lái)記錄該樹(shù)里的所有節(jié)點(diǎn) private Node<E>[] nodes; // 記錄樹(shù)的節(jié)點(diǎn)數(shù) private int nodeNums; // 以指定節(jié)點(diǎn)創(chuàng)建樹(shù) public TreeParent(E data) { treeSize = DEFAULT_TREE_SIZE; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data, -1); nodeNums++; } // 以指定根節(jié)點(diǎn)、指定treeSize創(chuàng)建樹(shù) public TreeParent(E data, int treeSize) { this.treeSize = treeSize; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data, -1); nodeNums++; } // 為指定節(jié)點(diǎn)添加子節(jié)點(diǎn) public void addNode(E data, Node parent) { for (int i = 0; i < treeSize; i++) { // 找到數(shù)組中第一個(gè)為null的元素,該元素保存新節(jié)點(diǎn) if (nodes[i] == null) { // 創(chuàng)建新節(jié)點(diǎn),并用指定的數(shù)組元素保存它 nodes[i] = new Node(data, pos(parent)); nodeNums++; return; } } throw new RuntimeException("該樹(shù)已滿,無(wú)法添加新節(jié)點(diǎn)"); } // 判斷樹(shù)是否為空 public boolean empty() { // 根結(jié)點(diǎn)是否為null return nodes[0] == null; } // 返回根節(jié)點(diǎn) public Node<E> root() { // 返回根節(jié)點(diǎn) return nodes[0]; } // 返回指定節(jié)點(diǎn)(非根結(jié)點(diǎn))的父節(jié)點(diǎn) public Node<E> parent(Node node) { // 每個(gè)節(jié)點(diǎn)的parent記錄了其父節(jié)點(diǎn)的位置 return nodes[node.parent]; } // 返回指定節(jié)點(diǎn)(非葉子節(jié)點(diǎn))的所有子節(jié)點(diǎn) public List<Node<E>> children(Node parent) { List<Node<E>> list = new ArrayList<Node<E>>(); for (int i = 0; i < treeSize; i++) { // 如果當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的位置等于parent節(jié)點(diǎn)的位置 if (nodes[i] != null && nodes[i].parent == pos(parent)) { list.add(nodes[i]); } } return list; } // 返回該樹(shù)的深度 public int deep() { // 用于記錄節(jié)點(diǎn)的最大深度 int max = 0; for (int i = 0; i < treeSize && nodes[i] != null; i++) { // 初始化本節(jié)點(diǎn)的深度 int def = 1; // m 記錄當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的位置 int m = nodes[i].parent; // 如果其父節(jié)點(diǎn)存在 while (m != -1 && nodes[m] != null) { // 向上繼續(xù)搜索父節(jié)點(diǎn) m = nodes[m].parent; def++; } if (max < def) { max = def; } } return max; } // 返回包含指定值的節(jié)點(diǎn) public int pos(Node node) { for (int i = 0; i < treeSize; i++) { // 找到指定節(jié)點(diǎn) if (nodes[i] == node) { return i; } } return -1; } }
測(cè)試類:
package com.ietree.basic.datastructure.tree; import java.util.List; /** * Created by ietree * 2017/4/30 */ public class treeParentTest { public static void main(String[] args) { TreeParent<String> tp = new TreeParent<String>("root"); TreeParent.Node root = tp.root(); System.out.println(root); tp.addNode("節(jié)點(diǎn)1", root); System.out.println("此樹(shù)的深度:" + tp.deep()); tp.addNode("節(jié)點(diǎn)2", root); // 獲取根節(jié)點(diǎn)的所有子節(jié)點(diǎn) List<TreeParent.Node<String>> nodes = tp.children(root); System.out.println("根節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn):" + nodes.get(0)); // 為根節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)新增一個(gè)子節(jié)點(diǎn) tp.addNode("節(jié)點(diǎn)3", nodes.get(0)); System.out.println("此樹(shù)的深度:" + tp.deep()); } }
程序輸出:
TreeParent$Node[data=root, parent=-1]
此樹(shù)的深度:2
根節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn):TreeParent$Node[data=節(jié)點(diǎn)1, parent=0]
此樹(shù)的深度:3
三、子節(jié)點(diǎn)鏈表示法
讓父節(jié)點(diǎn)記住它的所有子節(jié)點(diǎn)。
package com.ietree.basic.datastructure.tree; import java.util.ArrayList; import java.util.List; /** * Created by ietree * 2017/4/30 */ public class TreeChild<E> { private static class SonNode { // 記錄當(dāng)前節(jié)點(diǎn)的位置 private int pos; private SonNode next; public SonNode(int pos, SonNode next) { this.pos = pos; this.next = next; } } public static class Node<T> { T data; // 記錄第一個(gè)子節(jié)點(diǎn) SonNode first; public Node(T data) { this.data = data; this.first = null; } public String toString() { if (first != null) { return "TreeChild$Node[data=" + data + ", first=" + first.pos + "]"; } else { return "TreeChild$Node[data=" + data + ", first=-1]"; } } } private final int DEFAULT_TREE_SIZE = 100; private int treeSize = 0; // 使用一個(gè)Node[]數(shù)組來(lái)記錄該樹(shù)里的所有節(jié)點(diǎn) private Node<E>[] nodes; // 記錄節(jié)點(diǎn)數(shù) private int nodeNums; // 以指定根節(jié)點(diǎn)創(chuàng)建樹(shù) public TreeChild(E data) { treeSize = DEFAULT_TREE_SIZE; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data); nodeNums++; } // 以指定根節(jié)點(diǎn)、指定treeSize創(chuàng)建樹(shù) public TreeChild(E data, int treeSize) { this.treeSize = treeSize; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data); nodeNums++; } // 為指定節(jié)點(diǎn)添加子節(jié)點(diǎn) public void addNode(E data, Node parent) { for (int i = 0; i < treeSize; i++) { // 找到數(shù)組中第一個(gè)為null的元素,該元素保存新節(jié)點(diǎn) if (nodes[i] == null) { // 創(chuàng)建新節(jié)點(diǎn),并用指定數(shù)組元素保存它 nodes[i] = new Node(data); if (parent.first == null) { parent.first = new SonNode(i, null); } else { SonNode next = parent.first; while (next.next != null) { next = next.next; } next.next = new SonNode(i, null); } nodeNums++; return; } } throw new RuntimeException("該樹(shù)已滿,無(wú)法添加新節(jié)點(diǎn)"); } // 判斷樹(shù)是否為空 public boolean empty() { // 根結(jié)點(diǎn)是否為null return nodes[0] == null; } // 返回根節(jié)點(diǎn) public Node<E> root() { // 返回根節(jié)點(diǎn) return nodes[0]; } // 返回指定節(jié)點(diǎn)(非葉子節(jié)點(diǎn))的所有子節(jié)點(diǎn) public List<Node<E>> children(Node parent) { List<Node<E>> list = new ArrayList<Node<E>>(); // 獲取parent節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn) SonNode next = parent.first; // 沿著孩子鏈不斷搜索下一個(gè)孩子節(jié)點(diǎn) while (next != null) { // 添加孩子鏈中的節(jié)點(diǎn) list.add(nodes[next.pos]); next = next.next; } return list; } // 返回指定節(jié)點(diǎn)(非葉子節(jié)點(diǎn))的第index個(gè)子節(jié)點(diǎn) public Node<E> child(Node parent, int index) { // 獲取parent節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn) SonNode next = parent.first; // 沿著孩子鏈不斷搜索下一個(gè)孩子節(jié)點(diǎn) for (int i = 0; next != null; i++) { if (index == i) { return nodes[next.pos]; } next = next.next; } return null; } // 返回該樹(shù)的深度 public int deep() { // 獲取該樹(shù)的深度 return deep(root()); } // 這是一個(gè)遞歸方法:每棵子樹(shù)的深度為其所有子樹(shù)的最大深度 + 1 private int deep(Node node) { if (node.first == null) { return 1; } else { // 記錄其所有子樹(shù)的最大深度 int max = 0; SonNode next = node.first; // 沿著孩子鏈不斷搜索下一個(gè)孩子節(jié)點(diǎn) while (next != null) { // 獲取以其子節(jié)點(diǎn)為根的子樹(shù)的深度 int tmp = deep(nodes[next.pos]); if (tmp > max) { max = tmp; } next = next.next; } // 最后,返回其所有子樹(shù)的最大深度 + 1 return max + 1; } } // 返回包含指定值得節(jié)點(diǎn) public int pos(Node node) { for (int i = 0; i < treeSize; i++) { // 找到指定節(jié)點(diǎn) if (nodes[i] == node) { return i; } } return -1; } }
測(cè)試類:
package com.ietree.basic.datastructure.tree; import java.util.List; /** * Created by ietree * 2017/4/30 */ public class TreeChildTest { public static void main(String[] args) { TreeChild<String> tp = new TreeChild<String>("root"); TreeChild.Node root = tp.root(); System.out.println(root); tp.addNode("節(jié)點(diǎn)1", root); tp.addNode("節(jié)點(diǎn)2", root); tp.addNode("節(jié)點(diǎn)3", root); System.out.println("添加子節(jié)點(diǎn)后的根結(jié)點(diǎn):" + root); System.out.println("此樹(shù)的深度:" + tp.deep()); // 獲取根節(jié)點(diǎn)的所有子節(jié)點(diǎn) List<TreeChild.Node<String>> nodes = tp.children(root); System.out.println("根節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn):" + nodes.get(0)); // 為根節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)新增一個(gè)子節(jié)點(diǎn) tp.addNode("節(jié)點(diǎn)4", nodes.get(0)); System.out.println("此樹(shù)第一個(gè)子節(jié)點(diǎn):" + nodes.get(0)); System.out.println("此樹(shù)的深度:" + tp.deep()); } }
程序輸出:
TreeChild$Node[data=root, first=-1]
添加子節(jié)點(diǎn)后的根結(jié)點(diǎn):TreeChild$Node[data=root, first=1]
此樹(shù)的深度:2
根節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn):TreeChild$Node[data=節(jié)點(diǎn)1, first=-1]
此樹(shù)第一個(gè)子節(jié)點(diǎn):TreeChild$Node[data=節(jié)點(diǎn)1, first=4]
此樹(shù)的深度:3
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。