算法学习(七): 二叉树和二叉树搜索

2018-06-29 本文已影响55人 squall1744

树的定义

树(Tree): 是一种无向图(undirected graph), 其中任意两个顶点间存在唯一一条路径。或者说, 只要没有回路的连通图就是树。
一个(可能是非线性的)数据结构, 由结点, 顶点和边组成, 没有任何环

下面的就是典型的树:

下面这两种就不是树：

第一个两个顶点之间存在多条路
第二个形成了环路

二叉树

二叉树
上面的链接是关于二叉树的介绍, 大家可以先通过链接学习二叉树的相关概念

二叉树的属性

二叉树第i层最多有2ⁱ个节点(这里的层数是从0开始)
一个深度为k的二叉树树最多有2^(k+1)-1个节点(深度从0开始)
一个完全二叉树有n个节点, 树的深度则是log(n+1)-1 (深度从0开始)
在完全二叉树中, 如果从根节点开始为节点编号, 对于节点编号为k的节点, 其左孩子的编号为2k+1, 右孩子为2k+2, 其中跟节点编号为0

二叉树的遍历

前序遍历: 父节点, 左孩子, 右孩子
中序遍历: 左孩子, 父节点, 右孩子
后序遍历: 左孩子, 右孩子，父节点

二叉树遍历的框架

创建一个Node类用来保存二叉树结构
preOrderUnRecur方法实现非递归的二叉树前序遍历
inOrderUnRecur方法实现非递归的二叉树中序遍历
posOrderUnRecur方法实现非递归的二叉树后序遍历

import java.util.Stack;

public class PreInPosTraversal {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static void preOrderUnRecur(Node head) {}

    public static void inOrderUnRecur(Node head) {}

    public static void posOrderUnRecur(Node head) {}


    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);

    
        // unrecursive
        System.out.println("============unrecursive=============");
        preOrderUnRecur(head);
        inOrderUnRecur(head);
        posOrderUnRecur(head);
    }
}

非递归实现前序遍历

public static void preOrderUnRecur(Node head) {
  System.out.print("pre-order: ");
  if (head != null) {
    Stack<Node> stack = new Stack<Node>();
    stack.add(head);
    while (!stack.isEmpty()) {
      head = stack.pop();
      System.out.print(head.value + " ");
      if (head.right != null) {
        stack.push(head.right);
      }
      if (head.left != null) {
        stack.push(head.left);
      }
    }
  }
  System.out.println();
}

非递归实现中序遍历

首先对左子树进行迭代, 将非空节点入栈, 直到节点为空
当前节点为空时进行出栈操作, 并访问栈顶节点, 将当前节点用右子节点代替

public static void inOrderUnRecur(Node head) {
  System.out.print("in-order: ");
  if (head != null) {
    Stack<Node> stack = new Stack<Node>();
    while (!stack.isEmpty() || head != null) {
      if (head != null) {
        stack.push(head);
        head = head.left;
      } else {
        head = stack.pop();
        System.out.print(head.value + " ");
        head = head.right;
      }
    }
  }
  System.out.println();
}

非递归实现后序遍历

用两个栈实现后序遍历：

public static void posOrderUnRecur(Node head) {
  System.out.print("pos-order: ");
  if (head != null) {
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();
    s1.push(head);
    while (!s1.isEmpty()) {
      head = s1.pop();
      s2.push(head);
      if (head.left != null) {
        s1.push(head.left);
      }
      if (head.right != null) {
        s1.push(head.right);
      }
    }
    while (!s2.isEmpty()) {
      System.out.print(s2.pop().value + " ");
    }
  }
  System.out.println();
}

用一个栈实现后序遍历:
这个有兴趣的可以了解下, 平时不太能用的到, 因为用两个栈的空间复杂度跟一个一样, 并且代码简单, 所以通常用两个栈来实现后序遍历就可以了

