二叉樹的實現

數組查詢快，增刪慢；鏈表增刪快，查詢慢；二叉樹查詢和增刪都有很好的性能

package com.itheiam62;/*** @描述 中序遍歷是有序的二叉樹(不重復)* */ 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);}}}

從currentNode節點開始查找data的父節點

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;}

刪除節點，該節點有左右孩子

可以把右孩子添加到左孩子的右邊，或者把左孩子添加到右孩子的左邊

//node 要刪除的節點 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;}

刪除節點

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;}}}}}

刪除的節點非根節點，且右孩子為空

else if (temp.right == null) {// 只有左兒子if (compare(temp.data, temp.parrent.data)) {//在父節點右邊，下圖中的23temp.parrent.right = temp.left;temp.left.parrent = temp.parrent;} else {//在父節點左邊，下圖中的50temp.parrent.left = temp.left;temp.left.parrent = temp.parrent;} }

else {// 兩個兒子都有Node left = getLeft(temp);//上面還有父節點（爺爺）if (compare(left.data, temp.parrent.data)) {//比爺爺節點大，下圖中的89temp.parrent.right = left;left.parrent = temp.parrent;} else {//比爺爺節點小，下圖中的45temp.parrent.left = left;left.parrent = temp.parrent;} }

總結

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

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