树是一种非线性结构，栈和队列都是线性结构(线性一般是指每一个元素都通常只有一个前驱和一个后继)

一、树的定义

一棵树是由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/-

结论：已知前序序列和中序序列可以确定二叉树

         已知中序序列和后序序列也可以确定出二叉树         

已知前序序列和后序序列不能确定二叉树

【例题】某二叉树的中序遍历为abcdefg，后序遍历为bdcafge，则先序遍历是_______________

【解析】记住一点：中序遍历确定左右子树，后(前)序遍历确定根结点。

（1）已知后序遍历为bdcafge(左右根)，那么e一定是根结点；已知e是根结点，看中序遍历，那么abcd是左子树，fg是右子树

（2）先看左子树abcd，这几个符号在后序遍历中是bdca，所以a是根结点。那么再看中序遍历abcd，说明左子树为空，右子树是bcd。

（3） 继续看bcd，在后序遍历中出现的顺序是bdc,说明c是根结点，然后再看中序遍历，b是左子树，d是右子树。

 (4) 看右子树fg,在后序遍历的顺序是fg，说明g是根结点。再看中序遍历fg。说明f是左子树，右子树为空。

(adsbygoogle = window.adsbygoogle || []).push({});