《数据结构吴跃ch031》由会员分享，可在线阅读，更多相关《数据结构吴跃ch031（42页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树数据结构与算法数据结构与算法 主讲：吴跃主讲：吴跃教教教教 授授授授 电子科技大学电子科技大学电子科技大学电子科技大学计算机学院计算机学院计算机学院计算机学院吴吴 跃、李树全、尚明生、陈端兵编跃、李树全、尚明生、陈端兵编机械工业出版社机械工业出版社数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树树是非常重要和经常使用的一类非线性树是非常重要和经常使用的一类非线性结构。在线性结构中，数据元素之间至多有结
2、构。在线性结构中，数据元素之间至多有一个前驱和一个后继，表示的是数据元素之一个前驱和一个后继，表示的是数据元素之间一对一的关系。间一对一的关系。在树这类非线性结构中，数据元素之间在树这类非线性结构中，数据元素之间至多有一个前驱，但是可以有多个后继，表至多有一个前驱，但是可以有多个后继，表示的是数据元素之间一对多的关系。示的是数据元素之间一对多的关系。 二叉树二叉树二叉树的变形二叉树的变形树和森林树和森林树的变形树的变形树的应用树的应用数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树3.1 二叉树二叉树3.1.1 二叉树的
3、根本概念和性质二叉树的根本概念和性质二叉树的定义：二叉树是二叉树的定义：二叉树是n(n0)个具有相个具有相同类型的数据元素的有限集合，当同类型的数据元素的有限集合，当n=0时称时称为空二叉树，当为空二叉树，当n0时，数据元素分为：一时，数据元素分为：一个称为根的数据元素和两棵分别称为左子个称为根的数据元素和两棵分别称为左子树和右子树的数据元素的集合，左、右子树和右子树的数据元素的集合，左、右子树互不相交，并且他们也都是二叉树。树互不相交，并且他们也都是二叉树。二叉树中的数据元素又称作结点。二叉树中的数据元素又称作结点。数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学
4、数据结构与算法数据结构与算法 第第3章章 树树 即：二叉树或为空树，或是由一个根结点加上即：二叉树或为空树，或是由一个根结点加上两棵分别称为两棵分别称为左子树左子树和和右子树右子树的、的、互不交的互不交的二二叉树组成。叉树组成。ABCDEFGHK根结点左子树右子树数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树二叉树的特点：二叉树的特点： 每个结点最多只有两棵子树，即不存结每个结点最多只有两棵子树，即不存结点度大于点度大于2 2的结点；的结点； 子树有左右之分，不能颠倒。子树有左右之分，不能颠倒。324123413241
5、数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树二叉树的五种根本形态：二叉树的五种根本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树左右子树均不为空均不为空树树数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树根本概念根本概念结点的度结点的度结点所拥有的子树的个数结点所拥有的子树的个数叶子叶子度为度为0的结点的结点孩子孩子结点子树的根结点子树的根双亲双亲孩子结点的上层结点孩子结点的上层结点
6、子孙子孙以某结点为根的子树中的任一结点以某结点为根的子树中的任一结点 祖先祖先从根到该结点所经分支上的所有结点从根到该结点所经分支上的所有结点结点的层次结点的层次从根结点起，根为第一层，它从根结点起，根为第一层，它的孩子为第二层的孩子为第二层 ，孩子的孩子为第三层，孩子的孩子为第三层，兄弟兄弟 同一双亲的孩子互为兄弟同一双亲的孩子互为兄弟 堂兄弟堂兄弟其双亲在同一层的结点互为堂兄弟其双亲在同一层的结点互为堂兄弟 二叉树的度二叉树的度二叉树中最大的结点度数二叉树中最大的结点度数二叉树的深度二叉树的深度二叉树中结点的最大层次数二叉树中结点的最大层次数数据结构数据结构UESTC 电子科技大学电子科技
7、大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为指的是深度为k且含有且含有2k-1个结点的二叉树。个结点的二叉树。满二叉树中所有分支结点都满二叉树中所有分支结点都存在左子树和右子树，并且存在左子树和右子树，并且所有叶子结点都在同一层上。所有叶子结点都在同一层上。完全二叉树完全二叉树：树中所含树中所含的的 n 个结点和满二叉树个结点和满二叉树中中编号为编号为 1 至至 n 的结点的结点一一对应。一一对应。123456789 10 11 12 13 14 15abcdefghij数据结构数据结构UESTC
8、电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树性质性质 1 ：在二叉树的第在二叉树的第 i 层上至多有层上至多有2i-1 个结点。个结点。 (i1)用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点：层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的假设对所有的 j，1 j i，命题成立；命题成立；二叉树上每个结点至多有两棵子树，二叉树上每个结点至多有两棵子树，那么第那么第 i 层的结点数层的结点数 = 2i-2 2 = 2i-1 。每层的最大结点个数是确定的。每层
9、的最大结点个数是确定的。数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树性质性质 2 ：深度为：深度为 k 的二叉树上至的二叉树上至多含多含 2k-1 个结点个结点k1。证明：证明： 基于性质基于性质1，深度为，深度为 k 的二叉树上的二叉树上的结点数至多为：的结点数至多为： 20+21+ +2k-1 = 2k-1 深度一定，二叉树的最大结点数也是确定的。深度一定，二叉树的最大结点数也是确定的。深度一定，二叉树的最大结点数也是确定的。深度一定，二叉树的最大结点数也是确定的。数据结构数据结构UESTC 电子科技大学电子科技
10、大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树性质性质3：叶结点与双分支结点的关系叶结点与双分支结点的关系 对任何一棵二叉树对任何一棵二叉树T，设，设叶子结点数为叶子结点数为n0，度为，度为2的结点数为的结点数为n2，那么，那么，n0=n2+1。证明：证明： 假设度为假设度为1的结点数为的结点数为n1，二叉树总结点数为，二叉树总结点数为n，那么：，那么：n=n0+n1+n2孩子结点个数孩子结点个数=n-1孩子结点个数孩子结点个数=n1+2n2n=孩子结点个数孩子结点个数+1=n1+2n2+1=n0+n1+n2，化简得：化简得：n0=n2+1 数据结构数据结构UEST
11、C 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树 性质性质4：具有：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1证明：证明：深度为深度为k的完全二叉树最少有的完全二叉树最少有2k-1个结个结点，最多有点，最多有2k-1个结点，因此，结点数个结点，因此，结点数n满满足足2k-1n2k，两边取对数得：，两边取对数得：k-1log2nk，即：，即：klog2n+11，那么其双亲是，那么其双亲是 i/2 如果如果2in，那么结点，那么结点i无左孩子；如果无左孩子；如果2i n，那么其左孩子是，那么其左孩子是2i如果如果2
12、i+1n，那么结点，那么结点i无右孩子；如果无右孩子；如果2i+1 n，那么其右孩子是，那么其右孩子是2i+1证明：假设结点证明：假设结点i在第在第k层，其双亲层，其双亲j在第在第k-1层第层第q个结点，那么个结点，那么j的编号为：的编号为：j=2k-2-1+q 如果如果i是是j的左孩子的左孩子 ：i=2k-1-1+2(q-1)+1=2k-1+2q-2 如果如果i是是j的右孩子的右孩子 ： i=2k-1-1+2(q-1)+2=2k-1+2q-1 结点结点i的双亲的双亲j = i/2 假设结点假设结点j有左孩子，即有左孩子，即2jn，那么其左孩子为，那么其左孩子为2j； 假设结点假设结点j有右孩
13、子，即有右孩子，即2j+1n，那么其右孩子为，那么其右孩子为2j+1 数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树 二叉树的存储结构二叉树的存储结构二、链式存储二、链式存储一、一、 顺序存储顺序存储数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树一、二叉树的顺序存储结构一、二叉树的顺序存储结构 按完全二叉树顺序存储按完全二叉树顺序存储 完全二叉树中，结点完全二叉树中，结点i的左孩子为的左孩子为2i，右孩子为右孩子为2i+1，双亲为，双亲为 i/
14、2 ，因此如果将完全二叉树从上到下，从左到右，因此如果将完全二叉树从上到下，从左到右，从从1开始连续编号，把编号为开始连续编号，把编号为i的结点存放在线的结点存放在线性存储单元的性存储单元的第第i个位置个位置，那么它的，那么它的左孩子存左孩子存放于放于2i，右孩子存放于右孩子存放于2i+1的位置。的位置。n个结点的完全二叉树可存放在从个结点的完全二叉树可存放在从1到到n的一片的一片连续存储单元中连续存储单元中 数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树完全二叉树的顺序存储完全二叉树的顺序存储 用一组地址连续的存储单
15、元，以层序顺序存放二用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之叉树的数据元素，结点的相对位置蕴含着结点之间的关系。间的关系。数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树 一般二叉树的顺序存储一般二叉树的顺序存储 把一般的二叉树先补成完全二叉树，然后按照完全二叉树的顺序把一般的二叉树先补成完全二叉树，然后按照完全二叉树的顺序存储方式进行存储，而新补上去的结点只占位置，不存放结点数存储方式进行存储，而新补上去的结点只占位置，不存放结点数据。据。 KHGJI18数据结构数据结构UE
16、STC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树一般二叉树的顺序存储一般二叉树的顺序存储 19数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树二、二叉树的链式存储二、二叉树的链式存储1. 1. 二叉链表二叉链表2三叉链表三叉链表数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树ADEBCF rootlchild data rchild结点结构结点结构:1. 1. 二叉链表二叉链表typedef s
17、truct BiTreeNode Datatype data; struct BiTreeNode *lchild, rchild;BiTreeNode, *BiTree;数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树FEDABC root 2三叉链表三叉链表parent lchild data rchild结点结构结点结构:typedef struct BiTreeNode Datatype data; struct BiTreeNode *lchild, *rchild, *parent;BiTreeNode, *
18、BiTree; 数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树3.1.3 二叉树的遍历二叉树的遍历问题的提出问题的提出顺着某一条搜索路径巡访二叉树中的结点，使得每个顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。结点均被访问一次，而且仅被访问一次。“遍历是任何类型均有的操作，对线性结构而言，遍历是任何类型均有的操作，对线性结构而言，只有一条搜索路径只有一条搜索路径(因为每个结点均只有一个后继因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结故不需要另加讨论。而
19、二叉树是非线性结构，每个结点有两个后继，那么存在如何遍历即按什么样的搜索点有两个后继，那么存在如何遍历即按什么样的搜索路径遍历的问题路径遍历的问题常见的遍历方式有：常见的遍历方式有：递归遍历递归遍历层次遍历层次遍历非递归遍历非递归遍历数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树顺着某一条搜索路径顺着某一条搜索路径巡访巡访二叉树中的结点，二叉树中的结点，使得每个结点使得每个结点均被访问一次均被访问一次，而且，而且仅被访问仅被访问一次一次。3.1.3 二叉树的遍历二叉树的遍历访问访问是一种抽象操作，是对结点的某种处理，例
20、如可以是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任是求结点的度、或层次、打印结点的信息，或做其他任何工作。一次何工作。一次遍历遍历后，使树中结点的非线性排列，按访后，使树中结点的非线性排列，按访问的先后顺序变为某种线性排列。问的先后顺序变为某种线性排列。数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树 “遍历是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构， 每个结点有两个后继，每个结点有两个后继，
21、那么存在如何遍历即按什么样的搜索那么存在如何遍历即按什么样的搜索路径遍历的问题。路径遍历的问题。数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树 假设二叉树非空，那么，1访问根结点；2先序遍历左子树；3先序遍历右子树。先序遍历算法：先序遍历算法：数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树二叉树的递归遍历二叉树的递归遍历先序遍历先序遍历DLRADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C数据结构数据结构UE
22、STC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树 假设二叉树非空，那么，1中序遍历左子树；2访问根结点；3中序遍历右子树。中序遍历算法：中序遍历算法：数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树二叉树的递归遍历二叉树的递归遍历中序遍历中序遍历LDRADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树 假设二叉树非
23、空，那么，1后序遍历左子树；2后序遍历右子树；3访问根结点。后序遍历算法：后序遍历算法：数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树二叉树的递归遍历后序遍历后序遍历LRDADBC L R DL R DL R DADCL R D后序遍历序列： D B C AB数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树二叉树的层次遍历二叉树的层次遍历二叉树的层次遍历是指从二叉树的根结点开始，二叉树的层次遍历是指从二叉树的根结点开始，从上到下逐层遍历，同一层中
24、从左到右访问二从上到下逐层遍历，同一层中从左到右访问二叉树的结点。层次遍历中，对一层的结点访问叉树的结点。层次遍历中，对一层的结点访问完以后，再按照它们的访问次序依次访问各个完以后，再按照它们的访问次序依次访问各个结点的左孩子和右孩子，这样一层一层地进行，结点的左孩子和右孩子，这样一层一层地进行，先遇到的结点先访问先遇到的结点先访问首先将根结点入队，然后从对头取一个元素，首先将根结点入队，然后从对头取一个元素，每取一个元素，执行如下每取一个元素，执行如下3个动作：个动作：1. 访问该元素所指结点；访问该元素所指结点；2. 如果该元素所指结点有左孩子，那么左孩子如果该元素所指结点有左孩子，那么左
25、孩子指针入队指针入队3. 如果该元素所指结点有右孩子，那么右孩子如果该元素所指结点有右孩子，那么右孩子指针入队指针入队数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树二叉树的非递归遍历二叉树的非递归遍历先序，中序，后序都是沿着图中路线进行：从树根开先序，中序，后序都是沿着图中路线进行：从树根开始沿左子树一直深入，直到最左端无法深入时，返始沿左子树一直深入，直到最左端无法深入时，返回，进入刚深入时遇到结点的右子树，再进行如此回，进入刚深入时遇到结点的右子树，再进行如此的深入和返回，直到最后从根结点的右子树返回到的深入和返回
26、，直到最后从根结点的右子树返回到根结点为止。根结点为止。先序：遇到结点就访问先序：遇到结点就访问中序：左子树返回时访问中序：左子树返回时访问后序：右子树返回时访问后序：右子树返回时访问 深入返回的过程满足栈的特征，可用栈实现二叉树的深入返回的过程满足栈的特征，可用栈实现二叉树的遍历遍历数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树二叉树的非递归遍历二叉树的非递归遍历例子：中序遍历非递归算法例子：中序遍历非递归算法ABCDEFGpppp=NULLP-BP-AP-C访问序列：访问序列：CBpP-DpP-EEpP-GGpP-
27、FDFAp=NULL数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树void NRInOrder(BiTree bt)BiTree SMAXNODE, p=bt; /*定义栈定义栈S*/int top=-1;while(!(p=NULL & top=-1)/*p空同时栈空结空同时栈空结束束*/ while(p!=NULL) /* 找最左端结点找最左端结点,沿途结点入沿途结点入栈栈 */ Stop+=p; p=p-lchild; p=S-top; /*弹出栈顶元素弹出栈顶元素*/visit(p-data); /*访问结点访
28、问结点*/p=p-rchild; /*指向指向p的右孩子结点的右孩子结点*/ 为什么栈空了还不能结束？为什么栈空了还不能结束？看前例访问根看前例访问根A后，栈空，但是如后，栈空，但是如果果A右子树存在，此时右子树存在，此时p非空非空算法正确性分析：算法正确性分析：每个结点只入一次栈；不会重复访问，也不会遗漏。每个结点只入一次栈；不会重复访问，也不会遗漏。左孩子紧跟双亲结点入栈；右孩子在访问双亲结点后入栈；左孩子紧跟双亲结点入栈；右孩子在访问双亲结点后入栈；结点在出栈时被访问。结点在出栈时被访问。数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与
29、算法 第第3章章 树树2、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 (先序遍历先序遍历)3、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)1、建立二叉树、建立二叉树(先序和中序先序和中序)3.1.4 二叉树遍历算法的应用举例二叉树遍历算法的应用举例数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树思考：思考：仅知道二叉树的先序序列能否唯一确定一颗二叉树？仅知道二叉树的先序序列能否唯一确定一颗二叉树？知道同一颗树的两种不同序列能否唯一确实定一颗二叉树知道同一颗树的两种不同序列能否唯一确实定一颗二叉树?例如先
30、序和中序、先序和后序、后序和中序、层次和中序例如先序和中序、先序和后序、后序和中序、层次和中序1. 由先序和中序遍历序列建立二叉树由先序和中序遍历序列建立二叉树 二叉树的先序序列二叉树的先序序列二叉树的中序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算
31、机科学 数据结构与算法数据结构与算法 第第3章章 树树2.二叉树中叶结点统计二叉树中叶结点统计3. 先序先序(中序或后序中序或后序)遍历二叉树，在遍历过遍历二叉树，在遍历过程中查找叶结点，将算法中程中查找叶结点，将算法中“访问结点的操访问结点的操作改为：判叶结点。作改为：判叶结点。4.空树：叶子空树：叶子=05.左右子树为空：叶子左右子树为空：叶子=16.其它其它 ：叶子：叶子=左子树叶子左子树叶子+右子树叶子右子树叶子数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树3、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)
32、算法根本思想算法根本思想: : 从二叉树深度的定义可知，二叉树的深度从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加应为其左、右子树深度的最大值加1 1。由此，。由此，需先分别求得左、右子树的深度，算法中需先分别求得左、右子树的深度，算法中“访访问结点的操作为：求得左、右子树深度的最问结点的操作为：求得左、右子树深度的最大值，然后加大值，然后加 1 1 。 首先分析二叉树的深度和它的左、右子树深首先分析二叉树的深度和它的左、右子树深度之间的关系。度之间的关系。数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树3. 二叉树的深度二叉树的深度空树：深度空树：深度=0左右子树为空：深度左右子树为空：深度=1其它其它 ：深度：深度=1+max(左子树深度，右子树深度左子树深度，右子树深度数据结构数据结构UESTC 电子科技大学电子科技大学 计算机科学计算机科学 数据结构与算法数据结构与算法 第第3章章 树树作业作业 3.7习题习题P134一、选择题1-3二、填空题4三、简答题1-3四、算法设计题1
