數據結構-樹詳解

樹簡介

樹存儲和組織具有層級結構的數據（例：公司職級），就是一顆倒立生長的樹。
屬性：

遞歸
n個節點有n-1個連接
節點x的深度：節點x到根節點的最長路徑
節點x的高度：節點x到葉子節點的最長路徑

二叉樹

完美、完全、平衡二叉樹

二叉樹：每個節點最多有兩個子節點（左孩子，有孩子）。在第i層最多有2ⁱ個節點。
完美二叉樹、完全二叉樹查看之前文章
平衡二叉樹：空樹或左子樹和右子樹高度差不超過1
請添加圖片描述
?
二叉樹在內存中的存儲方式：

動態創建節點
數組

二叉樹高度實現

求二叉樹高度的實現方式：計算左右子樹高度取較大者+1
在這里插入圖片描述

class TreeNode{int data;TreeNode left;TreeNode right;public TreeNode(int data){this.data = data;this.left = null;this.right = null;}
}
public class DataStruct {//高度public int findHight(TreeNode root){if (root == null){return -1;}return Math.max(findHight(root.left),findHight(root.right))+1;}//遍歷public static void main(String[] args) {DataStruct ds = new DataStruct();TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.left.right.left = new TreeNode(8);root.left.right.right = new TreeNode(9);root.right = new TreeNode(3);root.right.left = new TreeNode(6);root.right.right = new TreeNode(7);System.out.println(ds.findHight(root));}
}

二叉樹遍歷實現

樹的遍歷算法兩類：廣度優先（同一層級，下圖舉例即 F,D,J,B,E,G,K,A,C,I,H）、深度優先（左子樹、根節點、右子樹三者順序可變）
深度優先：前序遍歷—根節點-左子樹-右子樹（F,D,B,A,C,E,J,G,I,H,K）
??????????????????中序遍歷—左子樹-根節點-右子樹（A,B,C,D,E,F,G,H,I,J,K）
??????????????????后續遍歷—左子樹-右子樹-根節點（A,C,B,E,D,H,I,G,K,J,F）

在這里插入圖片描述

廣度優先使用隊列來實現：取出節點的同時，讓他的孩子入隊。f(n)=O(n)，S(n)=O(1)最好情況，S(n)=O(n)最壞情況。
在這里插入圖片描述

import java.util.LinkedList;
import java.util.Queue;
class TreeNode{char data;TreeNode left;TreeNode right;public TreeNode(char data){this.data = data;this.left = null;this.right = null;}
}
public class DataStruct {//廣度優先public void levelOrder(TreeNode root){if (root == null){return;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()){TreeNode poll = queue.poll();System.out.print(poll.data + " ");if (poll.left != null){queue.add(poll.left);}if (poll.right != null){queue.add(poll.right);}}return;}//深度優先public void preOrder(TreeNode root){if(root == null){return;}System.out.print(root.data + " ");preOrder(root.left);preOrder(root.right);}public void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.data + " ");inOrder(root.right);}public void postOrder(TreeNode root){if(root == null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.data + " ");}public static void main(String[] args) {DataStruct ds = new DataStruct();TreeNode root = new TreeNode('F');root.left = new TreeNode('D');root.left.left = new TreeNode('B');root.left.right = new TreeNode('E');root.left.left.left = new TreeNode('A');root.left.left.right = new TreeNode('C');root.right = new TreeNode('J');root.right.left = new TreeNode('G');root.right.right = new TreeNode('K');root.right.left.right= new TreeNode('I');root.right.left.right.left = new TreeNode('H');System.out.println("廣度優先：");ds.levelOrder(root);System.out.println();System.out.println("前序遍歷：");ds.preOrder(root);System.out.println();System.out.println("中序遍歷：");ds.inOrder(root);System.out.println();System.out.println("后序遍歷：");ds.postOrder(root);}
}

二叉搜索樹

概述

搜索：用數組、鏈表進行搜索耗時O(n)。如果是已排序的數組，用二分查找(可查看之前算法文章)耗時O(logn)。

數據結構	數組	鏈表	二分查找	二叉搜索樹
搜索	O(n)	O(n)	O(logn)	O(logn)
插入	O(1)	O(1)	O(n)	O(logn)
刪除	O(n)	O(n)	O(n)	O(logn)

二叉搜索樹：對于任意節點，左子樹上的所有節點值都小于它，右子樹上的所有節點值都大于它，并且這種性質在每個子樹上都遞歸成立。
請添加圖片描述
二叉搜索樹搜索時間復雜度O(logn)原理：每次比較不是往左就是往右，每次數量都會減少一半，跟二分查找同理。但需要注意二叉搜索樹需要是平衡的，否則時間復雜度>O(logn)，下圖最壞情況是O(n)
在這里插入圖片描述

查找最小值和最大值

根據二叉搜索樹的特性，最小值一定在左邊，最大值一定在右邊

class TreeNode{int data;TreeNode left;TreeNode right;public TreeNode(int data){this.data = data;this.left = null;this.right = null;}
}
public class DataStruct {//迭代寫法public int findMin(TreeNode root){TreeNode temp = root;while (temp!=null && temp.left!=null){temp=temp.left;}return temp.data;}//遞歸寫法public int findMin1(TreeNode root){TreeNode temp = root;if (temp==null){return -1;}if (temp.left==null){return temp.data;}return findMin1(temp.left);}public static void main(String[] args) {DataStruct ds = new DataStruct();TreeNode root = new TreeNode(15);root.left = new TreeNode(10);root.left.left = new TreeNode(8);root.left.right = new TreeNode(12);root.right = new TreeNode(20);root.right.left = new TreeNode(17);root.right.right = new TreeNode(25);System.out.print(ds.findMin(root));}
}

