数据结构专题 - 二叉树(初级)

数据结构专题 - 二叉树(初级)

Scroll Down

二叉树

特点:

  • 根节点
  • 子节点
  • 叶子节点

image-20200712161252319

image-20200712161452841

递归特性

image-20200712161627358

二分搜索树

性质:

image-20200712161901819

实战

package com.sukai.BST;

public class BST<E extends Comparable<E>> {

    private class Node {
        public E e;
        public Node left;
        public Node right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public Node add(E e) {
        root = add(root, e);
        size++;
        return root;
    }

    // 在以node为根的二叉树中添加元素
    private Node add(Node node, E e) {
        if (node == null) {
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        }
        if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }
        return node;
    }

    // 前序遍历
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null)
            return;
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }

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

    private void inOrder(Node node) {
        if (node == null)
            return;
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

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

    private void postOrder(Node node) {
        if (node == null)
            return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }
}

前序遍历的非递归实现

// 前序遍历的非递归写法
    public void preOrderNR() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.println(cur.e);
            if (cur.right != null)
                stack.push(cur.right);
            if (cur.left != null)
                stack.push(cur.left);
        }
    }

层序遍历

image-20200712191126821

// 广度优先遍历
    public void levelOrder() {

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node cur = queue.remove();
            System.out.println(cur.e);
            if (cur.left != null)
                queue.add(cur.left);
            if (cur.right != null)
                queue.add(cur.right);
        }
    }

总结

  • 遍历的应用:
  1. 中序遍历可以排序
  2. 后序遍历使用场景是为二分搜索树释放内存
  • 二叉树的遍历重点掌握
  1. 深度优先遍历
  2. 广度优先遍历(非递归算法)
  3. 前序遍历的非递归算法