树

1.具有n个节点的树，有n-1条边

2.一种树的实现

每个节点有一个指向自己第一个孩子的指针，一个指向自己下一个兄弟的指针。

class TreeNode {
    Object value;
    TreeNode firstChild;
    TreeNode nextSibling;
}

3.树的遍历方式

主要有三种：先序、后序。
先序：先处理节点本身，再依次先序遍历子节点
后序：先后序遍历子节点，再处理节点本身

二叉树还有中序遍历方式：
中序：先中序遍历子节点，再处理节点本身

4.二叉树

定义：

二叉树是每个节点最多只有两个子节点的树

特点：

二叉树的特点是其深度一般比其节点数小很多。许多二叉树相关的算法都是因为这个性质才有很高的效率。（研究表明二叉树的平均深度为O根号N；二叉查找树的的平均深度为OlogN）

特点2：

n个节点的二叉树都有n+1个指针指向null。每个节点2个指针，共2n个。而指向真实节点的指针只有n-1个，剩下n+1个就指向null啦。

实现：

class BinaryNode ｛
   Object value;
    BinaryNode leftChild;
    BinaryNode rightChild;
｝

例题：构造表达式树

给出一个后缀表达式，构造出一棵表达式树。
表达式树：树叶是操作数，根是操作符。
构造过程：如果输入的数字则压入栈，如果是操作符则从堆栈里弹出两项，作为操作符的左右孩子，再把操作符表示的节点压入栈里。

二次查找树

性质：对于树中每个节点X，它的左子树中所有项的值小于X中的项，而它的右子数中所有项的值都大于X中的项。
中序遍历一颗二叉查找树，就得到了元素的顺序输出。

一种实现

public class BinarySearchTree<T extends Comparable<? super T>> {
    private  class BinaryNode <T>{
    
  }
}