二叉树的基本算法

树、二叉树 的基本概念，参考数据结构算法之美-23讲二叉树基础（上）：树、二叉树

二叉树的遍历

如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。

• 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
• 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
• 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身

private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
        
        public boolean isLeaf() {
            return left == null && right == null;
        }
        
        public boolean hasTwoChildren() {
            return left != null && right != null;
        }
    }
/**
 * 前序遍历
 */
public void preorderTraversal() {
   preorderTraversal(root);
}

private void preorderTraversal(Node<E> node) {
   if (node == null) return;

   System.out.println(node.element);
   preorderTraversal(node.left);
   preorderTraversal(node.right);
}

/**
 * 中序遍历
 */
public void inorderTraversal() {
   inorderTraversal(root);
}

private void inorderTraversal(Node<E> node) {
   if (node == null) return;

   inorderTraversal(node.left);
   System.out.println(node.element);
   inorderTraversal(node.right);
}

/**
 * 后序遍历
 */
public void postorderTraversal() {
   postorderTraversal(root);
}

private void postorderTraversal(Node<E> node) {
   if (node == null) return;

   postorderTraversal(node.left);
   postorderTraversal(node.right);
   System.out.println(node.element);
}

二叉树的递归序

image-20210526144429432

public static void f(Node head) {
   if (head == null) {
      return;
   }
   // 1 System.out.println(node.element);
   f(head.left);
   // 2 System.out.println(node.element);
   f(head.right);
   // 3 System.out.println(node.element);
}

递归需遍历 在上述代码1，2，3的位置都会打印一次，每个数字都会出现三次，如下图所示

image-20210526144948696

先序遍历：第一次出现的打印出来

image-20210526145318241

1 2 4 5 3 6 7

中序遍历：数字第二次出现，打印出来

image-20210526145447372

4 2 5 1 6 3 7

后序遍历 ：数组第三次出现打印出来

image-20210526145613264

4 5 2 6 7 3 1

非递归方式实现二叉树的先序、中序、后序遍历

• 任何递归函数都可以改成非递归
• 自己设计压栈的来实现

public class UnRecursiveTraversalBT {

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

      public Node(int v) {
         value = v;
      }
   }

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

   public static void pos1(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();
   }

   public static void pos2(Node h) {
      System.out.print("pos-order: ");
      if (h != null) {
         Stack<Node> stack = new Stack<Node>();
         stack.push(h);
         Node c = null;
         while (!stack.isEmpty()) {
            c = stack.peek();
            if (c.left != null && h != c.left && h != c.right) {
               stack.push(c.left);
            } else if (c.right != null && h != c.right) {
               stack.push(c.right);
            } else {
               System.out.print(stack.pop().value + " ");
               h = c;
            }
         }
      }
      System.out.println();
   }

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

      pre(head);
      System.out.println("========");
      in(head);
      System.out.println("========");
      pos1(head);
      System.out.println("========");
      pos2(head);
      System.out.println("========");
   }

}

RUN> 🚗🚗🚗🚗🚗🚗

pre-order: 1 2 4 5 3 6 7 
========
in-order: 4 2 5 1 6 3 7 
========
pos-order: 4 5 2 6 7 3 1 
========
pos-order: 4 5 2 6 7 3 1 
========

• 先序遍历：

   public static void pre(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) {//先push右
               stack.push(head.right);
            }
            if (head.left != null) {//再push左
               stack.push(head.left);
            }
         }
      }
      System.out.println();
   }

image-20210526150832096 image-20210526150947599 image-20210526151036542 image-20210526151153103

• 后序遍历

public static void pos1(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) {//先push左
               s1.push(head.left);
            }
            if (head.right != null) {//再push右
               s1.push(head.right);
            }
         }
         // 左 右 头
         while (!s2.isEmpty()) {
            System.out.print(s2.pop().value + " ");
         }
      }
      System.out.println();
   }

