非线性数据结构树和.ppt

第2章 非线性数据结构 树和图,西安交通大学计教中心 ,[第2页/91],树形结构,树形结构是以分支关系来定义的层次结构在客观世界中树形结构广泛存在，并应用于： 人类社会的族谱、家谱、行政区域划分管理； 各种社会组织机构； 在计算机领域中，用树表示源程序的语法结构； 在OS中，文件系统、目录等组织结构也是用树来表示的[第3页/91],树的逻辑结构,树是一种数据结构，可用二元组表示为： Tree=（D，R） 其中： D 是具有相同特性的数据元素的集合； R 是数据元素间逻辑关系的集合，且满足： 在D中存在唯一的称为根的数据元素，没有前趋； D中其余数据元素都有且只有一个前趋； D中所有元素，或有若干个互不相同的后继（子树），或无后继（叶结点）； 则称Tree为树[第4页/91],树的递归定义:,树是由n个具有相同特性的数据元素组成的集合若n=0，则称其为空树一棵非空树T必须满足： 1）其中有一个特定的元素称为T的根root 2）除根以外的集合可被划分为m个不相交的子集T1，T2，…，Tm，其中每个子集都是树它们称为根root的子树[第5页/91],树结构举例,C1（章） BOOK  1.1(节) 1.2 C1 C2 C3    C2 2.1 1.1 1.2 2.1 2.2 2.3      2.11 2.12 2.2 2.1.1 2.1.2   2.3 C3,,,,,,,,,,,,,,,,,,,,书目录 目录树 树结构,[第6页/91],与树相关的术语,• 结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。

• 结点的度：结点拥有的非空子树的个数 • 树的度：树中所有结点的度的最大值 • 叶子结点：度为0的结点 • 分支结点：至少有一个非空子树的结点 • 孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点[第7页/91],• 兄弟结点：具有相同父结点的结点互为兄弟结点 • 结点的层次：根结点的层次为1,其子结点的层次为2依次类推，子结点的层次总比父结点多一层 • 树的深度：树中结点所在的最大层次 • 有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树否则称为无序树 • 森林：由零棵或有限棵互不相交的树组成的集合[第8页/91],二叉树的定义,二叉树是另一种树形结构： Binary_Tree =( D,R) 其中: D 是具有相同性质的数据元素的集合; R 是在D上某个两元关系的集合,且满足: D中存在唯一称为根的数据元素,没有前趋; D中其余元素都有且仅有一个前趋; 每个结点至多只有两个子树; D中元素,或有两个互不相交后继,或无后继; 左、右子树分别又是一棵二叉树[第9页/91],二叉树的五种基本形态,,（a） （b） （c）,（d） （e）,O 空结点,O 单个结点,右子树为空的二叉树,左子树为空的二叉树,左、右子树非空的二叉树,,[第10页/91],二叉树与树的区别,表达形式（对3个结点） 普通树 二叉树 （a） （b） （c） （d） （e）,O,O,O,O,O,O,,,有两种不同形式,（a）,（b）,O,O,O,O,O,O,O,O,O,O,O,O,O,O,O,,,,,,,,,,,有五种不同形式,,,[第11页/91],二叉树与树的区别（二）,观念 二叉树的子树有顺序关系，分左子树和右子树，而树则无此区分； 二叉树的分支度一定为0、1或2，而树的度可大于2。

[第12页/91],特殊二叉树,满二叉树 完全二叉树 平衡二叉树 二叉排序树,[第13页/91],满二叉树,当二叉树每个分支结点的度都是2，且所有叶子结点都在同一层上，则称其为满二叉树 若k为二叉树T的深度，且T中共有2k-1个结点（k  1），则称T为满二叉树 （a） 满二叉树 （b）非满二叉树,[第14页/91],完全二叉树,从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树 （a）完全二叉树 （b） 非完全二叉树,叶结点只可能出现在层次最大的两层上[第15页/91],平衡二叉树,二叉树上任一结点的左子树深度减去右子树深度的差值，称为该结点的平衡因子 任意结点左、右子树的深度之差的绝对值1 ，这样的树称为平衡二叉树a）平衡二叉树 （b）非平衡二叉树,[第16页/91],二叉排序树定义,二叉排序树 或者是空二叉树； 或者是： 左子树上所有结点的值均小于根结点的值； 右子树上所有结点的值均大于等于根结点的值； 左、右子树本身又是一棵二叉排序树10,5,,7,11,,,,,,,,,14,18,15,15,,,,,,,,14,18,5,10,12,13,7,,,,,,,,（a）二叉排序树 （b）非二叉排序树,[第17页/91],二叉树的性质一,二叉树的第i层上至多有2i-1个结点（ i  1）。

利用归纳法证明： i=1时，只有一个结点，对的； 假设对所有的j，1 j  i，命题成立， 即在第j层上，至多有2j-1 个结点 由归纳假设，第i-1层上至多有2i-2 个结点由于二叉树的每个结点的度至多为2，故第i层上的最大结点数为第i-1层上的最大结点数的2倍，即 2×2i-2 = 2i-1[第18页/91],二叉树的性质二,深度为h的二叉树上至多含2h-1个结点(h≥1)证明：由性质一可见，深度为h的二叉树的最大结点数为：,[第19页/91],包含n(n0)个结点的二叉树总的分支数为n-1二叉树的性质三,证明： 二叉树中除了根结点之外每个元素有且只有一个父结点在所有子结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支，因此二叉树总的分支数为n-1[第20页/91],任意二叉树，若含有n0个叶结点、n2个度为2的结点，则必存在关系式n0=n2+1 二叉树的性质四,证明：设二叉树含有n1个度为1的结点，则二叉树结点总数显然为： n0 + n1 + n2 （2-2）,再看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支又因为除根结点外，其余每个结点都有一个分支进入。

