[关闭]
@pastqing 2016-03-18T13:03:37.000000Z 字数 8246 阅读 7294

树的常见算法(一)

java


一、二叉树(Binary Tree)

二叉树的基本知识

二叉树定义

  1. public class TreeNode<T> {
  2. TreeNode<T> left;
  3. TreeNode<T> right;
  4. TreeNode<T> parent; //可以没有
  5. T element;
  6. public TreeNode(T element) {
  7. this.element = element;
  8. left = null;
  9. right = null;
  10. parent = null;
  11. }
  12. }

以上是一个简单的二叉树结点的定义。

二叉树的遍历:

  1. public void preOrder(TreeNode<T> node) {
  2. if(node == null)
  3. return;
  4. print(node);
  5. preOrder(node.left);
  6. preOrder(node.right);
  7. }
  1. public void preOrederNotRecursive(TreeNode<T> node) {
  2. TreeNode<T> cur = node;
  3. LinkedList<TreeNode<T>> stack = new LinkedList<TreeNode<T>>();
  4. while(node != null || !stack.isEmpty()) {
  5. while(cur != null) {
  6. //print
  7. print(cur);
  8. stack.push(cur);
  9. cur = cur.left;
  10. }
  11. if(!stack.isEmpty()) {
  12. cur = stack.pop();
  13. cur = cur.right;
  14. }
  15. }
  16. }

为了得到前序的这种遍历顺序,利用辅助栈实现。
前序周游的非递归实现实际是在指针迭代的时候去打印结点。

  1. public void inOrder(TreeNode<T> node) {
  2. if(node == null)
  3. return ;
  4. inOrder(node.left);
  5. //print
  6. print(node);
  7. inOrder(node.right);
  8. }
  1. public void inOrderNotRecursive(TreeNode<T> node) {
  2. TreeNode<T> cur = node;
  3. LikedList<TreeNode<T>> stack = new LikedList<TreeNode<T>>();
  4. while(cur != null || !stack.isEmpty) {
  5. while(cur != null) {
  6. stack.push(cur);
  7. cur = cur.left;
  8. }
  9. if(!stack.isEmpty()) {
  10. //print stack top
  11. cur = stack.pop();
  12. print(cur);
  13. cur = cur.right;
  14. }
  15. }
  16. }

中序遍历的非递归实现方法与前序的代码结构基本相同,但是中序实际上是打印栈顶元素。

  1. public void postOrder(TreeNode<T> node) {
  2. if(node == null)
  3. return ;
  4. postOrder(node.left);
  5. postOrder(node.right);
  6. //print
  7. print(node);
  8. }
  1. public void postOrderNotRecursive(TreeNode<T> node) {
  2. TreeNode<T> cur = node;
  3. //设置一个标记结点,用来确定是第几次访问栈顶元素
  4. TreeNode<T> flag = null;
  5. LinkedList<TreeNode<T>> stack = new LinkedList<TreeNode<T>>();
  6. while(cur != null || !stack.isEmpty()) {
  7. if(cur != null ) {
  8. stack.push(cur);
  9. cur = cur.left;
  10. }else {
  11. cur = stack.peek();
  12. //判断栈顶元素是否是第一次出现,以压入其右子树
  13. if(cur.right != null && cur.right != flag) {
  14. cur = cur.rigth;
  15. stack.push(cur);
  16. //return to left
  17. cur = cur.left;
  18. }else {
  19. cur = stack.pop();
  20. //print
  21. print(cur);
  22. flag = cur;
  23. cur = null;
  24. }
  25. }
  26. }
  27. }

后序遍历的非递归实现:对于任一结点P,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子的结点,此时该结点出现在栈顶,但是此时不能将其出栈并访问,因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理,当访问完其右孩子时,该结点又出现在栈顶,此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出现在栈顶,只有在第二次出现在栈顶时,才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

一、二叉搜索树(Binary Search Tree)

二叉搜索树的基本知识

二叉查找树或者是一颗空树,或者是一颗具有以下特性的非空二叉树:

BST相关算法

算法一:判断一个树是否为BST

思路:中序遍历一个BST会得到一个有序的递增序列,可以利用此性质判断一颗二叉树是否为BST。

  1. private int compare(T e1, T e2) {
  2. return e1.compareTo(e2);
  3. }
  4. public boolean isBST(TreeNode<T> root, T max, T min) {
  5. return isBSTHelper(root, max, min);
  6. }

