线性结构和非线性结构讲解.ppt

《线性结构和非线性结构讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二叉树二叉树遍历递归线性结构和非线性结构线性结构：结构中的数据元素之间存在一对一的关系。我们前面学的数据结构(向量、列表、堆栈、队列等)都是线性结构。非线性结构：树形：结构中数据元素之间存在一对多的关系。图形：结构中数据元素之间存在多对多的关系。数据的逻辑结构——线性结构A,B,C,·······，X,Y,Z学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号（1）有且仅有一个开始结点(表头结点)，它没有直接前驱，只有一个直接后继;（2）有且仅有一个终端结点(表尾结点)，它没有直接后继，只有一个直接前驱;（3）其它结点都有且仅有一个直接前驱和直接

2、后继；（4）元素之间为一对一的线性关系。数据的逻辑结构——树形结构全校学生档案管理的组织方式1423213数据的逻辑结构——图形结构结点间的连结是任意的树的概述树形结构是一类非常重要的非线性结构，它可以很好地描述客观世界中广泛存在的具有分支关系或层次特性的对象。因此在计算机领域里有着广泛应用。如：操作系统中的文件管理编译程序中的语法结构数据库系统信息组织形式数据的逻辑结构可描述为：Group=（D，R）有限个数据元素的集合这些数据元素间关系的集合ABCDEFGHJID={A,B,C,D,E,F,G,H,I,J}R={(A,B),(A,C),(A,D),(B,E),(B,F),(D,G)

3、,(D,H),(F,I),(F,J)}树的定义1树的逻辑结构可以这样描述：树是包含n(n>0)个结点的有穷集合K（k0、k1、...、kn-2、kn-1），且在K上定义了一个关系N，关系N满足以下条件：有且仅有一个结点k0∈K，它对于关系N来说没有前驱结点。k0称作树的根。除结点外k0，K中的每一个结点对于关系N来说都有且仅有一个直接前驱结点；有零个或多个直接后继结点。ABCDEFGHJI一颗大树分成几个大的分枝（称作子树），每个大分枝再分成几个小分枝，小分枝再分成更小的分枝，…，每个分枝也都是一颗树，由此我们可以给出树的递归定义。树的逻辑结构可以这样描述：树是包含n(n>0)个结点的有

4、穷集合T，使得：有一个特别标出的称作根的结点。除根以外的其他结点被分成m（m≥0）个不相交的集合T1，T2，…，Tm，而且这些集合的每一个又都是树。树T1，T2，…，Tm称作这个根的子树。ABCDEFGHJI树的定义2ABCDEFGHJI树的相关术语度：一个结点的子树的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。树中度为零的结点称为叶结点（或终端结点）。树中度不为零的结点称为分枝结点（或非终端结点）。除根结点外的分枝结点统称为内部结点。ABCDEFGHJI树的相关术语结点的子树的根称为该结点的孩子结点，相应地，该结点称为孩子的双亲结点。如果存在树中的一个结点序列K1，K2，.

5、..，Kj，使得结点Ki是结点Ki+1的双亲结点(1≤i≤j-1)，则称该结点序列是树中从结点K1到结点Kj的一条路径。我们把路径所经过的边(即连接两个结点的线段)的数目称作这条路径的长度。如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先结点，也称结点M是结点K的子孙结点。注意，任一结点既是它自己的祖先也是它自己的子孙。树的相关术语树中一个结点的高度是指：从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的深度或层数。根结点的深度为0，其余结点的深度为其双亲结点的深度加1。深度相同

6、的结点属于同一层。ABCDEFGHJI第2层第0层第1层第3层ABCDEFGHJI树的相关术语树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子孙关系。但是树中的许多结点之间仍然没有这种关系。例如兄弟（同一个双亲的孩子称为兄弟）结点之间就没有祖先子孙关系。如果我们在树的每一组兄弟结点之间定义一个从左到右的次序（即不能互换），则得到一棵有序树；否则称为无序树。设结点n的所有儿子按其从左到右的次序排列为：n1，n2，…，nk，则我们称n1是n的最左儿子，或简称左儿子，并称ni是ni-1的右邻兄弟，或简称右兄弟(i=2,3,..k)。二叉树的定义二叉树（BinaryTree）是

7、n（n≥0）个结点的有限集合，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。ABABABCA（a）空二叉树（b）根和空的左右子树（c）根和非空左子树，空的右子树（d）根和空的左子树，非空右子树（e）根和非空的左右子树二叉树不是树的特例二叉树与无序树不同：二叉树中，每个结点最多只能有两棵子树，且有左右之分。树不能为空，但二叉树可以为空，因此二叉树并非是树的特殊情形，它们是两种不同