树的基本概念
有序树、无序树、森林
二叉树
- 二叉树的性质
真二叉树
满二叉树
完全二叉树
- 完全二叉树的性质
  - index以1为起点
  - index以0为起点
方法及实现
- 二叉树的遍历
- 前驱节点与后继节点
  - 前驱节点
  - 后继节点
面试题
总代码

树的基本概念

有序树、无序树、森林

二叉树

二叉树的性质

真二叉树

满二叉树

完全二叉树

完全二叉树的性质

index以1为起点

index以0为起点

方法及实现

二叉树的遍历

前序遍历

访问顺序：根节点、前序遍历左子树、前序遍历右子树（左右可互换）

//前序遍历
public void preorder(Visitor<E> visitor) {
	if (visitor == null) return;
	preorder(root, visitor);
}

private void preorder(Node<E> node, Visitor<E> visitor) {
	if (node == null || visitor.stop) return;
	
	visitor.stop = visitor.visit(node.element);
	preorder(node.left, visitor);
	preorder(node.right, visitor);
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack=new LinkedList<>();
        LinkedList<Integer> ans=new LinkedList<>();
        if(root==null) return ans;
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode node=stack.pollLast();
            ans.add(node.val);
            if(node.right!=null){
                stack.add(node.right);
            }
            if(node.left!=null){
                stack.add(node.left);
            }
        }
        return ans;
    }
}

中序遍历

访问顺序：中序遍历左子树、根节点、中序遍历右子树（左右可互换）

二叉搜索树的中序遍历结果是升序或者降序的

//中序遍历
public void inorder(Visitor<E> visitor) {
    if (visitor == null) return;
    inorder(root, visitor);
}

private void inorder(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor.stop) return;

    inorder(node.left, visitor);
    if (visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
    inorder(node.right, visitor);
}

public List<Integer> inorderTraversal(TreeNode root) {
    LinkedList<Integer> ans = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        ans.add(cur.val);
        cur = cur.right;
    }
    return ans;
}

后序遍历

访问顺序：后序遍历左子树、后序遍历右子树、根节点（左右可互换）

//后序遍历
public void postorder(Visitor<E> visitor) {
    if (visitor == null) return;
    postorder(root, visitor);
}

private void postorder(Node<E> node, Visitor<E> visitor) {
    if (node == null || visitor.stop) return;

    postorder(node.left, visitor);
    postorder(node.right, visitor);
    if (visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
}

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack=new LinkedList<>();
    LinkedList<Integer> ans=new LinkedList<>();
    if(root==null) return ans;
    stack.add(root);
    while (!stack.isEmpty()){
        TreeNode node=stack.pollLast();
        ans.addFirst(node.val);
        if(node.left!=null){
            stack.add(node.left);
        }
        if(node.right!=null){
            stack.add(node.right);
        }
    }
    return ans;
}

层序遍历

从上到下、从左到右依次访问每一个节点

实现思路：使用队列

将根节点入队
循环执行以下操作，直到队列为空
- 将队头节点 A 出队，进行访问
- 将 A 的左子节点入队
- 将 A 的右子节点入队

//层序遍历
public void levelOrder(Visitor<E> visitor) {
    if (root == null || visitor == null) return;

    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        if (visitor.visit(node.element)) return;

        if (node.left != null) {
            queue.offer(node.left);
        }

        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

前驱节点与后继节点

前驱节点

前驱节点：中序遍历时的前一个节点

如果是二叉搜索树，前驱节点就是前一个比它小的节点

node.left!=null
- predecessor = node.left.right.right.right... (终止条件为right==null)
node.left == null && node.parent != null
- predecessor = node.parent.parent.parent... (终止条件为：node 在 parent 的右子树中)
node.left == null && node.parent == null
没有前驱节点

//前驱节点: 中序遍历时的前一个节点
protected 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;
    }

    // 从父节点、祖父节点中寻找前驱节点
    while (node.parent != null && node == node.parent.left) {
        node = node.parent;
    }

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

后继节点

与前驱节点相反

//后继节点：中序遍历时的后一个节点
protected 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;
}

面试题

题目一：完全二叉树根据节点求叶子节点个数

题目二：翻转二叉树

解法一：递归

public TreeNode invertTree(TreeNode root) {
   if (root == null) return root;

   TreeNode tmp = root.left;
   root.left = root.right;
   root.right = tmp;

   invertTree(root.left);
   invertTree(root.right);

   return root;
}

