大学数据结构课件6.树和二叉树

《大学数据结构课件6.树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树前面讲的线性表主要表现的是数据元素之间的前后次序关系，是一种线性结构。树型结构是以分支关系定义的层次结构。树形结构在客观世界中广泛存在，如人类的家庭族谱及各种社会组织机构。又如计算机文件管理和信息组织也用到树形结构。本章讨论树的基本概念，重点讨论二叉树的有关概念、性质、存储结构和各种运算。6.1.1树的定义树(tree)是由n(n≥0)个结点组成的有限集合T。n=0的树称为空树；对n>0的树，有:(1)仅有一个特殊的结点称为根(root)结点，根结点没有前驱结点；(2)当n>1时，除根结点外其余的结点分为m(m>0)个互不相交

2、的有限集合T1,T2，…，Tm，其中每个集合Ti本身又是一棵树，称之为根的子树（subtree）。注：树的定义具有递归性，即“树中还有树”。仅有一个根结点的树是最小树，6.1树基本概念和术语6.1.2若干术语（从结构上分）分支结点：度不为0的结点，除叶结点之外的其余结点。ABCGEIDHFJMLK结点（node）：由数据元素和构造数据元素之间关系的指针组成结点的度：结点所拥有的子树的个数树的度：树中所有结点的度的最大值叶结点：度为0的结点，也称作终端结点结点的层次：从根结点到树中某结点所经路径上的分支数树的深度：树中所有结点的层次的最大值森林

3、：m（m≥0）棵树的集合6.1.2.若干术语（从关系上分）孩子(child)结点：树中一个结点的子树的根结点双亲(parent)结点：若树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点兄弟(sibling)结点：具有相同的双亲结点的结点ABCGEIDHFJMLK无序树：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树有序树：树中任意一个结点的各孩子结点有严格排列次序的树6.1.2若干术语（从结构上分）BEFLKBFELK6.1.3树的表示形式(1)倒悬树法(直观表示)(2)集合包含关系图法(3)凹入表示法ABCGEIDHFJ

4、MLKFEKLCGABIJMDHABCDEFGHIJKLM6.1.4树的抽象数据类型数据集合:树的结点集合，每个结点由数据元素和构造数　　　　　据元素之间关系的指针组成。操作集合:（1）创建MakeTree(T)（2）撤消DestroyTree(T)（3）双亲结点Parent(T,curr)（4）左孩子结点LeftChild(T,curr)（5）右兄弟结点RightSibling(T,curr)（6）遍历树Traverse(T,Visit())6.1.5树的存储结构树的结点之间的逻辑关系主要有双亲-孩子关系，兄弟关系。因此，从结点之间的逻辑关

5、系分，树的存储结构主要有：双亲表示法、孩子表示法、双亲孩子表示法和孩子兄弟表示法四种组合。指针有常规指针和仿真指针4H2G1F1E1D0C0B-1AI4dataparent012345678(1)双亲表示法(a)一棵树（b)仿真指针的双亲表示法存储结构树及其使用仿真指针的双亲表示法ABCFGEIHD(2)孩子表示法常规指针的孩子表示法BCrootA∧∧∧D∧∧∧E∧F∧∧∧G∧∧∧I∧∧∧H∧∧∧ABCFGEIHD双亲孩子表示法(3)双亲孩子表示法∧4H2G1F1E1D0C0B-1AI4dataparenthead012345678∧∧∧∧c

6、hildnext∧87∧∧∧123456ABCFGEIHD(4)孩子兄弟表示法常规指针的孩子兄弟表示法root∧BCDEFGHI∧∧∧∧∧∧∧∧∧AABCFGEIHD6.2二叉树二叉树(binarytree)：是n(n≥0)个结点的有限集合。n=0的树称为空二叉树；n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。其逻辑结构：一对二（1:2）左、右子树也是二叉树，所以子树也可以为空树。下图展现了五种不同形态的二叉树。6.2.1二叉树的定义n=0n=1n>1n>1n>1基本特征:①每个结点最多只有两棵子树（不存在

7、度大于2的结点）；②左子树和右子树次序不能颠倒。所以下面是两棵不同的树6.2.1二叉树的定义BACEDFGBACEDFG满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。BACEDFGHIJKLMNO完全二叉树：如果一棵深度为k，有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树称为完全二叉树。如下图所示BACEDFGHIJBACEDFGHIJKLMNO(a)满二叉树(b)完全二叉树数据集合：二叉树的结点集合，每个结点由数据元素和构

8、造数据元素之间关系的指针组成。操作集合：（1）创建MakeTree(T)（2）撤消DestroyTree(T)（3）左插入结点InsertLeftNode(curr