树是一种非线性结构，栈和队列都是线性结构(线性一般是指每一个元素都通常只有一个前驱和一个后继)
一、树的定义
一棵树是由n(n>0)个元素组成的有限集合，其中：
(1)每个元素称为结点(node)
(2)有一个特定的结点，称为根结点或树根(root)
(3)除根结点外，其余结点能分成m(m>=0)个互不相交的有限集合T0,T1,T2…… Tm-1。其中的每个子集又都是一棵树，这些集合称为这颗树的子树。
三、树的基本概念
(1)树都是递归定义的。
(2)一棵树中至少有1个结点。这个结点就是根结点。
(3)一个结点的子树个数，称为这个结的度(degree)
例如，结点1的度为3，结点3的度为0；度为0的结点称为叶结点。
(4)在用图形表示的树型结构中，对两个用线段连接的相关联的结点，称上端点为下端点的父结点，称下端结点为上端结点为子结点。同一个父结点的多个子结点称为兄弟结点。
(5)定义一棵树的根结点的层次为1，其他节点的层次等于它的父结点层次加1。
(6)对于树中任意两个不同的结点，如果从一个结点出发，自上而下沿着树中连着结点的线段能到达另一结点，称它们之间存在着一条路径。
(7)森林是m(m>=0)棵互不相交的树的集合。
三、树的种类
无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;
有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；
二叉树：每个节点最多含有两个子树的树称为二叉树；
满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树
完全二叉树：二叉树除去最后一层为满二叉树，且最后一层的结点依次从左到右分布，这样的二叉树称为完全二叉树
哈夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
四、二叉树的基本形态
五、二叉树的性质
性质1：在非空二叉树的第i层做多有2i-1节点。
性质2：深度为k的二叉树最多有2k -1个节点。
性质3：对于任意一棵二叉树，如果度为0的节点个数为n0。度为2的节点数为n2。则n0=n2+1
性质4:具有n个节点的完全二叉树的深度k=floor(log2n)+1
性质5:对于含n个节点的完全二叉树中编号为i(1<=i<=n)的节点。
- 如果i=1,则i节点是这可完全二叉树的根，没有双亲。否则其双亲编号为i/2
- 如果2i>n,则i节点没有左孩子，否则其左孩子的编号为2i
- 如果2i+1>n,则i节点没有右孩子，否则其右孩子的编号为2i+1
补充性质1：叶子结点数=度为2的结点+1
叶子结点数=总结点数/2（慎用）
补充性质2：结点总数=n1+n2+n0 ( n1 是度为1的点，n2是度为2的点，n0是度为0点)
补充性质3：对于一棵完全二叉树来说，n1（度为1的点）只有1或0
补充性质4：结点总数=度数 * 该度数对应的结点数 + 1
六、二叉树的遍历
遍历表达法是有3种，先序遍历、中序遍历、后序遍历。
例如：
先序(根)遍历为ABDECF(根-左-右)
中序(根)遍历为DBEAFC(左-根-右)
后序(根)遍历为DEBFCA(左-右-根)
例2：
先序遍历：对于当前节点，先输出该节点，然后输出他的左孩子，最后输出他的右孩子。以上图为例，递归的过程如下：
（1）：输出 1，接着左孩子；（2）：输出 2，接着左孩子；（3）：输出 4，左孩子为空，再接着右孩子；（4）：输出 6，左孩子为空，再接着右孩子；（5）：输出 7，左右孩子都为空，此时 2 的左子树全部输出，2 的右子树为空，此时 1 的左子树全部输出，接着 1 的右子树；
（6）：输出 3，接着左孩子；（7）：输出 5，左右孩子为空，此时 3 的左子树全部输出，3 的右子树为空，至此 1 的右子树全部输出，结束。 结果：1246735
中序遍历：对于当前结点，先输出它的左孩子，然后输出该结点，最后输出它的右孩子。以上图为例：
（1）：1–>2–>4，4 的左孩子为空，输出 4，接着右孩子；
（2）：6 的左孩子为空，输出 6，接着右孩子；
（3）：7 的左孩子为空，输出 7，右孩子也为空，此时 2 的左子树全部输出，输出 2，2 的右孩子为空，此时 1 的左子树全部输出，输出 1，接着 1 的右孩子；
（4）：3–>5，5 左孩子为空，输出 5，右孩子也为空，此时 3 的左子树全部输出，而 3 的右孩子为空，至此 1 的右子树全部输出，结束。
结果：4672153
后序遍历：对于当前结点，先输出它的左孩子，然后输出它的右孩子，最后输出该结点。依旧以上图为例：
（1）：1->2->4->6->7，7 无左孩子，也无右孩子，输出 7，此时 6 无左孩子，而 6 的右子树也全部输出，输出 6，此时 4 无左子树，而 4 的右子树全部输出，输出 4，此时 2 的左子树全部输出，且 2 无右子树，输出 2，此时 1 的左子树全部输出，接着转向右子树；
（2）：3->5，5 无左孩子，也无右孩子，输出 5，此时 3 的左子树全部输出，且 3 无右孩子，输出 3，此时 1 的右子树全部输出，输出 1，结束。
结果：7642531
七、遍历与表达式
一棵二叉树的先序遍历的结果就是前缀表达式(波兰式)
一棵二叉树中序遍历的结果就是中缀表达式
一个二叉树后序遍历的结果就是后缀表达式(逆波兰式)
前缀表示: -+a*b-cd/ef
中缀表示: a+b*c-d-e/f
后缀表示: abcd-*+ef/-
结论：已知前序序列和中序序列可以确定二叉树
已知中序序列和后序序列也可以确定出二叉树
已知前序序列和后序序列不能确定二叉树
返回目录：NOIP/CSP信息学奥赛初赛