判斷是否是二叉搜索樹

對于isSubTreeGreater，isSubTreeLesser也可以換種思路，即尋找最大最小值與父節點比較。
進一步優化：舍去比較大小的遞歸函數，而采用傳入該節點的數據范圍的參數來進行比較。
另一種方法：二叉搜索樹的中序遍歷是排序好的，也可以檢查中序遍歷結果是否排序好了。

class TreeNode{int data;TreeNode left;TreeNode right;public TreeNode(int data){this.data = data;this.left = null;this.right = null;}
}
public class DataStruct {public boolean isSubTreeLesser(TreeNode root,int data){if (root == null){return true;}if (root.data <= data && isSubTreeLesser(root.left, data) && isSubTreeLesser(root.right, data)){return true;}return false;}public boolean isSubTreeGreater(TreeNode root,int data){if (root == null){return true;}if (root.data>=data && isSubTreeGreater(root.left, data) && isSubTreeGreater(root.right, data)){return true;}return false;}public boolean isBinaryTree(TreeNode root){if(root == null){return true;}if (isSubTreeLesser(root.left, root.data) && isSubTreeGreater(root.right, root.data)&& isBinaryTree(root.left) && isBinaryTree(root.right)){return true;}return false;}public boolean isBinaryTree1(TreeNode root,int min,int max){if(root == null){return true;}if (root.data < max && root.data > min && isBinaryTree1(root.left,min,root.data) && isBinaryTree1(root.right,root.data,max)){return true;}return false;}public static void main(String[] args) {DataStruct ds = new DataStruct();TreeNode root = new TreeNode(7);root.left = new TreeNode(4);root.left.left = new TreeNode(1);root.left.right = new TreeNode(6);root.right = new TreeNode(9);System.out.println(ds.isBinaryTree(root));System.out.println(ds.isBinaryTree1(root,Integer.MIN_VALUE,Integer.MAX_VALUE));}
}

二叉搜索樹查詢、插入、刪除實現

在這里插入圖片描述

class TreeNode{int data;TreeNode left;TreeNode right;public TreeNode(int data){this.data = data;this.left = null;this.right = null;}
}
public class DataStruct {public TreeNode insert(TreeNode root, int data){if (root == null){return new TreeNode(data);}if (data<=root.data){root.left=insert(root.left,data);}else {root.right=insert(root.right,data);}return root;}public boolean search(TreeNode root, int data){if (root == null){return false;}if (data==root.data){return true;}if (data<root.data){return search(root.left,data);}else {return search(root.right,data);}}public TreeNode deleteNode(TreeNode root, int data){if (root == null){return null;}if (data<root.data){root.left=deleteNode(root.left,data);}else if (data>root.data){root.right=deleteNode(root.right,data);}else {//要刪除的節點是葉子節點if (root.left==null && root.right==null){return null;}//要刪除的節點只有一個子節點if (root.left==null){return root.right;//用右節點替代當前節點}if (root.right==null){return root.left;}//要刪除的節點有兩個節點，需要用子節點替換當前被刪除的節點，然后刪除子節點//此子節點要么是右子樹中的最小值，要么是左子樹中的最大值TreeNode minNode = root.right;while (minNode.left!=null){minNode = minNode.left;}root.data=minNode.data;root.right=deleteNode(root.right,minNode.data);}return root;}public void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.data + " ");inOrder(root.right);}   public static void main(String[] args) {DataStruct ds = new DataStruct();TreeNode root = null;root=ds.insert(root,15);root=ds.insert(root,10);root=ds.insert(root,20);root=ds.insert(root,8);root=ds.insert(root,12);root=ds.insert(root,17);root=ds.insert(root,25);ds.inOrder(root);System.out.print("\n");System.out.println(ds.search(root,12));System.out.println(ds.search(root,19));ds.deleteNode(root,15);ds.inOrder(root);}
}

尋找某個節點的中序后繼節點

二叉搜索樹的中序遍歷結果是已排序的。中序后繼節點就是排序好的數據中某個節點的下一個數據是什么。如果使用中序遍歷找后繼節點時間復雜度O(n)。

優化：

某節點有右子樹，后繼節點=右子樹的最小值。
某節點無右子樹，后繼節點=最近祖先節點（前提：某節點一定位于祖先節點的左子樹上）。（為了存儲父祖先，需要從跟節點走到指定節點）

10后繼=11，6后繼=8，12后繼=15
在這里插入圖片描述

class TreeNode{int data;TreeNode left;TreeNode right;public TreeNode(int data){this.data = data;this.left = null;this.right = null;}
}
public class DataStruct {public TreeNode getSuccessor(TreeNode root, TreeNode p){if (root == null){return null;}if (p.right != null){return findMin(p.right);}else {TreeNode successor = null;TreeNode temp = root;while (temp != p){if (p.data<temp.data){successor = temp;temp = temp.left;}else {temp=temp.right;}}return successor;}}public TreeNode findMin(TreeNode root){TreeNode temp = root;while (temp!=null && temp.left!=null){temp=temp.left;}return temp;}public static void main(String[] args) {DataStruct ds = new DataStruct();TreeNode root = new TreeNode(15);root.left = new TreeNode(10);root.left.left = new TreeNode(8);root.left.right = new TreeNode(12);root.left.left.left = new TreeNode(6);root.left.right.left = new TreeNode(11);root.right = new TreeNode(20);root.right.left = new TreeNode(17);root.right.right = new TreeNode(25);root.right.left.left = new TreeNode(16);root.right.right.right = new TreeNode(27);System.out.println(ds.getSuccessor(root,root.left.right).data);}
}