解法二：非递归

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        if (node.left != null)
            queue.offer(node.left);
        if (node.right != null)
            queue.offer(node.right);
    }
    return root;
}

题目三：计算二叉树的高度

解法一：递归

public int height() {
    return height(root);
}

private int height(Node<E> node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

解法二：非递归

public int height() {
    if (root == null) return 0;

    // 树的高度
    int height = 0;
    // 存储着每一层的元素数量
    int levelSize = 1;
    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        levelSize--;

        if (node.left != null) {
            queue.offer(node.left);
        }

        if (node.right != null) {
            queue.offer(node.right);
        }

        if (levelSize == 0) { // 意味着即将要访问下一层
            levelSize = queue.size();
            height++;
        }
    }

    return height;
}

题目四：判断一棵树是否为完全二叉树

public boolean isComplete() {
    if (root == null) return false;

    Queue<Node<E>> queue = new LinkedList<>();
    queue.offer(root);

    boolean leaf = false;
    while (!queue.isEmpty()) {
        Node<E> node = queue.poll();
        if (leaf && !node.isLeaf()) return false;

        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.left == null && node.right != null) { 
            return false;
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
        if (node.left == null && node.right == null) { 
            leaf = true;
        }
    }
    return true;
}

总代码

@SuppressWarnings("unchecked")
public class BinaryTree<E> {
    protected int size;
    protected Node<E> root;

    public static abstract class Visitor<E> {
        boolean stop;

        /**
         * @return 如果返回true，就代表停止遍历
         */
        abstract boolean visit(E element);
    }

    protected 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 int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    //前序遍历
    public void preorder(Visitor<E> visitor) {
        if (visitor == null) return;
        preorder(root, visitor);
    }

    private void preorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;

        visitor.stop = visitor.visit(node.element);
        preorder(node.left, visitor);
        preorder(node.right, visitor);
    }

    //中序遍历
    public void inorder(Visitor<E> visitor) {
        if (visitor == null) return;
        inorder(root, visitor);
    }

    private void inorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;

        inorder(node.left, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
        inorder(node.right, visitor);
    }

    //后序遍历
    public void postorder(Visitor<E> visitor) {
        if (visitor == null) return;
        postorder(root, visitor);
    }

    private void postorder(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) return;

        postorder(node.left, visitor);
        postorder(node.right, visitor);
        if (visitor.stop) return;
        visitor.stop = visitor.visit(node.element);
    }

    //层序遍历
    public void levelOrder(Visitor<E> visitor) {
        if (root == null || visitor == null) return;

        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) return;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    public boolean isComplete() {
        if (root == null) return false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        boolean leaf = false;
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (leaf && !node.isLeaf()) return false;

            if (node.left != null) {
                queue.offer(node.left);
            } else if (node.right != null) {
                return false;
            }

            if (node.right != null) {
                queue.offer(node.right);
            } else { // 后面遍历的节点都必须是叶子节点
                leaf = true;
            }
        }

        return true;
    }

    //树的高度，非递归
    public int height() {
        if (root == null) return 0;

        // 树的高度
        int height = 0;
        // 存储着每一层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }

            if (levelSize == 0) { // 意味着即将要访问下一层
                levelSize = queue.size();
                height++;
            }
        }

        return height;
    }

    //树的高度，递归
    public int height2() {
        return height(root);
    }

    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(node.right));
    }

    //前驱节点: 中序遍历时的前一个节点
    protected 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;
        }

        // 从父节点、祖父节点中寻找前驱节点
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }

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

    //后继节点：中序遍历时的后一个节点
    protected 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;
    }
}

nice

二叉树-数据结构

树的基本概念

有序树、无序树、森林

二叉树

二叉树的性质

真二叉树

满二叉树

完全二叉树

完全二叉树的性质

index以1为起点

index以0为起点

方法及实现

二叉树的遍历

前序遍历

中序遍历

后序遍历

层序遍历

前驱节点与后继节点

前驱节点

后继节点

面试题

题目一：完全二叉树根据节点求叶子节点个数

题目二：翻转二叉树

题目三：计算二叉树的高度

题目四：判断一棵树是否为完全二叉树

总代码

https代理

Python3.8安装Scrapy & 使用

skyyemperor

Comments | 0 条评论

nice