- Java 資料結構與演算法 教程
- Java 資料結構與演算法 - 首頁
- Java 資料結構與演算法 - 概述
- Java 資料結構與演算法 - 環境設定
- Java 資料結構與演算法 - 演算法
- Java 資料結構與演算法 - 資料結構
- Java 資料結構與演算法 - 陣列
- Java 資料結構與演算法 - 連結串列
- Java 資料結構與演算法 - 雙向連結串列
- Java 資料結構與演算法 - 迴圈連結串列
- Java 資料結構與演算法 - 棧
- 資料結構與演算法 - 表示式解析
- Java 資料結構與演算法 - 佇列
- Java 資料結構與演算法 - 優先佇列
- Java 資料結構與演算法 - 樹
- Java 資料結構與演算法 - 雜湊表
- Java 資料結構與演算法 - 堆
- Java 資料結構與演算法 - 圖
- Java 資料結構與演算法 - 搜尋技術
- Java 資料結構與演算法 - 排序技術
- Java 資料結構與演算法 - 遞迴
- Java 資料結構與演算法 有用資源
- Java 資料結構與演算法 - 快速指南
- Java 資料結構與演算法 - 有用資源
- Java 資料結構與演算法 - 討論
Java 資料結構與演算法 - 樹
概述
樹由節點和邊連線而成。我們將專門討論二叉樹或二叉搜尋樹。
二叉樹是一種用於資料儲存的特殊資料結構。二叉樹有一個特殊的條件，即每個節點最多可以有兩個子節點。二叉樹兼具有序陣列和連結串列的優點，搜尋速度與有序陣列一樣快，插入或刪除操作速度與連結串列一樣快。
術語
以下是關於樹的一些重要術語。
路徑 - 路徑指的是樹中沿邊的一系列節點。
根 - 樹頂部的節點稱為根。每棵樹只有一個根，並且從根節點到任何節點都只有一條路徑。
父節點 - 除根節點外的任何節點都有一條向上連線到稱為父節點的節點的邊。
子節點 - 在給定節點下方由其向下連線的邊連線的節點稱為其子節點。
葉子節點 - 沒有子節點的節點稱為葉子節點。
子樹 - 子樹表示節點的後代。
訪問 - 訪問是指當控制權在節點上時檢查節點的值。
遍歷 - 遍歷是指按特定順序透過節點。
層級 - 節點的層級表示節點的代數。如果根節點在第 0 層，那麼其下一個子節點在第 1 層，其孫節點在第 2 層，依此類推。
鍵 - 鍵表示節點的值，根據該值執行節點的搜尋操作。
二叉搜尋樹表現出特殊的行為。節點的左子節點的值必須小於其父節點的值，節點的右子節點的值必須大於其父節點的值。
二叉搜尋樹表示
我們將使用節點物件來實現樹，並透過引用將它們連線起來。
基本操作
以下是樹的基本主要操作。
搜尋 - 在樹中搜索一個元素。
插入 - 在樹中插入一個元素。
先序遍歷 - 以先序方式遍歷樹。
中序遍歷 - 以中序方式遍歷樹。
後序遍歷 - 以後序方式遍歷樹。
節點
定義一個節點，它包含一些資料以及對其左右子節點的引用。
public class Node {
public int data;
public Node leftChild;
public Node rightChild;
public Node(){}
public void display(){
System.out.print("("+data+ ")");
}
}
搜尋操作
當要搜尋一個元素時。從根節點開始搜尋，如果資料小於鍵值，則在左子樹中搜索元素，否則在右子樹中搜索元素。對每個節點遵循相同的演算法。
public Node search(int data){
Node current = root;
System.out.print("Visiting elements: ");
while(current.data != data){
if(current != null)
System.out.print(current.data + " ");
//go to left tree
if(current.data > data){
current = current.leftChild;
}//else go to right tree
else{
current = current.rightChild;
}
//not found
if(current == null){
return null;
}
}
return current;
}
插入操作
當要插入一個元素時。首先找到其合適的位置。從根節點開始搜尋，如果資料小於鍵值，則在左子樹中搜索空位置並插入資料。否則，在右子樹中搜索空位置並插入資料。
public void insert(int data){
Node tempNode = new Node();
tempNode.data = data;
//if tree is empty
if(root == null){
root = tempNode;
}else{
Node current = root;
Node parent = null;
while(true){
parent = current;
//go to left of the tree
if(data < parent.data){
current = current.leftChild;
//insert to the left
if(current == null){
parent.leftChild = tempNode;
return;
}
}//go to right of the tree
else{
current = current.rightChild;
//insert to the right
if(current == null){
parent.rightChild = tempNode;
return;
}
}
}
}
}
先序遍歷
這是一個簡單的三步過程。
訪問根節點
遍歷左子樹
遍歷右子樹
private void preOrder(Node root){
if(root!=null){
System.out.print(root.data + " ");
preOrder(root.leftChild);
preOrder(root.rightChild);
}
}
中序遍歷
這是一個簡單的三步過程。
遍歷左子樹
訪問根節點
遍歷右子樹
private void inOrder(Node root){
if(root!=null){
inOrder(root.leftChild);
System.out.print(root.data + " ");
inOrder(root.rightChild);
}
}
後序遍歷
這是一個簡單的三步過程。
遍歷左子樹
遍歷右子樹
訪問根節點
private void postOrder(Node root){
if(root!=null){
postOrder(root.leftChild);
postOrder(root.rightChild);
System.out.print(root.data + " ");
}
}
樹的實現
Node.java
package com.tutorialspoint.datastructure;
public class Node {
public int data;
public Node leftChild;
public Node rightChild;
public Node(){}
public void display(){
System.out.print("("+data+ ")");
}
}
Tree.java
package com.tutorialspoint.datastructure;
public class Tree {
private Node root;
public Tree(){
root = null;
}
public Node search(int data){
Node current = root;
System.out.print("Visiting elements: ");
while(current.data != data){
if(current != null)
System.out.print(current.data + " ");
//go to left tree
if(current.data > data){
current = current.leftChild;
}//else go to right tree
else{
current = current.rightChild;
}
//not found
if(current == null){
return null;
}
}
return current;
}
public void insert(int data){
Node tempNode = new Node();
tempNode.data = data;
//if tree is empty
if(root == null){
root = tempNode;
}else{
Node current = root;
Node parent = null;
while(true){
parent = current;
//go to left of the tree
if(data < parent.data){
current = current.leftChild;
//insert to the left
if(current == null){
parent.leftChild = tempNode;
return;
}
}//go to right of the tree
else{
current = current.rightChild;
//insert to the right
if(current == null){
parent.rightChild = tempNode;
return;
}
}
}
}
}
public void traverse(int traversalType){
switch(traversalType){
case 1:
System.out.print("\nPreorder traversal: ");
preOrder(root);
break;
case 2:
System.out.print("\nInorder traversal: ");
inOrder(root);
break;
case 3:
System.out.print("\nPostorder traversal: ");
postOrder(root);
break;
}
}
private void preOrder(Node root){
if(root!=null){
System.out.print(root.data + " ");
preOrder(root.leftChild);
preOrder(root.rightChild);
}
}
private void inOrder(Node root){
if(root!=null){
inOrder(root.leftChild);
System.out.print(root.data + " ");
inOrder(root.rightChild);
}
}
private void postOrder(Node root){
if(root!=null){
postOrder(root.leftChild);
postOrder(root.rightChild);
System.out.print(root.data + " ");
}
}
}
演示程式
TreeDemo.java
package com.tutorialspoint.datastructure;
public class TreeDemo {
public static void main(String[] args){
Tree tree = new Tree();
/* 11 //Level 0
*/
tree.insert(11);
/* 11 //Level 0
* |
* |---20 //Level 1
*/
tree.insert(20);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
*/
tree.insert(3);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* |--42 //Level 2
*/
tree.insert(42);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* |--42 //Level 2
* |
* |--54 //Level 3
*/
tree.insert(54);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* 16--|--42 //Level 2
* |
* |--54 //Level 3
*/
tree.insert(16);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* |
* 16--|--42 //Level 2
* |
* 32--|--54 //Level 3
*/
tree.insert(32);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* | |
* |--9 16--|--42 //Level 2
* |
* 32--|--54 //Level 3
*/
tree.insert(9);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* | |
* |--9 16--|--42 //Level 2
* | |
* 4--| 32--|--54 //Level 3
*/
tree.insert(4);
/* 11 //Level 0
* |
* 3---|---20 //Level 1
* | |
* |--9 16--|--42 //Level 2
* | |
* 4--|--10 32--|--54 //Level 3
*/
tree.insert(10);
Node node = tree.search(32);
if(node!=null){
System.out.print("Element found.");
node.display();
System.out.println();
}else{
System.out.println("Element not found.");
}
Node node1 = tree.search(2);
if(node1!=null){
System.out.println("Element found.");
node1.display();
System.out.println();
}else{
System.out.println("Element not found.");
}
//pre-order traversal
//root, left ,right
tree.traverse(1);
//in-order traversal
//left, root ,right
tree.traverse(2);
//post order traversal
//left, right, root
tree.traverse(3);
}
}
如果我們編譯並執行上述程式，則會產生以下結果：
Visiting elements: 11 20 42 Element found.(32) Visiting elements: 11 3 Element not found. Preorder traversal: 11 3 9 4 10 20 16 42 32 54 Inorder traversal: 3 4 9 10 11 16 20 32 42 54 Postorder traversal: 4 10 9 3 16 32 54 42 20 11
廣告