数据结构-树详解

树简介

树存储和组织具有层级结构的数据（例：公司职级），就是一颗倒立生长的树。
属性：

递归
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);}
}