一. 树的简介

1. 什么是树(tree)

树是一种非线性的数据结构，是由n（n >=0）个结点组成的有限集合，运行时间平均为O(logN)。请看下图

简单树实例

2. 树的相关概念

①根节点(root)：每个树的顶部节点
②树存在子节点与父节点的概念，除去根节点外每个节点都只有一个父亲(可以用来识别是不是树)
③树叶(leaf)：没有儿子的节点，即最底层节点
④兄弟(sibling)：具有同一个父亲的两个节点称为兄弟节点
⑤深度(depth)：从根节点到n节点的唯一路径的长(即第n节点到根节点的边的条数)
⑥高(height)：从n节点到自己树叶的最长路径的长

二. 实现

1. 数据结构

• 左孩子右兄弟表示法

package com.shan.tree;

import com.shan.list.Node;

public class TreeNode {
    private int element;

    private Node firstChild; // 第一个孩子节点

    private Node nextSib; // 下一个兄弟节点

    public TreeNode(int element) {
        this.element = element;
        this.firstChild = null;
        this.nextSib = null;
    }

    public TreeNode(int element, Node firstChild, Node nextSib) {
        this.element = element;
        this.firstChild = firstChild;
        this.nextSib = nextSib;
    }

    public int getElement() {
        return element;
    }

    public void setElement(int element) {
        this.element = element;
    }

    public Node getFirstChild() {
        return firstChild;
    }

    public void setFirstChild(Node firstChild) {
        this.firstChild = firstChild;
    }

    public Node getNextSib() {
        return nextSib;
    }

    public void setNextSib(Node nextSib) {
        this.nextSib = nextSib;
    }
}

2. 二叉树

• 学习树最简单的就是二叉树：每个节点的子节点不能超过两个
• 二叉树的平均深度比节点数N少得多，最坏情况N-1

数据结构

package com.shan.tree;

import com.shan.list.Node;

public class BinaryTreeNode<T> {
    private T element;
    private Node left;
    private Node right;

    public BinaryTreeNode(T element) {
        this.element = element;
    }

    public T getElement() {
        return element;
    }

    public void setElement(T element) {
        this.element = element;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

表达式树

• 二叉树的重要应用就是表达式树

package com.shan.tree;

import java.util.Stack;

public class BinaryTree {
    private BinaryTreeNode root;

    public BinaryTree(BinaryTreeNode root) {
        this.root = root;
    }

    /**
     * 后缀表达式转成表达式树
     * @param exp 后缀表达式
     * @return 表达式树
     */
    public BinaryTree postorderToExpressionTree(String exp)  {
        Stack<BinaryTreeNode<Character>> optionStack = new Stack<>();
        for(int i=0; i<exp.length(); i++) {
            char nextChar = exp.charAt(i);
            if(nextChar == '+' || nextChar == '-' || nextChar == '*'|| nextChar == '/') {
                BinaryTreeNode midNode = new BinaryTreeNode(nextChar);
                BinaryTreeNode rightNode = optionStack.pop();
                BinaryTreeNode leftNode = optionStack.pop();
                midNode.setLeft(leftNode);
                midNode.setRight(rightNode);
                optionStack.push(midNode);
            }else {
                optionStack.push(new BinaryTreeNode<>(nextChar));
            }
        }
        BinaryTreeNode root = optionStack.pop();
        BinaryTree tree = new BinaryTree(root);
        return tree;
    }
}

二叉查找树