因此二叉树的分支数加1就是结点总数即结点总数为：,1 + n1 + 2n2 （2-3） 由（2-2）和（2-3）两式可知：n0=n2+1,[第21页/91],具有n个结点的完全二叉树的深度为 [log2(n)]+1二叉树的性质五,证明： 假设二叉树的深度为h， 则必有2h-1-1n≤2h-1， 于是有2h-1n+1≤2h，也就是 2h-1≤n2h， 从而得到h-1≤log2(n)h， 于是h=[log2(n)]+1[第22页/91],若对含n个结点的完全二叉树从上到下、从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点： ① 若i=1，则该结点是二叉树的根，无父结点否则，编号为[i/2]的结点为其父结点； ② 若2in，则该结点无左孩子否则，编号为2i的结点为其左孩子结点； ③ 若2i+1n，则该结点无右孩子否则，编号为2i+1的结点为其右孩子结点 证明：通过对i进行归纳即可得证二叉树的性质六,[第23页/91],验证性质六,,,第i个结点就存放在第i个位置上； 第i个结点（i1)的父结点就存放在第 i/2个位置; 第i个结点的左子结点就存放在第2*i的位置;右子存放在第2*i+1的位置（若2i+1＜n ）。

[第24页/91],二叉树的链式存储,结点定义： struct BinTreeNode { ElemType data; struct BinTreeNode *leftChild, *rightChild; }; struct BinTreeNode *root; // 定义根结点指针 这里leftChild和rightChild分别为某一结点指向其左孩子和右孩子的指针对于叶结点或一个新生成的结点而言，其左孩子和右孩子指针都为空值[第25页/91],利用这种结点形式存储的树一般称为二叉链表从根结点出发，可以访问二叉树的任何结点为了能够访问二叉树，必须保留指向根结点的指针这和单链表必须保留头指针的道理一样[第26页/91],二叉树的遍历,遍历（Traversing）是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次遍历的方法很多，常用的有： 前序法（PreOrder） 中序法（InOrder） 后序法（PostOrder）,[第27页/91],前序法（PreOrder）,方法描述： 从根结点a开始访问， 接着访问左子结点b， 最后访问右子结点c。

即：,根,左子,右子,,,,,a b c,[第28页/91],中序法（InOrder）,方法描述： 从左子结点b开始访问， 接着访问根结点a， 最后访问右子结点c 即：,根,左子,右子,,,,,b a c,[第29页/91],后序法（PostOrder）,方法描述： 从左子结点b开始访问， 接着访问右子结点c， 最后访问根结点a 即：,根,左子,右子,,,,,b c a,[第30页/91],二叉树的遍历举例,,前序遍历序列： 中序遍历序列： 后序遍历序列：,DGEBHIFCA,DBGEACHFI,ABDEGCFHI,[第31页/91],二叉树遍历算法（递归、前序法）,void PreOrder(BinTreeNode *t) { if (t) { Visit( t ); //访问根结点 PreOrder( t-leftChild ); //遍历左子树 PreOrder( t-rightChild ); //遍历右子树 } },前序遍历二叉树的序列为： A B C D E F,[第32页/91],二叉树遍历算法（递归、前序法验证）,打印A 取A.左子(B) 打印B 取B.左子(C) 打印C 取C.左子(空) 取C.右子(空) 取B.右子(D) 打印D 取D.左子(E) 打印E 取E.左子(空) 取E.右子(空) 取D.右子(F) 打印F 取F.左子(空) 取F.右子(空) 取A.右子(空) 结束,,,,,,,A,B,C,D,E,F,[第33页/91],（2）中序遍历 对一颗非空二叉树进行中序遍历时，首先按中序遍历方式访问左子树，然后访问根结点，最后按中序遍历方式访问右子树。

中序遍历算法如下： void InOrder(BinTreeNode *t) { if(t) { } },InOrder( t-leftChild ); // 遍历左子树 Visit( t ); // 访问根节点 InOrder( t-rightChild ); // 遍历右子树,[第34页/91],（3）后序遍历 对一颗非空二叉树进行中序遍历时，首先按后序遍历方式访问左子树，然后按后序遍历方式访问右子树，最后访问根结点后序遍历算法如下： void PostOrder(BinTreeNode *t) { if(t) { } },PostOrder( t-leftChild ); // 遍历左子树 PostOrder( t-rightChild ); // 遍历右子树 Visit( t ); // 访问根节点,[第35页/91],表达式树及应用,在计算机中对表达式进行分析和计算是一项重要的任务 举例，用二叉树表示表达式： a + b * （ c - d ）－ｅ／ｆ 前序遍历序列：－＋ａ＊ｂ－ｃｄ／ｅｆ 中序遍历序列：ａ＋ｂ＊ｃ－ｄ－ｅ／ｆ 后序遍历序列：ａｂｃｄ－＊＋ｅｆ／－ 分析： 每。