java數據結構之樹的示例分析

這篇文章主要介紹java數據結構之樹的示例分析，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

樹定義和基本術語

定義

樹(Tree)是n(n≥0)個結點的有限集T，并且當n＞0時滿足下列條件：

（1）有且僅有一個特定的稱為根(Root)的結點；

（2）當n＞1時，其余結點可以劃分為m(m＞0)個互不相交的有限集T1、T2、…、Tm，每個集Ti(1≤i≤m)均為樹，且稱為樹T的子樹(SubTree)。

特別地，不含任何結點(即n＝0)的樹，稱為空樹。

如下就是一棵樹的結構：

基本術語

結點：存儲數據元素和指向子樹的鏈接，由數據元素和構造數據元素之間關系的引用組成。
孩子結點：樹中一個結點的子樹的根結點稱為這個結點的孩子結點，如圖1中的A的孩子結點有B、C、D
雙親結點：樹中某個結點有孩子結點(即該結點的度不為0)，該結點稱為它孩子結點的雙親結點，也叫前驅結點。雙親結點和孩子結點是相互的，如圖1中，A的孩子結點是B、C、D，B、C、D的雙親結點是A。
兄弟結點：具有相同雙親結點(即同一個前驅)的結點稱為兄弟結點，如圖1中B、B、D為兄弟結點。
結點的度：結點所有子樹的個數稱為該結點的度，如圖1，A的度為3，B的度為2.
樹的度：樹中所有結點的度的最大值稱為樹的度，如圖1的度為3.
葉子結點：度為0的結點稱為葉子結點，也叫終端結點。如圖1的K、L、F、G、M、I、J
分支結點：度不為0的結點稱為分支結點，也叫非終端結點。如圖1的A、B、C、D、E、H
結點的層次：從根結點到樹中某結點所經路徑的分支數稱為該結點的層次。根結點的層次一般為1(也可以自己定義為0)，這樣，其它結點的層次是其雙親結點的層次加1.
樹的深度：樹中所有結點的層次的最大值稱為該樹的深度(也就是最下面那個結點的層次)。
有序樹和無序樹：樹中任意一個結點的各子樹按從左到右是有序的，稱為有序樹，否則稱為無序樹。
樹的抽象數據類型描述
數據元素：具有相同特性的數據元素的集合。
結構關系：樹中數據元素間的結構關系由樹的定義確定。

基本操作：樹的主要操作有

（1）創建樹IntTree(&T)
         創建1個空樹T。
（2）銷毀樹DestroyTree(&T)
（3）構造樹CreatTree(&T，deinition)
（4）置空樹ClearTree(&T)
          將樹T置為空樹。
（5）判空樹TreeEmpty(T)
（6）求樹的深度TreeDepth(T)
（7）獲得樹根Root(T)
（8）獲取結點Value(T，cur_e，&e)
         將樹中結點cur_e存入e單元中。
（9）數據賦值Assign(T，cur_e，value)
         將結點value，賦值于樹T的結點cur_e中。
（10）獲得雙親Parent(T，cur_e)
        返回樹T中結點cur_e的雙親結點。
（11）獲得最左孩子LeftChild(T，cur_e)
        返回樹T中結點cur_e的最左孩子。
（12）獲得右兄弟RightSibling(T，cur_e)
        返回樹T中結點cur_e的右兄弟。
（13）插入子樹InsertChild(&T，&p，i，c)
      將樹c插入到樹T中p指向結點的第i個子樹之前。
（14）刪除子樹DeleteChild(&T，&p，i)
       刪除樹T中p指向結點的第i個子樹。
（15）遍歷樹TraverseTree(T，visit())

樹的實現

樹是一種遞歸結構，表示方式一般有孩子表示法和孩子兄弟表示法兩種。樹實現方式有很多種、有可以由廣義表的遞歸實現，也可以有二叉樹實現，其中最常見的是將樹用孩子兄弟表示法轉化成二叉樹來實現。

下面以孩子表示法為例講一下樹的實現：

樹的定義和實現

package datastructure.tree;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/** 
   * 樹的定義和實現 
   * @author Administrator 
   * 
   */
