数据结构学习笔记(六)——树上篇

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

定义

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

未完待续...

每周更新两篇原创文章

谢谢各位支持

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180809G1VM7M00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券