手寫查詢二叉樹
查詢二叉樹
隨著大資料時代的來臨,樹形結構得到了越來越廣泛的應用,廢話不多說,直接開始我們的正題,查詢二叉樹。
何為查詢二叉樹
查詢二叉樹是二叉樹的一種,又名查詢樹,搜尋樹。查詢二叉樹具有如下特點;
1.必須是二叉樹
2.任意節點的左子樹上所有的資料都比該節點資料小,或者為空樹
3.任意節點的右子樹上所有的資料都比該節點資料大,或者為空樹
應用場景
顧名思義,查詢二叉樹的作用就是快速查詢 ,使用於資料量特別大時候的快速查詢,時間複雜度介於O(log2n)到O(n)之間,資料量越大,越接近於O(log2n),效能越優,大資料時代的必備技能之一。
程式碼實現
一.使用孩子雙親表示法表示樹
public class Node <T extends Comparable>{ T item; Node<T> leftChild; Node<T> rightChild; Node<T> parent; public Node(T item) { this.item = item; } }
二.定義屬性變數
Node root; int size;
三.實現必要的增刪查詢和遍歷方法
add 方法實現
public boolean add(T item) { Node<T> newNode = new Node<T>(item); if (root == null) { //如果是空樹 root = newNode; size++; return true; } Node node = root; Node parent = null; while (node != null) { parent = node; if (node.item.compareTo(item) == 0) { //去掉重複的,不進行新增操作 return false; } else if (node.item .compareTo(item) >0) { //如果加入的節點比做節點小 node = node.leftChild; } else { //如果加入的節點比做節點大 node = node.rightChild; } } if (parent.item .compareTo(item)>0) { parent.leftChild = newNode; } else { parent.rightChild = newNode; } newNode.parent = parent; size++; returntrue; }
get方法實現
public Node get(T item) { if (root == null) { return null; } Node node = root; while (node != null) { if (node.item.compareTo(item)<0) { node = node.rightChild; } else if (node.item.compareTo(item)>0) { node = node.leftChild; } else { return node; } } return null; }
遍歷
/** * 採取中序遍歷的方式對樹進行遍歷 */ public void midOrderTraseval(){ midOrderTraseval(root); } privatevoid midOrderTraseval(Node<T> node) { if (node == null) { return; } midOrderTraseval(node.leftChild); System.out.print(node.item +" "); midOrderTraseval(node.rightChild); }
delete方法(難點)
思路:
1.如果刪除的節點左右子樹都為空,即葉子節點時:
Node<T> left = node.leftChild; Node<T> right = node.rightChild; Node<T> parent = node.parent; //第一種情況 node 為葉子節點 if (left == null && right == null) { if(parent == null){ root = null; }else { if (parent.leftChild == node) { parent.leftChild = null; } else { parent.rightChild = null; } } node.parent = null; }
2.如果刪除的節點只有右子樹為空時:
else if (left != null && right == null) { //第二種情況,只有左節點,沒有右節點 if(parent == null){ root = left; }else { if (parent.leftChild == node) { parent.leftChild = left; } else { parent.rightChild = left; } } left.parent = parent; node.parent = null; node.leftChild = null; }
3.如果刪除的節點只有左子樹為空時:
else if (left == null && right != null) { //第三種情況,只有右節點,沒有左節點 if(parent == null){ root = right; }else { if (parent.leftChild == node) { parent.leftChild = right; } else { parent.rightChild = right; } } right.parent = parent; node.parent = null; node.rightChild = null; }
4.刪除節點的左右子樹均不為空時:
else { //左右兩邊都有節點的 Node lleftNode = getLeftChildNode(right); lleftNode.leftChild = left; left.parent = lleftNode; if(lleftNode.rightChild !=null){ if(lleftNode.parent != node){ lleftNode.parent.leftChild = lleftNode.rightChild; lleftNode.rightChild.parent = lleftNode.parent; } } if(lleftNode == right){ lleftNode.rightChild =null; }else { lleftNode.rightChild = right; } right.parent = lleftNode; if(parent == null){ lleftNode.parent = null; root = lleftNode; }else { if(parent.leftChild == node){ parent.leftChild = lleftNode; }else { parent.rightChild = lleftNode; } lleftNode.parent = parent; } node.leftChild = null; node.rightChild =null; node.parent = null; }
完整程式碼
package com.example.administrator.myapplication; /** * Created by Administrator on 2018-12-09. */ public class SearchBinaryTree<T extends Comparable> { Node root; int size; public class Node <T extends Comparable>{ T item; Node<T> leftChild; Node<T> rightChild; Node<T> parent; public Node(T item) { this.item = item; } } public int size() { return size; } public boolean add(T item) { Node<T> newNode = new Node<T>(item); if (root == null) { //如果是空樹 root = newNode; size++; return true; } Node node = root; Node parent = null; while (node != null) { parent = node; if (node.item.compareTo(item) == 0) { //去掉重複的,不進行新增操作 return false; } else if (node.item .compareTo(item) >0) { //如果加入的節點比做節點小 node = node.leftChild; } else { //如果加入的節點比做節點大 node = node.rightChild; } } if (parent.item .compareTo(item)>0) { parent.leftChild = newNode; } else { parent.rightChild = newNode; } newNode.parent = parent; size++; returntrue; } public Node get(T item) { if (root == null) { return null; } Node node = root; while (node != null) { if (node.item.compareTo(item)<0) { node = node.rightChild; } else if (node.item.compareTo(item)>0) { node = node.leftChild; } else { return node; } } return null; } /** * 採取中序遍歷的方式對樹進行遍歷 */ public void midOrderTraseval(){ midOrderTraseval(root); } privatevoid midOrderTraseval(Node<T> node) { if (node == null) { return; } midOrderTraseval(node.leftChild); System.out.print(node.item +" "); midOrderTraseval(node.rightChild); } public Node<T> delete(T item){ Node<T> node = get(item); if(node !=null){ delete(node); } return node; } private void delete(Node<T> node) { if (node == null) { return; } Node<T> left = node.leftChild; Node<T> right = node.rightChild; Node<T> parent = node.parent; //第一種情況 node 為葉子節點 if (left == null && right == null) { if(parent == null){ root = null; }else { if (parent.leftChild == node) { parent.leftChild = null; } else { parent.rightChild = null; } } node.parent = null; } else if (left != null && right == null) { //第二種情況,只有左節點,沒有右節點 if(parent == null){ root = left; }else { if (parent.leftChild == node) { parent.leftChild = left; } else { parent.rightChild = left; } } left.parent = parent; node.parent = null; node.leftChild = null; }else if (left == null && right != null) { //第三種情況,只有右節點,沒有左節點 if(parent == null){ root = right; }else { if (parent.leftChild == node) { parent.leftChild = right; } else { parent.rightChild = right; } } right.parent = parent; node.parent = null; node.rightChild = null; }else { //左右兩邊都有節點的 Node lleftNode = getLeftChildNode(right); lleftNode.leftChild = left; left.parent = lleftNode; if(lleftNode.rightChild !=null){ if(lleftNode.parent != node){ lleftNode.parent.leftChild = lleftNode.rightChild; lleftNode.rightChild.parent = lleftNode.parent; } } if(lleftNode == right){ lleftNode.rightChild =null; }else { lleftNode.rightChild = right; } right.parent = lleftNode; if(parent == null){ lleftNode.parent = null; root = lleftNode; }else { if(parent.leftChild == node){ parent.leftChild = lleftNode; }else { parent.rightChild = lleftNode; } lleftNode.parent = parent; } node.leftChild = null; node.rightChild =null; node.parent = null; } size--; } private Node<T> getLeftChildNode(Node<T> node){ Node<T> leftChild = node; Node<T> newNode = node; while (newNode!=null){ leftChild = newNode; newNode = newNode.leftChild; } return leftChild; }
}
測試及結果列印
@Test public void testSearchTree(){ SearchBinaryTree<Integer> tree = new SearchBinaryTree(); int[] array = new int[]{5,4,9,2,0,7,3,1,8}; for (int i : array) { tree.add(i); } for (int i : array) { tree.midOrderTraseval(); System.out.println("-----------------------"); tree.delete(i); } for (int i : array) { tree.add(i); } tree.midOrderTraseval(); }
結果列印
0 1 2 3 4 5 7 8 9 ----------------------- 0 1 2 3 4 7 8 9 ----------------------- 0 1 2 3 7 8 9 ----------------------- 0 1 2 3 7 8 ----------------------- 0 1 3 7 8 ----------------------- 1 3 7 8 ----------------------- 1 3 8 ----------------------- 1 8 ----------------------- 8 ----------------------- 0 1 2 3 4 5 7 8 9
完美收工:
初次寫技術部落格,各位大牛請多包涵,共同進步!