程序员社区

二叉树的基本算法

二叉树的基本算法

树、二叉树 的基本概念,参考数据结构算法之美-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的位置都会打印一次,每个数字都会出现三次,如下图所示

二叉树的基本算法插图1
image-20210526144948696

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

二叉树的基本算法插图2
image-20210526145318241

1 2 4 5 3 6 7

中序遍历:数字第二次出现,打印出来

二叉树的基本算法插图3
image-20210526145447372

4 2 5 1 6 3 7

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

二叉树的基本算法插图4
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();
   }


二叉树的基本算法插图5
image-20210526150832096
二叉树的基本算法插图6
image-20210526150947599
二叉树的基本算法插图7
image-20210526151036542
二叉树的基本算法插图8
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();
   }
二叉树的基本算法插图9
image-20210526151833123
二叉树的基本算法插图10
image-20210526151945051
二叉树的基本算法插图11
image-20210526152036176
二叉树的基本算法插图12
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();
   }


二叉树的基本算法插图13
image-20210526154208401
二叉树的基本算法插图14
image-20210526154412170
二叉树的基本算法插图15
image-20210526154550363
二叉树的基本算法插图16
image-20210526154747553
二叉树的基本算法插图17
image-20210526154824294

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

  • 其实就是宽度优先遍历,用队列
二叉树的基本算法插图18
image-20210526161019277
二叉树的基本算法插图19
image-20210526161301682
二叉树的基本算法插图20
image-20210526161341246
二叉树的基本算法插图21
image-20210526161414358
二叉树的基本算法插图22
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变量的方式,来发现某一层的结束
二叉树的基本算法插图23
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的方法

二叉树的基本算法插图24
image-20210526163617201
二叉树的基本算法插图25
image-20210526163837652
二叉树的基本算法插图26
image-20210526163940564
二叉树的基本算法插图27
image-20210526164054104
二叉树的基本算法插图28
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)

二叉树的基本算法插图29
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)

二叉树的基本算法插图30
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;
    }
赞(0) 打赏
未经允许不得转载:IDEA激活码 » 二叉树的基本算法

一个分享Java & Python知识的社区