原文鏈接：http://www.cnblogs.com/skywang12345/p/3576452.html

1. 二叉查找樹簡介

二叉查找樹(Binary Search Tree)，又被稱為二叉搜索樹。

它是特殊的二叉樹：對于二叉樹，假設x為二叉樹中的任意一個結點，x節點包含關鍵字key，節點x的key值記為key[x]。如果y是x的左子樹中的一個結點，則key[y] <= key[x]；如果y是x的右子樹的一個結點，則key[y] >= key[x]。那么，這棵樹就是二叉查找樹。如下圖所示

在二叉查找樹中：

• 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值
• 任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值
• 任意節點的左、右子樹也分別為二叉查找樹
• 沒有鍵值相等的節點（no duplicate nodes）

2. 二叉查找樹的Java實現

2.1 二叉查找樹節點的定義

public class BSTree<T extends Comparable<T>> {private BSTNode<T> mRoot; // 根結點public class BSTNode<T extends Comparable<T>> {T key; // 關鍵字(鍵值)BSTNode<T> left; // 左孩子BSTNode<T> right; // 右孩子BSTNode<T> parent; // 父結點public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {this.key = key;this.parent = parent;this.left = left;this.right = right;}}...... }

BSTree是二叉樹，它保護了二叉樹的根節點mRoot；mRoot是BSTNode類型，而BSTNode是二叉查找樹的節點，它是BSTree的內部類。BSTNode包含二叉查找樹的幾個基本信息：

• key – 它是關鍵字，是用來對二叉查找樹的節點進行排序的。
• left – 它指向當前節點的左孩子。
• right – 它指向當前節點的右孩子。
• parent – 它指向當前節點的父結點。

2.2 遍歷

這里講解前序遍歷、中序遍歷、后序遍歷3種方式。

2.2.1 前序遍歷

若二叉樹非空，則執行以下操作：

• 訪問根結點；
• 先序遍歷左子樹；
• 先序遍歷右子樹。

前序遍歷代碼

private void preOrder(BSTNode<T> tree) {if(tree != null) {System.out.print(tree.key+" ");preOrder(tree.left);preOrder(tree.right);} }public void preOrder() {preOrder(mRoot); }

2.2.2 中序遍歷

若二叉樹非空，則執行以下操作：
(01) 中序遍歷左子樹；
(02) 訪問根結點；
(03) 中序遍歷右子樹。

中序遍歷代碼

private void inOrder(BSTNode<T> tree) {if(tree != null) {inOrder(tree.left);System.out.print(tree.key+" ");inOrder(tree.right);} }public void inOrder() {inOrder(mRoot); }

2.3 后序遍歷

若二叉樹非空，則執行以下操作：
(01) 后序遍歷左子樹；
(02) 后序遍歷右子樹；
(03) 訪問根結點。

后序遍歷代碼

private void postOrder(BSTNode<T> tree) {if(tree != null){postOrder(tree.left);postOrder(tree.right);System.out.print(tree.key+" ");} }public void postOrder() {postOrder(mRoot); }

看看下面這顆樹的各種遍歷方式：

對于上面的二叉樹而言，

• 前序遍歷結果： 3 1 2 5 4 6
• 中序遍歷結果： 1 2 3 4 5 6
• 后序遍歷結果： 2 1 4 6 5 3

2.4 層序遍歷

所謂層序遍歷(Levelorder Traversal)二叉樹，是指從二叉樹的第一層(根結點)開始，自上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。對于右圖所示的二叉樹，按層序遍歷方式進行遍歷所得到的結點序列為：A、B、C、D、E、F、G、H、I。

3. 二叉樹的存儲結構

3.1 數組表示法

二叉樹的數組表示就是采用一組連續存儲空間存儲二叉樹結點中的數據元素，利用數組下標來反映數據元素之間的關系。

對具有n個結點的完全二叉樹按從上到下、自左向右的順序連續給結點編號0、1、2、…、n-1。按此結點編號將二叉樹中各結點中的數據元素順序地存放于一個一維數組中，首先將根結點中的數據元素儲存在數組的0號位置；對于二叉樹中任一個結點，如果它的數據元素存儲在數組的第i個位置，就把它的左、右孩子結點中的數據元素分別存放在數組的第2*i+1個位置和第2*i+2個位置。這樣就得到了二叉樹的一種數組表示法。

采用這種方法表示一般的二叉樹時，空間利用效率低是一個主要的問題。當被表示的二叉樹結構很不完整時，在數組中就會出現很多空位置，因此空間浪費就變得非常大。

用這種方法表示二叉樹時，還有一個問題需要注意的是：必須處理結點不存在的情況。如果一個結點不存在，就必須在數組中相應位置設置一個特殊標志，指明在這個位置沒有結點。

二叉樹的二叉鏈表表示，對于大多數的應用來說是適合的。但是，在二叉鏈表中要想找出一個結點的雙親是比較困難的，必須通過二叉樹的遍歷才能實現。如果在應用中需要方便地找到任何一個結點的雙親，可以在結點中增加一個Parent域來指向該結點的雙親，二叉樹的這種表示方法稱為三叉鏈表。

3.2 鏈表表示法

在二叉樹的鏈表表示中，樹中的每一個元素用一個結點表示，結點一般包括三個域，其結構如圖(a)所示。其中，Data域用于存放數據元素的信息；leftChild域用于存放指向其左孩子結點的指針；rightChild域用于存放指向其右孩子結點的指針。二叉樹的這種鏈表表示稱為二叉鏈表。

4. 二叉樹實現

中序遍歷是有序的二叉樹(不重復)

public class MyTree {private Node root; // 根節點private class Node{Node parrent; // 父節點Node left; // 左兒子Node right; // 右兒子Object data;public Node(Object data) {this.data = data;}}/*** @param data* 傳遞的數據* @return 父節點的值*/private Node findParrent(Object data, Node currentNode) {// 從根節點找Node temp = currentNode;Node parrent = currentNode;// 循環找while (temp != null) {parrent = temp;// 比較if (compare(data, temp.data)) {// data 大于 當前節點temp = temp.right;} else {// data 小于 當前節點temp = temp.left;}}return parrent;}public void update(Object oldData,Object newData){remove(oldData);add(newData);}/*** 添加數據* * @param data* 要添加的數據*/public void add(Object data) {// 判斷該數據是否存在if (contains(data))return;// 1.把數據放到節點中Node node = new Node(data);// 2.把節點鏈接到二叉樹中// 是否有根節點if (root == null) {root = node;// 保存到根節點中} else {// 找位置,找父節點,比較父節點的值，小左邊 大右邊Node parrent = findParrent(data, root);// 設置新增節點的父節點node.parrent = parrent;// 比較if (compare(data, parrent.data)) {// 自己比父節點大parrent.right = node;} else {// 自己比父節點小parrent.left = node;}}}/*** @param data* @return 是否包含該數據*/public boolean contains(Object data) {return null != find(data);}private Node find(Object data) {Node temp = root;// 從根節點找while (temp != null) {// 判斷數據if (temp.data.equals(data)&& temp.data.hashCode() == data.hashCode()) {// 找到數據break;} else if (compare(data, temp.data)) {// true data > temp// 從右邊找temp = temp.right;} else {// false data < temp// 從坐標邊找temp = temp.left;}}return temp;}public void remove(Object data) {// 1. 查找數據是否存在Node temp = find(data);// 2. 存在：找到數據節點if (temp != null) {// 存在// 3. 刪除節點// 1. 根節點if (temp == root) {// 11 沒有兒子if (temp.left == null && temp.right == null) {root = null;} else if (temp.right == null) {root = root.left;root.parrent = null;// 12 只有左兒子} else if (temp.left == null) {// 13 只有右兒子root = root.right;root.parrent = null;} else {// 14 兩個兒子都有// 保留左兒子Node left = getLeft(temp);// left成為新的根節點root = left;left.parrent = null;}} else {// 2. 非根節點if (temp.left == null && temp.right == null) {// 21 沒有兒子if (compare(temp.data, temp.parrent.data)) {//在父節點右邊temp.parrent.right = null;} else {//在父節點左邊temp.parrent.left = null;}} else if (temp.right == null) {// 22 只有左兒子if (compare(temp.data, temp.parrent.data)) {//在父節點右邊temp.parrent.right = temp.left;temp.left.parrent = temp.parrent;} else {//在父節點左邊temp.parrent.left = temp.left;temp.left.parrent = temp.parrent;}} else if (temp.left == null) {// 23 只有右兒子if (compare(temp.data, temp.parrent.data)) {//在父節點右邊temp.parrent.right = temp.right;temp.right.parrent = temp.parrent;} else {//在父節點左邊temp.parrent.left = temp.right;temp.right.parrent = temp.parrent;}} else {// 24 兩個兒子都有Node left = getLeft(temp);//上面還有父節點（爺爺）if (compare(left.data, temp.parrent.data)) {//比爺爺節點大temp.parrent.right = left;left.parrent = temp.parrent;} else {//比爺爺節點小temp.parrent.left = left;left.parrent = temp.parrent;}}}}}/*** @param node* 要刪除的節點* @return 左兒子節點*/private Node getLeft(Node node) {// 保留左兒子Node left = node.left;// 處理右節點Node rightNewParrent = findParrent(node.right.data, left);rightNewParrent.right = node.right;// 把刪除節點的右節點放到刪除節點的左兒子最右邊node.right.parrent = rightNewParrent;return left;}/*** @param o1* 第一個值* @param o2* 第二個值* @return 如果o1 大于 o2 返回true 否則false*/public boolean compare(Object o1, Object o2) {boolean res = false;// 判斷o1 有沒有實現比較器if (o1 instanceof Comparable) {Comparable c1 = (Comparable) o1;Comparable c2 = (Comparable) o2;if (c1.compareTo(c2) > 0) {res = true;} else {// 默認值就是false}} else {// 傳遞的對象沒有比較器res = o1.toString().compareTo(o2.toString()) > 0 ? true : false;}return res;}// 遞歸打印public void print() {print(root);}public void print(Node node) {if (node == null) {return;} else {// 遍歷 中序print(node.left);System.out.println(node.data + ",");print(node.right);}}} public class TestTreeApp {public static void main(String[] args) {MyTree trees = new MyTree();int[] datas = {55,33,44,88,66,99};for (int d : datas) {trees.add(d);}trees.print();System.out.println();//測試刪除trees.update(33,77);trees.print();}}

總結

以上是生活随笔為你收集整理的Java数据结构与算法：二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

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