利用一个辅助函数,引入最大值最小值思想:

  1. public boolean isBSTHelper(TreeNode<T> root, T max, T min) {
  2. if(root == null)
  3. return true;
  4. if( compare(root.element, max) < 0 || (compare(root.element, max) == 0 && root.right == null)
  5. && compare(root.element, min) > 0 || (compare(root.element, min) == 0 && root.left == null)
  6. && isBSTHelper(root.left, root.element, min)
  7. && isBSTHelper(root.right, max, root.element)) {
  8. return true;
  9. }
  10. return false;
  11. }

算法二:BST的插入(insert),删除(delete),查找(search)

  1. public void insert(TreeNode<T> node, T ele) {
  2. if(ele.compareTo(node.element) == -1) {
  3. if(node.left != null) {
  4. insert(node.left, ele);
  5. }else {
  6. node.left = new TreeNode<T>(ele);
  7. }
  8. }else {
  9. if(node.right != null) {
  10. insert(node.right, ele);
  11. }else {
  12. node.right = new TreeNode<T>(ele);
  13. }
  14. }
  15. }

3.如果被删除结点p有左、右两颗子树,则让p的右子树上中序第一个子女,也就是右子树上的最小值来填补p。这样就装换成了第1种和第2种情况了。例如:
删除结点12,这个结点存在左右孩子
bst-remove-case-3-3.png-12.3kB
找到右子树的最小值,来替代被删除结点,转而删除这个替代的结点即可
bst-remove-case-3-4.png-12.9kB
递归找到替代结点,删除即可,又变成了第1或者第2种情况。
bst-remove-case-3-5.png-12.6kB

  1. public void delete(T val) {
  2. root = delete(root, val);
  3. }
  1. /**
  2. * @param the node that the root
  3. * @param the item to remove
  4. * @return the new root
  5. */
  6. public TreeNode<T> delete(TreeNode<T> node, T val) {
  7. if(node == null)
  8. return node;
  9. else {
  10. if(val.compareTo(node.element) < 0) {
  11. node.left = delete(node.left, val);
  12. }else if(val.compareTo(node.element) > 0) {
  13. node.right = delete(node.right, val);
  14. }else {
  15. //two children
  16. if(node.left != null && node.right != null) {
  17. node.element = findMin(node.right).element;
  18. node.right = delete(node.right, node.element);
  19. }else {
  20. node = (node.left != null) ? node.left : node.right;
  21. }
  22. }
  23. }
  24. return node;
  25. }
  1. //find min node
  2. public TreeNode<T> findMin(TreeNode<T> node) {
  3. if(node.left == null)
  4. return node;
  5. else
  6. return findMin(node.left);
  7. }
  1. public boolean search(T val) {
  2. TreeNode<T> r = root;
  3. while(val.compareTo(r.element) != 0) {
  4. if(val.compareTo(r.element) < 0) {
  5. r = r.left;
  6. }else {
  7. r = r.right;
  8. }
  9. if(r == null)
  10. return false;
  11. }
  12. return true;
  13. }

算法三:判断一颗二叉树或者一颗bst是否是平衡树

思路:考虑平衡树的一些特点

  1. public boolean isBanlanced(TreeNode<T> root) {
  2. if(root == null)
  3. return true;
  4. int res = Math.abs(height(root.left) - height(root.right));
  5. return res < 2 && isBanlanced(root.left) && isBanlanced(root.right);
  6. }
  1. //return the tree's height
  2. public int height(TreeNode<T> root) {
  3. if(root == null)
  4. return 0;
  5. return Math.max(height(root.left), height(root.right)) + 1;
  6. }

另外给出一种判断平衡树的优化做法:
isBanlancedHelper返回当前结点的高度, 将计算结果自底向下向上传递,确保每个结点只被计算一次。O(n)

  1. public boolean isBanlancedEffective(TreeNode<T> root) {
  2. return (-1 != isBanlancedHelper(root));
  3. }
  4. private int isBanlancedHelper(TreeNode<T> root) {
  5. if(root == null)
  6. return 0;
  7. int lheight = isBanlancedHelper(root.left);
  8. if(lheight == -1)
  9. return -1;
  10. int rheight = isBanlancedHelper(root.right);
  11. if(rheight == -1)
  12. return -1;
  13. if(Math.abs(lheight - rheight) > 1) {
  14. return -1;
  15. }
  16. return Math.max(lheight, rheight) + 1;
  17. }

算法四:将一个sortArray 转化为bst

用java做还是比较容易的


算法五:Find Next

分别给出preOrder, inOrder, postOrder, levelOrder的后继结点的求出方法。

