数据结构之——二叉树

最近开始重新温习一下大学数据结构的一些算法，也重新梳理一下自己的思路和想法。

先从二叉树开始。每周一期，希望能分享给大家，如有问题及时给予指正，谢谢大家。

 

二叉树的基本概念：

 

       二叉树是有限元素的集合，该集合或者为空，或者由一个称为根的元素及两个不想交，被分别称为左子树和右子树的二叉树组成。 二叉树是有序的，若将其左右子树颠倒，就成为另一颗不同的二叉树。

 

二叉树的相关概念

 

• 结点的度：结点所拥有的子树的个数称为该结点的度。
• 叶结点：度为0的结点称为叶结点，或者称为终端结点。
• 分枝结点：度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。
• 左孩子、右孩子、双亲：树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。

• 路径、路径长度。如果一棵树的一串结点n₁,n₂,…,n_k有如下关系：结点n_i是n_i+1的父结点（1≤i<k）,就把n₁,n₂,…,n_k称为一条由n₁至n_k的路径。这条路径的长度是k-1。

• 祖先、子孙：在树中，如果有一条路径从结点M到结点N，那么M就称为N的祖先，而N称为M的子孙。
• 结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。
• 树的深度：树中所有结点的最大层数称为树的深度。
• 树的度：树中各结点度的最大值称为该树的度。
• 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。如图1.0所示，（a）图就是一棵满二叉树，（b）图则不是满二叉树，因为，虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树。

                 
      (a) 一棵满二叉树                                               (b) 一棵非满二叉树

图1.0 满二叉树和非满二叉树示意图

 

• 完全二叉树：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。如图1.1所示（a）为一棵完全二叉树，（b）和图1.0（b）都不是完全二叉树。

                      

           (a) 一棵完全二叉树                                    (b) 一棵非完全二叉树

图1.1 完全二叉树和非完全二叉树示意图

 

二叉树的主要性质

 

• 一棵非空二叉树的第i层上最多有2^i-1个结点（i≥1）。
• 一棵深度为k的二叉树中，最多具有2^k－1个结点。
• 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0＝n2＋1。
• 具有n个结点的完全二叉树的深度k为[log₂n]+1。

• 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有:

        （1）如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝1，则序号为i的结点是根结点，无双亲结点。

        （2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩子。 

（3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1>n，则序号为i的结点无右孩子。 此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i－1）/2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。

 

二叉树的存储

 

• 顺序存储结构：所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。

• 链式存储结构：用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常有下面两种形式。 1、二叉链表存储。2、三叉链表存储。

二叉树的遍历方法

 

• A、先序遍历（DLR） 先序遍历的递归过程为：若二叉树为空，遍历结束。否则，

（1）访问根结点；

（2）先序遍历根结点的左子树；

（3）先序遍历根结点的右子树。

 

• B、中序遍历（LDR） 中序遍历的递归过程为：若二叉树为空，遍历结束。否则，

（1）中序遍历根结点的左子树；

（2）访问根结点；

（3）中序遍历根结点的右子树。

 

• C、后序遍历（LRD） 后序遍历的递归过程为：若二叉树为空，遍历结束。否则，

（1）后序遍历根结点的左子树；

（2）后序遍历根结点的右子树。

（3）访问根结点；

对于图图1.0(b)所示的二叉树，按先序遍历所得到的结点序列为：G D B E F C A

 

• D、层次遍历 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对于图6.3(b)所示的二叉树，按层次遍历所得到的结果序列为： A B C D E F G