数据结构学习笔记（六）——树上篇

今天来学习一种非线性结构——树。树形结构是一类非常重要的结构，其中二叉树，红黑树最为重要和常用。从宏观角度看，树是以分支关系定义的层次结构。与前面提到的数组、链表、栈不同，树结构在客观世界中广泛存在，如社会上的公司上下级关系，遗传图等。而在计算机领域中也到了广泛应用，例如数据库中，树结构是信息的重要组织形式之一；以及在操作系统中进程管理的进程树的概念。

定义

DEF

﹀

﹀

﹀

在详细讲解之前，先来看下树的定义：

树是n(n>=0)个结点的有限集。

树有且只有一个根结点(该结点是一个特殊的无父结点的结点)。

除根结点外，有若干个互不相交的的有限集，其中每个集合本身又是一棵树，这样的树称为子树(SubTree)。

其它名词解释：

结点拥有的子树的个数称为结点的度(Degree)；没有子结点的结点称为叶子结点或终端结点(度为0)，反之称为非终端结点或分支结点；树的度是树内各结点的度的最大值；结点的子树的根称为该结点的孩子(Child)，相应的，该结点称为孩子的双亲(Parent)；同一个双亲的孩子互称兄弟；结点的层次从根开始说起，根为第一层，根的孩子为第二层，以此类推。其双亲在同一层的结点互为堂兄弟；从根结点到最底层结点的层数称为深度(Depth)；最后，如果一个树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则为无序树。

牛刀小试

在上图中，A的度为2，B的度为2， C的度为1，DEF的度均为0；终端结点是D,E,F；该树的度为2；树的深度为3

二叉树

DEF

﹀

﹀

﹀

二叉树分为一般二叉树，满二叉树和完全二叉树。二叉树的特点是每个结点最多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树是一种有序树；满二叉树指在不增加层次的情况下，无法再添加结点的二叉树；如果只是删除了满二叉树最底层最右边的连续若干个结点，这样形成的二叉树称为完全二叉树。

二叉树的存储

DEF

﹀

﹀

﹀

无论是树也好，还是二叉树也好，说到底就是非线性结构如何用线性结构的内存来表示的问题。首先来看看二叉树的存储问题，二叉树的存储可以分为两类，一类顺序存储，一类链式存储。我们先来讨论一下链式存储的方法。

设计不同的结点结构可构成不同形式的链式存储结构。我们由二叉树的定义可知，二叉树的的结点有一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域、左指针域，和右指针域，如图。

遍历二叉树

DEF

﹀

﹀

﹀

三种遍历方式

先序遍历二叉树的步骤为：

访问根结点

先序遍历左子树

先序遍历右子树

中序遍历二叉树的步骤为：

中序遍历左子树

访问根结点

中序遍历右子树

后序遍历二叉树的步骤为：

后序遍历左子树

后序遍历右子树

访问根结点

牛刀小试

❈

先序遍历：a->b->d->g->c->e->f->h

中序遍历：d->g->b->a->e->c->h->f

后序遍历：g->d->b->e->h->f->c->a

❈

作业

各位看官，学习了上面的三种遍历方法，现在请你们分别用这三种方法写出下图中树的遍历顺序。想回答的把答案写在留言区哦。

已知两种遍历序列求二叉树

DEF

﹀

﹀

﹀

已知先，中求后序

先序遍历：ABDGHCEFI

中序遍历：GDHBAECIF

首先这个问题里最终要达到的目标是求出后序，那么求出后序应该先构建出原始的二叉树，所以这个问题可以转化为根据先序和中序构建出二叉树。

先要清楚在先序遍历中先访问的是根结点，所以在先序中最先出现的一定是根结点，据此可以推论出根结点为A。再把根结点A放到中序中观察发现A的左右两边各有结点，根据中序遍历的特点我们不难发现在A的左边的结点是A的左子树，反之亦然。现在我们知道A的左子树必然是GDHB那么GDHB中哪个又是A左子树的根结点呢？把GDHB放到先序中不难发现B最先出现，所以B为A左子树的根结点。还是和前面一样的思路在中序中观察B结点的位置发现GDH为B的左子树，通过先序和中序来回的推演，可以得出如下树的原型。

最后根据二叉树，直接得出后序遍历的顺序为：GHDBEIFCA

未完待续...

每周更新两篇原创文章

谢谢各位支持