数据结构与算法(3)——树（二叉、二叉搜索树）
2018-07-11 本文已影响139人
我没有三颗心脏
前言：题图无关，现在开始来学习学习树相关的知识
前序文章：
- 数据结构与算法(1)——数组与链表（https://www.jianshu.com/p/7b93b3570875）
- 数据结构与算法(2)——栈和队列(https://www.jianshu.com/p/5087c751cb42)
树
什么是树
树是一种类似于链表的数据结构，不过链表的结点是以线性方式简单地指向其后继结点，而树的一个结点可以指向许多个结点；数是一种典型的非线性结构；树结构是以表达具有层次特性的图结构的一种方法；
相关术语
- 根节点：根节点是一个没有双亲结点的结点，一棵树中最多有一个根节点（如上图的结点A就是根节点）；
- 边：边表示从双亲结点到孩子结点的链接（如上图中所有的链接）；
- 叶子结点：没有孩子结点的结点叫作叶子结点（如E、J、K、H和I）；
- 兄弟结点：拥有相同双亲结点的所有孩子结点叫作兄弟结点（B、C、D是A的兄弟结点，E、F是B的兄弟结点）；
- 祖先结点：如果存在一条从根节点到结点q的路径，其结点p出现在这条路径上，那么就可以吧结点p叫作结点q的祖先结点，结点q也叫做p的子孙结点（例如，A、C和G是K的祖先结点）；
- 结点的大小：结点的大小是指子孙的个数，包括其自身。（子树C的大小为3）；
- 树的层：位于相同深度的所有结点的集合叫作树的层（B、C和D具有相同的层，上图的结构有0/1/2/3四个层）；
- 结点的深度：是指从根节点到该节点的路径长度（G点的深度为2，A—C—G）；
- 结点的高度：是指从该节点到最深节点的路径长度，树的高度是指从根节点到书中最深结点的路径长度，只含有根节点的树的高度为0。（B的高度为2，B—F—J）；
- 树的高度：是树中所有结点高度的最大值，树的深度是树中所有结点深度的最大值，对于同一棵树，其深度和高度是相同的，但是对于各个结点，其深度和高度不一定相同；
二叉树
如果一棵树中的每个结点有0，1或者2个孩子结点，那么这棵树就称为二叉树；空树也是一颗有效的二叉树，一颗二叉树可以看做是由根节点和两棵不相交的子树（分别称为左子树和右子树）组成，如下图所示。
二叉树的类型
严格二叉树：二叉树中的每个节点要么有两个孩子结点，要么没有孩子结点
满二叉树：二叉树中的每个结点恰好有两个孩子结点且所有叶子结点都在同一层
完全二叉树：在定义完全二叉树之前，假定二叉树的高度为h；对于完全二叉树，如果将所有结点从根节点开始从左至右，从上至下，依次编号（假定根节点的编号为1），那么僵得到从1~n（n为结点总数）的完整序列，在遍历过程中对于空指针也赋予编号，如果所有伽椰子结点的深度为h或h-1，且在结点编号序列中没有漏掉任何数字，那么这样的二叉树叫作完全二叉树。
二叉树的应用
- 编译器中的表达式树；
- 用于数据压缩算法中的赫夫曼编码树；
- 支持在集合中查找、插入和删除，其平均时间复杂度为O(lognn)的二叉搜索树（BST）；
- 优先队列（PQ），它支持以对数时间（最坏情况下）对集合中的最小（或最大）数据元素进行搜索和删除；
二叉树的遍历
访问树中所有结点的过程叫作树的遍历，在遍历过程中，每个结点只能被处理一次，尽管其有可能被访问多次；根据结点处理顺序的不同，。可以定义不同的遍历方法，遍历分类可以根据当前节点被处理的顺序来划分：
前序遍历
在前序遍历中，每个结点都是在它的子树遍历之前进行处理，这是最容易理解的便利方法，然而，尽管每个结点在其子树之前进行了处理，但在向下移动的过程仍然需要保留一些信息，以上图为例，首先访问结点1，随后遍历其左子树，最后遍历其右子树，因此当左子树遍历完后，必须要返回到其右子树来继续遍历；为了能够在左子树遍历完成后移动到右子树，必须保留根节点的信息，能够实现该信息存储的抽象数据类型显而易见是栈，由于它是LIFO的结构，所以它可以以逆序来汇过去该信息并返回到右子树；
前序遍历可以如下定义：
- 访问根节点；
- 按前序遍历方式遍历左子树；
- 按前序遍历方式遍历右子树；
利用前序遍历方法上图所示的树的输出序列为：1 2 4 5 3 6 7
void preOrder(BinaryTreeNode root) {
if (null != root) {
System.out.println(root.getData());
preOrder(root.getLeft());
preOrder(root.getRight());
}
}
中序遍历
在中序遍历中，根节点的访问在两棵子树的遍历中间完成，中序遍历如下定义：
- 按中序遍历方式遍历左子树；
- 访问根节点；
- 按中序遍历方式遍历右子树；
基于中序遍历，上图所示树的中序遍历输出顺序为：4 2 5 1 6 3 7
void inOrder(BinaryTreeNode root) {
if (null != root) {
inOrder(root.getLeft());
System.out.println(root.getData());
inOrder(root.getRight());
}
}
后序遍历
在后续遍历中，根节点的访问是在其两棵子树都遍历完成后进行的，后续遍历如下定义：
- 按后序遍历左子树；
- 按后序遍历右子树；
- 访问根节点；
对上图所示的二叉树，后续遍历产生的输出序列为：4 5 2 6 7 3 1
void postOrder(BinaryTreeNode root) {
if (null != root) {
postOrder(root.getLeft());
postOrder(root.getRight());
System.out.println(root.getData());
}
}
层次遍历
层次遍历的定义如下：
- 访问根节点；
- 在访问第l层时，将l+1层的节点按顺序保存在队列中；
- 进入下一层并访问该层的所有结点；
- 重复上述操作直至所有层都访问完；
对于上图所示的二叉树，层次遍历产生的输出序列为：1 2 3 4 5 6 7
void levelOrder(BinaryTreeNode root) {
BinaryTreeNode temp;
LoopQueue Q = new LoopQueue();
if (null == root) {
return;
}
Q.enqueue(root);
while (!Q.isEmpty()) {
temp = Q.dequeue();
// 处理当前节点
System.out.println(temp.getData());
if (temp.getLeft()) {
Q.enqueue(temp.getLeft());
}
if (temp.getRight()) {
Q.enqueue(temp.getRight());
}
}
// 删除队列中的所有数据
Q.deletequeue();
}
二叉搜索树
在二叉搜索树中，所有左子树结点的元素小于根节点的数据，所有右子树结点的元素大于根节点数据，注意，树中的每个结点都应满足这个性质；
实现自己的二叉搜索树
其中包含了常用的一些方法，包括几种遍历方法还有查询、删除等，仅供参考：
public class BST<E extends Comparable<E>> {
private class Node{
public E e;
public Node left, right;
public Node(E e){
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int size;
public BST(){
root = null;
size = 0;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
// 向二分搜索树中添加新的元素e
public void add(E e){
root = add(root, e);
}
// 向以node为根的二分搜索树中插入元素e，递归算法
// 返回插入新节点后二分搜索树的根
private Node add(Node node, E e){
if(node == null){
size ++;
return new Node(e);
}
if(e.compareTo(node.e) < 0)
node.left = add(node.left, e);
else if(e.compareTo(node.e) > 0)
node.right = add(node.right, e);
return node;
}
// 看二分搜索树中是否包含元素e
public boolean contains(E e){
return contains(root, e);
}
// 看以node为根的二分搜索树中是否包含元素e, 递归算法
private boolean contains(Node node, E e){
if(node == null)
return false;
if(e.compareTo(node.e) == 0)
return true;
else if(e.compareTo(node.e) < 0)
return contains(node.left, e);
else // e.compareTo(node.e) > 0
return contains(node.right, e);
}
// 二分搜索树的前序遍历
public void preOrder(){
preOrder(root);
}
// 前序遍历以node为根的二分搜索树, 递归算法
private void preOrder(Node node){
if(node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
// 二分搜索树的非递归前序遍历
public void preOrderNR(){
Stack<Node> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Node cur = stack.pop();
System.out.println(cur.e);
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
}
}
// 二分搜索树的中序遍历
public void inOrder(){
inOrder(root);
}
// 中序遍历以node为根的二分搜索树, 递归算法
private void inOrder(Node node){
if(node == null)
return;
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
// 二分搜索树的后序遍历
public void postOrder(){
postOrder(root);
}
// 后序遍历以node为根的二分搜索树, 递归算法
private void postOrder(Node node){
if(node == null)
return;
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
// 二分搜索树的层序遍历
public void levelOrder(){
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node cur = q.remove();
System.out.println(cur.e);
if(cur.left != null)
q.add(cur.left);
if(cur.right != null)
q.add(cur.right);
}
}
// 寻找二分搜索树的最小元素
public E minimum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty!");
return minimum(root).e;
}
// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node){
if(node.left == null)
return node;
return minimum(node.left);
}
// 寻找二分搜索树的最大元素
public E maximum(){
if(size == 0)
throw new IllegalArgumentException("BST is empty");
return maximum(root).e;
}
// 返回以node为根的二分搜索树的最大值所在的节点
private Node maximum(Node node){
if(node.right == null)
return node;
return maximum(node.right);
}
// 从二分搜索树中删除最小值所在节点, 返回最小值
public E removeMin(){
E ret = minimum();
root = removeMin(root);
return ret;
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin(Node node){
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// 从二分搜索树中删除最大值所在节点
public E removeMax(){
E ret = maximum();
root = removeMax(root);
return ret;
}
// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
private Node removeMax(Node node){
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
// 从二分搜索树中删除元素为e的节点
public void remove(E e){
root = remove(root, e);
}
// 删除掉以node为根的二分搜索树中值为e的节点, 递归算法
// 返回删除节点后新的二分搜索树的根
private Node remove(Node node, E e){
if( node == null )
return null;
if( e.compareTo(node.e) < 0 ){
node.left = remove(node.left , e);
return node;
}
else if(e.compareTo(node.e) > 0 ){
node.right = remove(node.right, e);
return node;
}
else{ // e.compareTo(node.e) == 0
// 待删除节点左子树为空的情况
if(node.left == null){
Node rightNode = node.right;
node.right = null;
size --;
return rightNode;
}
// 待删除节点右子树为空的情况
if(node.right == null){
Node leftNode = node.left;
node.left = null;
size --;
return leftNode;
}
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
generateBSTString(root, 0, res);
return res.toString();
}
// 生成以node为根节点，深度为depth的描述二叉树的字符串
private void generateBSTString(Node node, int depth, StringBuilder res){
if(node == null){
res.append(generateDepthString(depth) + "null\n");
return;
}
res.append(generateDepthString(depth) + node.e +"\n");
generateBSTString(node.left, depth + 1, res);
generateBSTString(node.right, depth + 1, res);
}
private String generateDepthString(int depth){
StringBuilder res = new StringBuilder();
for(int i = 0 ; i < depth ; i ++)
res.append("--");
return res.toString();
}
}
LeetCode相关题目整理
94.二叉树的中序遍历
我的答案：（1ms）
public List<Integer> inorderTraversal(TreeNode root) {
List result = new ArrayList();
if (null != root) {
result.addAll(inorderTraversal(root.left));
result.add(root.val);
result.addAll(inorderTraversal(root.right));
}
return result;
}
参考答案：（0ms）
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
traversal(root, list);
return list;
}
public void traversal(TreeNode root,List<Integer> list) {
if(root!=null){
traversal(root.left, list);
list.add(root.val);
traversal(root.right, list);
}
}
98. 验证二叉搜索树
我的答案：（53ms）
private static int INT_MIN = Integer.MIN_VALUE;
private static int INT_MAX = Integer.MAX_VALUE;
public boolean isValidBST(TreeNode root) {
// 如果节点为空则满足二叉搜索树条件
if (null == root) {
return true;
}
// 如果左孩子结点大于了根节点则返回false
if (null != root.left && findMax(root.left) > root.val) {
return false;
}
// 如果右孩子结点小于了根节点则返回false
if (null != root.right && findMin(root.right) < root.val) {
return false;
}
// 递归判断左子树和右子树，若其中有一颗不是BST树，则返回false
if (!isValidBST(root.left) || !isValidBST(root.right)) {
return false;
}
// 通过所有判断则是一颗BST树
return true;
}
/**
* 找到一颗非空树中的最大值
*
* @param root
* @return
*/
private int findMax(TreeNode root) {
int maxVal = INT_MIN;
int leftMaxVal = INT_MIN;
int rightMaxVal = INT_MIN;
if (null != root) {
// 最大值默认等于当前节点值
maxVal = root.val;
leftMaxVal = findMax(root.left);
rightMaxVal = findMax(root.right);
// maxVal等于当前maxVal与leftMaxVal中较大的一个
maxVal = maxVal > leftMaxVal ? maxVal : leftMaxVal;
// maxVal等于当前maxVal与rightMaxVal中较大的一个
maxVal = maxVal > rightMaxVal ? maxVal : rightMaxVal;
}
return maxVal;
}
/**
* 找到一颗非空树的最小值
*
* @param root
* @return
*/
private int findMin(TreeNode root) {
int minVal = INT_MAX;
int leftMinVal = INT_MAX;
int rightMinVal = INT_MAX;
if (null != root) {
// 最小值默认为当前节点值
minVal = root.val;
leftMinVal = findMin(root.left);
rightMinVal = findMin(root.right);
// minVal等于当前minVal与leftMinVal中较小的一个
minVal = minVal < leftMinVal ? minVal : leftMinVal;
// minVal等于当前minVal与rightMinVal中较小的一个
minVal = minVal < rightMinVal ? minVal : rightMinVal;
}
return minVal;
}
自己写的时候提交错了很多次..没有掌握到二分搜索树的精髓..
参考答案：（2ms）
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
public boolean valid(TreeNode root, long low, long high) {
if (root == null) return true;
if (root.val <= low || root.val >= high) return false;
return valid(root.left, low, root.val) && valid(root.right, root.val, high);
}
这答案写得我服了..真服..
101. 对称二叉树（剑指Offer面试题28）
参考答案：（12ms）
public boolean isSymmetric(TreeNode root) {
return isSymmetric(root, root);
}
public boolean isSymmetric(TreeNode root1, TreeNode root2) {
if (null == root1 && null == root2) {
return true;
}
if (null == root1 || null == root2) {
return false;
}
if (root1.val != root2.val) {
return false;
}
return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
}
自己做的思路是使用中序遍历来判断（转成数组之后是对称的），但是出了很多问题，就是需要考虑null值，中序遍历中并不能很好地把一棵树保存为一个完整二叉树的样子..所以看了下参考答案..写得服..
104. 二叉树的最大深度（剑指Offer面试题55）
我的答案：（3ms）
public int maxDepth(TreeNode root) {
int leftHeight, rightHeight;
if (null == root) {
return 0;
} else { // 计算每个子树的高度
leftHeight = maxDepth(root.left);
rightHeight = maxDepth(root.right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
}
参考答案：（0ms）
public int maxDepth(TreeNode root) {
if(root==null)
return 0;
return Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
}
105. 从前序与中序遍历序列构造二叉树（剑指Offer面试题7）
参考答案：（2ms）
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
return buildTree(preorder, inorder, 0, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int ps, int is, int ie) {
int val = preorder[ps];
TreeNode node = new TreeNode(val);
int iRoot = ie;
while (iRoot > is) {
if (val == inorder[iRoot]) {
break;
}
iRoot--;
}
if (iRoot > is) {
node.left = buildTree(preorder, inorder, ps + 1, is, iRoot - 1);
}
if (iRoot < ie) {
node.right = buildTree(preorder, inorder, ps + 1 + (iRoot - is), iRoot + 1, ie);
}
return node;
}
思路是这样的：在二叉树的前序遍历序列中，第一个数字总是树的根节点的值，但在中序遍历序列中，根节点的值保存在序列的中间，左子树的节点的值位于根节点的值的左边，而右子树则相反，然后既然找到了左右子树我们又可以使用同样的方法在前序和中序中分别构建左右子树，这样我们就能够使用递归的方法完成；（上面算法中的ps、is、ie分别表示前序的开始位置，中序的开始位置和中序的结束位置；）
113. 路径总和 II（剑指Offer面试题34）
参考答案：（3ms）
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<Integer> nodeList = new ArrayList<Integer>();
List<List<Integer>> sumList = new ArrayList<List<Integer>>();
if (root == null) {
return sumList;
}
pathSum2(root, sum, sumList, nodeList);
return sumList;
}
public void pathSum2(TreeNode root, int target,
List<List<Integer>> sumList, List<Integer> nodeList) {
if (root.left == null && root.right == null) {
nodeList.add(root.val);
int sum = 0;
for (Integer integer : nodeList) {
sum += integer;
}
if (sum == target) {
sumList.add(new ArrayList<Integer>(nodeList));
}
return;
}
nodeList.add(root.val);
if (root.left != null) {
pathSum2(root.left, target, sumList, nodeList);
nodeList.remove(nodeList.size() - 1);
}
if (root.right != null) {
pathSum2(root.right, target, sumList, nodeList);
nodeList.remove(nodeList.size() - 1);
}
}
230. 二叉搜索树中第K小的元素（类似剑指Offer面试题54）
我的答案：（23ms）
public int kthSmallest(TreeNode root, int k) {
// 正确性判断
if (null == root || k < 1) {
return -1;
}
List<Integer> result = preOrder(root);
// 从小到大排序
Collections.sort(result);
return result.get(k - 1);
}
/**
* 遍历整棵树并返回一个List
*
* @param root
* @return
*/
private List<Integer> preOrder(TreeNode root) {
List result = new ArrayList();
if (null != root) {
result.add(root.val);
result.addAll(preOrder(root.left));
result.addAll(preOrder(root.right));
}
return result;
}
贼蠢，完全没有用到二叉搜索树的特性
参考答案：（1ms）
public int kthSmallest(TreeNode root, int k) {
int count = countNodes(root.left);
if (k <= count) {
return kthSmallest(root.left, k);
} else if (k > count + 1) {
return kthSmallest(root.right, k - 1 - count);
}
return root.val;
}
public int countNodes(TreeNode n) {
if (n == null) return 0;
return 1 + countNodes(n.left) + countNodes(n.right);
}
449. 序列化二叉搜索树（类似剑指Offer面试题37）
参考答案：（12ms）
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuffer sb = new StringBuffer();
preOrder(root,sb);
return sb.toString();
}
private static void preOrder(TreeNode root, StringBuffer sb){
if(root==null)
return;
sb.append(root.val).append('#');
preOrder(root.left,sb);
preOrder(root.right,sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data==null)
return null;
int val =0;
TreeNode root = null;
for(int i=0;i<data.length();i++){
if(data.charAt(i)!='#'){
val = val*10+(data.charAt(i)-'0');
}else{
root = insert(root,val);
val=0;
}
}
return root;
}
private static TreeNode insert(TreeNode root,int val){
if(root==null)
return new TreeNode(val);
if(root.val<val)
root.right = insert(root.right,val);
else
root.left = insert(root.left,val);
return root;
}
572. 另一个树的子树（类似剑指Offer面试题26）
参考答案：（15ms）
public boolean isSubtree(TreeNode s, TreeNode t) {
// Write your code here
if (s == null) {
return t == null;
}
if (s.val == t.val && isSametree(s, t)) {
return true;
}
return isSubtree(s.left, t) | isSubtree(s.right, t);
}
private boolean isSametree(TreeNode s, TreeNode t) {
if (s == null) {
return t == null;
}
if (t == null) {
return false;
}
if (s.val != t.val) {
return false;
}
return isSametree(s.left, t.left) & isSametree(s.right, t.right);
}
我的第一个反应还是去把两棵树的前序遍历的数组弄出来然后判断是否为子集，但是树这样的天然递归结构这样写很自然...
简单总结
还是只是简单复习了一下树的相关知识吧，通过刷LeetCode题目还有参照着剑指Offer对二叉树、二叉搜索树仅仅这两种结构有了一个较深的认识，因为后续还会继续用到，所以这里简单复习一下也无所谓，不过看着题目倒是感觉这样的结构很容易考面试题啊，因为这些结构既重要考点又多...
欢迎转载，转载请注明出处！
简书ID：@我没有三颗心脏
github：wmyskxz
欢迎关注公众微信号：wmyskxz_javaweb
分享自己的Java Web学习之路以及各种Java学习资料