InOrderSuccessor: 若该结点的右子树存在,则它的后继就是其右子树中最左边的结点,也就是右子树中最小的结点。
遍历bst,找到该结点,则第一个比它大的即为后继结点

  1. public TreeNode<T> inOrderSuccessor(TreeNode<T> node) {
  2. if(node == null)
  3. return null;
  4. if(node.right != null) {
  5. return leftMostNode(node.right);
  6. }
  7. TreeNode<T> successor = null;
  8. TreeNode<T> cur = root;
  9. while(cur != null) {
  10. if(node.element.compareTo(root.element) < 0) {
  11. successor = cur;
  12. cur = cur.left;
  13. }else {
  14. cur = cur.right;
  15. }
  16. }
  17. return successor;
  18. }
  1. private TreeNode<T> leftMostNode(TreeNode<T> node) {
  2. if(node == null)
  3. return null;
  4. while(node.left != null) {
  5. node = node.left;
  6. }
  7. return node;
  8. }

preOrderSuccessor 大体思路:
主要问题就是要求后继的结点是一个叶子结点的话,需要提前知道它的祖先结点

  1. public TreeNode<T> preOrderSuccessor(TreeNode<T> node) {
  2. //null node
  3. if(node == null)
  4. return null;
  5. TreeNode<T> cur = root;
  6. TreeNode<T> ancesor = null;
  7. while(cur != null && node.element.compareTo(cur.element) != 0) {
  8. if(node.element.compareTo(cur.element) < 0) {
  9. if(cur.right != null) {
  10. ancesor = cur;
  11. }
  12. cur = cur.left;
  13. }else {
  14. cur = cur.right;
  15. }
  16. }
  17. //can't find this node
  18. if(cur == null)
  19. return null;
  20. if(cur.left != null)
  21. return cur.left;
  22. if(cur.right != null)
  23. return cur.right;
  24. if(ancesor != null)
  25. return ancesor.right;
  26. return null;
  27. }

postOrderSuccessor 大体思路:后序遍历找当前结点p的后继时,p的下面的结点都在p的前面顺序出现,因此只需要关注p结点的parent结点即可。

  1. public TreeNode<T> postOrderSuccessor(TreeNode<T> node) {
  2. if(node == null)
  3. return null;
  4. if(node == root)
  5. return null;
  6. TreeNode<T> cur = root;
  7. TreeNode<T> parent = null;
  8. while(cur != null && node.element.compareTo(cur.element) != 0) {
  9. parent = cur;
  10. if(node.element.compareTo(cur.element) < 0) {
  11. cur = cur.left;
  12. }else {
  13. cur = cur.right;
  14. }
  15. }
  16. //find the node
  17. if(parent.right == cur) {
  18. return parent;
  19. }else {
  20. return leftMostNode(parent.right);
  21. }
  22. }

算法六:LCA,Lowest Common Ancestor

就是在一颗树中寻找两个结点p, q的公共祖先,例如下图:
lca.gif-5.9kB
结点3, 10的公共祖先就是8。结点1, 13的公共祖先也是8

算法思路: 如果结点p, q都在某个结点左子树或者右子树,即在同一边上,那么它们的LCA也一定在左子树或者右子树上。这样就可以分解成相同的小规模去解决问题,运用递归。如果p, q在某个结点的两边,那么这个结点即为LCA

  1. public TreeNode<T> lowestCommonAncetor(TreeNode<T> root, TreeNode<T> p, TreeNode<T> q ) {
  2. if(lcaHelper(root.left, p) && lcaHelper(root.left, q)) {
  3. return lowestCommonAncetor(root.left, p, q);
  4. }
  5. if(lcaHelper(root.right, p) && lcaHelper(root.right, q)) {
  6. return lowestCommonAncetor(root.right, p ,q);
  7. }
  8. return root;
  9. }
  10. //判断结点p是否是某个在某个子树中
  11. private boolean lcaHelper(TreeNode<T> root, TreeNode<T> p) {
  12. if(root == null) {
  13. return false;
  14. }
  15. if(root == p)
  16. return true;
  17. return lcaHelper(root.left, p) || lcaHelper(root.right, p);
  18. }

算法七-:print Range

给定一个区间值,打印BST中所有在这个区间的结点的值
思路:bst运用中序遍历

  1. //the range [start, end]
  2. public void printRange(TreeNode<T> root, T start, T end) {
  3. //assert start <= end
  4. if(root == null)
  5. return ;
  6. //inOrder
  7. if(start.compareTo(root.element) < 0) {
  8. printRange(root.left, start, end);
  9. }
  10. if(start.compareTo(root.element) <= 0 && end.compareTo(root.element) >= 0) {
  11. System.out.print(root.element + " ");
  12. }
  13. if(end.compareTo(root.element) > 0) {
  14. printRange(root.right, start, end);
  15. }
  16. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注