def postOrderTraversalOneStack(self):
      nodeStack = stack.Stack()
      curNode = self.root
      newNode = None
      while not nodeStack.isEmpty() or curNode != None:
        while curNode != None:
          newNode = NodeWithFlag(curNode, False)
          nodeStack.push(newNode)
          curNode = curNode.left

        newNode = nodeStack.pop()
        curNode = newNode.node
        if not newNode.flag:
          newNode.flag = True
          nodeStack.push(newNode)
          curNode = curNode.right
        else:
          print(curNode.key)
          curNode = None

二叉树相关算法

得到一个二叉树节点的后继节点

有一个二叉树, 给定一个节点, 找出他的后继节点,
这个二叉树的节点有个特殊的地方, 每个节点不但有指向左孩子的left和右孩子的right, 还有一个指向父节点的parent，在二叉树的中序遍历的序列中, node的下一个节点叫做node的后继节点

分析：
这里先要给出、几个概念：

中序前驱：
中序遍历时, 某个节点的前一个遍历的节点叫前驱
中序后继:
中序遍历时, 某个节点的后一个遍历的节点叫做后继
二叉搜索树
对于二叉树中任意一个元素, 若其左子树中所有元素的值都小于该元素的值, 并且其右子树中所有元素的值都大于该元素的值, 这个二叉树就叫做搜索二叉树
二叉搜索树中序遍历后的结果是从小到大依次排列的, 这也是我们判断一个二叉树是不是二叉搜索树的依据

算法流程:

当节点有右孩子时, 节点的后继就是以右孩子为根的二叉树的最后一个左孩子
当节点没有右孩子时, 一直沿着父节点往上找, 直到找到某个节点是其父节点的第一个左孩子, 则某个节点的父节点就是目标节点的后继

