程序员社区
当前位置：IDEA激活码 > 未分类 > 正文

二叉树的基本算法

2022-02-05 分类：未分类 阅读(407)

二叉树的基本算法

树、二叉树 的基本概念，参考数据结构算法之美-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激活码 » 二叉树的基本算法

相关推荐

IDEA永久激活破解教程,IDEA激活码

pycharm激活破解教程,pycharm激活码

Java视频资源

Java电子书

DataGrip激活教程 Docker Git教程 IntellIJ idea IntelliJ IDEA激活码 Java Java IO Java基础 Java基础面试题 Java集合面试题 Java面试题 JVM JVM面试题 Linux MySQL MySQL面试题 Nginx PyCharm PyCharm激活 redis Redis SpringBoot SpringBoot SpringBoot面试题 Web开发 剑指Offer系列 多线程 多线程并发面试题 字符串面试题 数据库 数据库 数据结构与算法 未分类 爬虫 电子书 软件下载

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