public class Tree {
	private Object data;
	private List<Tree> childs;
	public Tree(){
		data = null;
		childs = new ArrayList();
		childs.clear();
	}
	public Tree(Object data) {
		this.data = data;
		childs = new ArrayList();
		childs.clear();
	}
	/** 
     * 添加子樹 
     * @param tree 子樹 
     */
	public void addNode(Tree tree) {
		childs.add(tree);
	}
	/** 
     * 置空樹 
     */
	public void clearTree() {
		data = null;
		childs.clear();
	}
	/** 
     * 求樹的深度 
     * 這方法還有點問題，有待完善 
     * @return 樹的深度 
     */
	public int dept() {
		return dept(this);
	}
	/** 
     * 求樹的深度 
     * 這方法還有點問題，有待完善 
     * @param tree 
     * @return 
     */
	private int dept(Tree tree) {
		if(tree.isEmpty()) {
			return 0;
		} else if(tree.isLeaf()) {
			return 1;
		} else {
			int n = childs.size();
			int[] a = new int[n];
			for (int i=0; i<n; i++) {
				if(childs.get(i).isEmpty()) {
					a[i] = 0+1;
				} else {
					a[i] = dept(childs.get(i)) + 1;
				}
			}
			Arrays.sort(a);
			return a[n-1];
		}
	}
	/** 
     * 返回遞i個子樹 
     * @param i 
     * @return 
     */
	public Tree getChild(int i) {
		return childs.get(i);
	}
	/** 
     * 求第一個孩子 結點 
     * @return 
     */
	public Tree getFirstChild() {
		return childs.get(0);
	}
	/** 
     * 求最后 一個孩子結點 
     * @return 
     */
	public Tree getLastChild() {
		return childs.get(childs.size()-1);
	}
	public List<Tree> getChilds() {
		return childs;
	}
	/** 
     * 獲得根結點的數據 
     * @return 
     */
	public Object getRootData() {
		return data;
	}
	/** 
     * 判斷是否為空樹 
     * @return 如果為空，返回true,否則返回false 
     */
	public Boolean isEmpty() {
		if(childs.isEmpty() && data == null) 
		        return true;
		return false;
	}
	/** 
     * 判斷是否為葉子結點 
     * @return 
     */
	public Boolean isLeaf() {
		if(childs.isEmpty()) 
		        return true;
		return false;
	}
	/** 
     * 獲得樹根 
     * @return 樹的根 
     */
	public Tree root() {
		return this;
	}
	/** 
     * 設置根結點的數據 
     */
	public void setRootData(Object data) {
		this.data = data;
	}
	/** 
     * 求結點數 
     * 這方法還有點問題，有待完善 
     * @return 結點的個數 
     */
	public int size() {
		return size(this);
	}
	/** 
     * 求結點數 
     * 這方法還有點問題，有待完善 
     * @param tree 
     * @return 
     */
	private int size(Tree tree) {
		if(tree.isEmpty()) {
			return 0;
		} else if(tree.isLeaf()) {
			return 1;
		} else {
			int count = 1;
			int n = childs.size();
			for (int i=0; i<n; i++) {
				if(!childs.get(i).isEmpty()) {
					count += size(childs.get(i));
				}
			}
			return count;
		}
	}
}

樹的遍歷

樹的遍歷有兩種

前根遍歷

（1）.訪問根結點；

（2）.按照從左到右的次序行根遍歷根結點的第一棵子樹；

后根遍歷

（1）.按照從左到右的次序行根遍歷根結點的第一棵子樹；

（2）.訪問根結點；

Visit.Java

package datastructure.tree;
import datastructure.tree.btree.BTree;
/** 
   * 對結點進行操作的接口,規定樹的遍歷的類必須實現這個接口 
   * @author Administrator 
   * 
   */
public interface Visit {
	/** 
     * 對結點進行某種操作 
     * @param btree 樹的結點 
     */
	public void visit(BTree btree);
}

order.java

package datastructure.tree;
import java.util.List;
/** 
   * 樹的遍歷 
   * @author Administrator 
   * 
   */
public class Order {
	/** 
     * 先根遍歷 
     * @param root 要的根結點 
     */
	public void preOrder(Tree root) {
		if(!root.isEmpty()) {
			visit(root);
			for (Tree child : root.getChilds()) {
				if(child != null) {
					preOrder(child);
				}
			}
		}
	}
	/** 
     * 后根遍歷 
     * @param root 樹的根結點 
     */
	public void postOrder(Tree root) {
		if(!root.isEmpty()) {
			for (Tree child : root.getChilds()) {
				if(child != null) {
					preOrder(child);
				}
			}
			visit(root);
		}
	}
	public void visit(Tree tree) {
		System.out.print("\t" + tree.getRootData());
	}
}

測試：

要遍歷的樹如下：

package datastructure.tree;
import java.util.Iterator;
import java.util.Scanner;
public class TreeTest {
	/** 
     * @param args 
     */
	public static void main(String[] args) {
		Tree root = new Tree("A");
		root.addNode(new Tree("B"));
		root.addNode(new Tree("C"));
		root.addNode(new Tree("D"));
		Tree t = null;
		t = root.getChild(0);
		t.addNode(new Tree("L"));
		t.addNode(new Tree("E"));
		t = root.getChild(1);
		t.addNode(new Tree("F"));
		t = root.getChild(2);
		t.addNode(new Tree("I"));
		t.addNode(new Tree("H"));
		t = t.getFirstChild();
		t.addNode(new Tree("L"));
		System.out.println("first node:" + root.getRootData());
		//System.out.println("size:" + root.size()); 
		//System.out.println("dept:" + root.dept()); 
		System.out.println("is left:" + root.isLeaf());
		System.out.println("data:" + root.getRootData());
		Order order = new Order();
		System.out.println("前根遍歷：");
		order.preOrder(root);
		System.out.println("\n后根遍歷：");
		order.postOrder(root);
	}
}

結果：

first node:A
is left:false
data:A
前根遍歷：
A BL E C F DI L H
后根遍歷：
B LE C F D IL H A

以上是“java數據結構之樹的示例分析”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！