public SuccessorNode {

    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node getSuccessorNode(Node node) {
        if (node == null) {
            return node;
        }
        if (node.right != null) {
            return getLeftMost(node.right);
        } else {
            Node parent = node.parent;
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    public static Node getLeftMost(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

二叉树的序列化和反序列化

二叉树的序列化：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。
二叉树的反序列化: 把字符串格式保存的二叉树文本转换成内存中的二叉树, 应按照序列化时的遍历方式来反序列化, 如序列化时用的是前序遍历, 则反序列化也必须用前序遍历的方式来反序列化

二叉树序列化的方法如下:

先规定按某个方式遍历, 遇到元素时,保存元素的值, 并用下滑下_隔开, 如:
我们遍历第一个元素为1, 第二个为23, 则记录方式为1_23_
遍历某个元素的左节点时, 如果其左节点为空, 用#符号记录, 同样的遍历到右节点时, 若右节点为空, 也用#记录
整个二叉树遍历完后记录的字符串结构即为序列化结果

我们还可以利用按层遍历二叉树来序列化:

准备一个队列, 在把head加入队列前先打印head的值,比如head的值为1, 我们记录为1_
从队列弹出一个数, 打印head的左孩子和右孩子的值, 然后把左孩子和右孩子存入队列中, 如果某个孩子不存在, 仅打印#_, 无需存入队列
继续从队列中弹出一个数, 然后继续打印head左孩子的左孩子和右孩子的值,并存入队列, 跟上面一样如果没有就仅打印#_
继续从队列弹出一个数, 打印head右孩子的左孩子和右孩子的值,并存入队列,如果没有就打印#_
重复弹出一个数, 然后打印下一个元素的左右孩子, 存入队列, 没有就打印#_, 直到队列中所有元素都弹出为止

按层遍历的反序列化:

序列化和反序列化的代码比较简单, 请大家自己试着写出来吧

判断一棵二叉树是否是平衡二叉树

平衡二叉树:
对于二叉树中任意节点, 其左子树的高度和右子树的高度差不超过1

此类问题的套路:
适用情况为考察每一个节点为头的整棵子树
利用递归来解决问题

先写主函数框架

public static boolean isBalance() {
  ...
}

分析我们需要得到的数据
判断一棵树是否是平衡二叉树需要满足两点: 左子树和右子树都是平衡二叉树, 左子树和右子树的高度差不大于1。为了判断是否平衡二叉树, 我们需要得到以下数据:
- 左子树是否平衡二叉树
- 右子树是否平衡二叉树
- 左子树的高度
- 右子树的高度
整合信息,定义抽象数据类型(ADT)
进一步抽象数据, 把所有数据整合, 设计返回整合后数据的抽象数据类型
我们发现如果不考虑左子树和右子树, 对于每一个节点,我们都需要两个数据: 以该节点为根的二叉树是否为平衡二叉树, 节点的高度。我们可以用一个抽象数据类型来获得这两个数据, 这道题的情况是左右刚好需要的数据是一样的, 如果左右子树需要的数据不一样, 我们把所有需要的数据都整合成一个ADT, 在递归时对左右子树返回其各自需要的数据即可
- isBalance 布尔类型
- height 整型

public static class ReturnData {
  public boolean isBalance;
  public int height;
  public ReturnData(boolean, isBalance, int height) {
    this.isBalance = isBalance;
    this.height = height;
  }
}

设计递归函数
先确定简单情况
设计递归时, 默认左树返回所需的信息, 默认右树也返回所需的信息, 然后自身也同样返回相同的所需信息

通过递归先得到所有节点的左子树和右子树是否为平衡二叉树以及他们的高度, 并根据这些数据判断以该节点为根的二叉树是否为平衡二叉树, 层层往上, 最终就能得到整个二叉树是否为平衡二叉树

public static ReturnData process(Node node) {
  //简单情况
  if (node == null) {
    return new ReturnData(true, 0);
  }
  //默认左子树返回isBalance和height
  ReturnData leftData = process(node.left);

  //默认右子树返回isBalance和height
  ReturnData rightData = process(node.right);

  //自身判断并返回相同的所需信息
  int height = 0;
  boolean isBalance = true;
  if (!leftData.isBalance || !rightData.isBalance ) {
    isBalance = false;
  }
  if (Math.abs(leftData.height - rightData.height) > 1) {
    isBalance = false;
  }
  height = Math.max(leftData.height, rightData.height) + 1
  return new ReturnData(isBalance, height)
}

在主函数中调用递归函数

public static boolean isBalance() {
  return process(head).isBalance;
}

判断一棵树是否是完全二叉树

思路:
按层遍历

如果某个节点有右孩子没有左孩子, 则不是完全二叉树
如果某个节点k左右孩子不全, 则他之后的节点必须都是叶节点

  public static boolean isCBT(Node head) {
    if (head == null) {
      return true;
    }
    Queue<Node> queue = new LinkedList<Node>();
    boolean leaf = false; // 触发检测k之后节点全是叶节点的开关
    Node left = null;
    Node right = null;
    queue.offer(head);
    while (!queue.isEmpty()) {
      head = queue.poll();
      left = head.left;
      right = head.right;
      if ((left == null && right != null) || (leaf && (left !=null || right != null))) {
        return false;
      }
      if (left == null && right == null) {
        leaf = true;
      }
      if (left !=null) {
        queue.offer(left);
      }
      if (right != null) {
        queue.offer(right);
      }
    }
    return true;
  }

已知一棵完全二叉树, 求其节点的个数

要求: 时间复杂度低于O(n)， N为这棵树的节点个数

// 保证head是一棵完全二叉树
public static int nodeNum(Node node) {
  if (node == null) {
    return 0;
  }
  return bs(head, 0, mostLeftLevel(head, 0));
}

public static int bs(Node node, int i, int allLevel) {
  if (i == allLevel) {
    return 1;
  }
  if (mostLeftLevel(node.right, i + 1) == allLevel) {
    return (1<<(allLevel - i)) + bs(node.right, i + 1, allLevel);
  }else {
    return (1<<(allLevel - i - 1)) + bs(node.left, i + 1, allLevel);
  }
}

public static int mostLeftLevel(Node node, int i) {
   while (node != null) {
    i++;
    node = node.left;
  }
  return i - 1;
}