image-20210526151833123 image-20210526151945051 image-20210526152036176 image-20210526152154596

4 5 2 6 7 3 1

中序遍历

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

image-20210526154208401 image-20210526154412170 image-20210526154550363 image-20210526154747553 image-20210526154824294

二叉树的按层遍历(宽度优先遍历)

• 其实就是宽度优先遍历，用队列

image-20210526161019277 image-20210526161301682 image-20210526161341246 image-20210526161414358 image-20210526161430205

public class LevelTraversalBT {

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

      public Node(int v) {
         value = v;
      }
   }

   public static void level(Node head) {
      if (head == null) {
         return;
      }
      Queue<Node> queue = new LinkedList<>();
      queue.add(head);
      while (!queue.isEmpty()) {
         Node cur = queue.poll();
         System.out.println(cur.value);
         if (cur.left != null) {
            queue.offer(cur.left);
         }
         if (cur.right != null) {
            queue.offer(cur.right);
         }
      }
   }
}

二叉树求树🌲的宽度

• 可以通过设置flag变量的方式，来发现某一层的结束

image-20210526162330686

public static int maxWidthUseMap(Node head) {
   if (head == null) {
      return 0;
   }
   Queue<Node> queue = new LinkedList<>();
   queue.add(head);
   // key 在 哪一层，value
   HashMap<Node, Integer> levelMap = new HashMap<>();
   levelMap.put(head, 1);
   int curLevel = 1; // 当前你正在统计哪一层的宽度
   int curLevelNodes = 0; // 当前层curLevel层，宽度目前是多少
   int max = 0;
   while (!queue.isEmpty()) {
      Node cur = queue.poll();
      int curNodeLevel = levelMap.get(cur);
      if (cur.left != null) {
         levelMap.put(cur.left, curNodeLevel + 1);//如队列的时候，记录好结点的层次
         queue.add(cur.left);
      }
      if (cur.right != null) {
         levelMap.put(cur.right, curNodeLevel + 1);//如队列的时候，记录好结点的层次
         queue.add(cur.right);
      }
      if (curNodeLevel == curLevel) {
         curLevelNodes++;
      } else {
         max = Math.max(max, curLevelNodes);
         curLevel++;
         curLevelNodes = 1;
      }
   }
   max = Math.max(max, curLevelNodes);//最后一次加入一次比较
   return max;
}

不使用HashMap的方法

image-20210526163617201 image-20210526163837652 image-20210526163940564 image-20210526164054104 image-20210526164139989

public static int maxWidthNoMap(Node head) {
   if (head == null) {
      return 0;
   }
   Queue<Node> queue = new LinkedList<>();
   queue.add(head);
   Node curEnd = head; // 当前层，最右节点是谁
   Node nextEnd = null; // 下一层，最右节点是谁
   int max = 0;
   int curLevelNodes = 0; // 当前层的节点数
   while (!queue.isEmpty()) {
      Node cur = queue.poll();
      if (cur.left != null) {
         queue.add(cur.left);
         nextEnd = cur.left;
      }
      if (cur.right != null) {
         queue.add(cur.right);
         nextEnd = cur.right;
      }
      curLevelNodes++;
      if (cur == curEnd) {
         max = Math.max(max, curLevelNodes);
         curLevelNodes = 0;
         curEnd = nextEnd;
      }
   }
   return max;
}

---

前驱节点(predecessor)

image-20210526182702556

    private Node<E> predecessor(Node<E> node) {
        if (node == null) return null;
        
        // 前驱节点在左子树当中（left.right.right.right....）
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        
        // 从父节点、祖父节点中寻找前驱节点
        //终止条件：node在parent的右字数中
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

        // node.parent == null
        // node == node.parent.right
        return node.parent;
    }

后继节点(successor)

image-20210526182918978

    private Node<E> successor(Node<E> node) {
        if (node == null) return null;
        
        // 前驱节点在左子树当中（right.left.left.left....）
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        
        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }