2019数据结构电子教案-深圳大学-自动化课件-ds-05.ppt
《2019数据结构电子教案-深圳大学-自动化课件-ds-05.ppt》由会员分享,可在线阅读,更多相关《2019数据结构电子教案-深圳大学-自动化课件-ds-05.ppt(179页珍藏版)》请在三一文库上搜索。
1、1,第五章 树与二叉树,数据结构电子教案,殷人昆,2,第五章 树与二叉树,树和森林的概念 二叉树 二叉树遍历 二叉树的计数 线索化二叉树 树与森林 堆 Huffman树,3,树和森林的概念,两种树:自由树与有根树。 自由树: 一棵自由树 Tf 可定义为一个二元组 Tf = (V, E) 其中V = v1, ., vn 是由 n (n0) 个元素组成的有限非空集合,称为顶点集合。E = (vi, vj) | vi, vj V, 1i, jn 是n-1个序对的集合,称为边集合,E 中的元素 (vi, vj)称为边或分支。,4,自由树,有根树: 一棵有根树 T,简称为树,它是n (n0) 个结点的有
2、限集合。当n = 0时,T 称为空树;否则,T 是非空树,记作,5,r 是一个特定的称为根(root)的结点,它只有直接后继,但没有直接前驱; 根以外的其他结点划分为 m (m 0) 个互不相交的有限集合T1, T2, , Tm,每个集合又是一棵树,并且称之为根的子树。 每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继。,6,树的基本术语,子女:若结点的子树非空,结点子树的根即为该结点的子女。 双亲:若结点有子女,该结点是子女双亲。,7,兄弟:同一结点的子女互称为兄弟。 度:结点的子女个数即为该结点的度;树中各个结点的度的最大值称为树的度。 分支结点:度不为0的结点即为分支结点
3、,亦称为非终端结点。 叶结点:度为0的结点即为叶结点,亦称为终端结点。 祖先:某结点到根结点的路径上的各个结点都是该结点的祖先。 子孙:某结点的所有下属结点,都是该结点的子孙。,8,结点的层次:规定根结点在第一层,其子女结点的层次等于它的层次加一。以下类推。 深度:结点的深度即为结点的层次;离根最远结点的层次即为树的深度。,9,高度:规定叶结点的高度为1,其双亲结点的高度等于它的高度加一。 树的高度:等于根结点的高度,即根结点所有子女高度的最大值加一。 有序树:树中结点的各棵子树 T0, T1, 是有次序的,即为有序树。 无序树:树中结点的各棵子树之间的次序是不重要的,可以互相交换位置。 森林
4、:森林是m(m0)棵树的集合。,10,树的抽象数据类型,template class Tree /对象: 树是由n (0) 个结点组成的有限集合。在 /类界面中的 position 是树中结点的地址。在顺序 /存储方式下是下标型, 在链表存储方式下是指针 /型。T 是树结点中存放数据的类型, 要求所有结 /点的数据类型都是一致的。 public: Tree (); Tree ();,11,BuildRoot (const T /在结点 p 下插入值为 value 的新子女, 若插 /入失败, 函数返回false, 否则返回true,12,bool DeleteChild (position p
5、, int i); /删除结点 p 的第 i 个子女及其全部子孙结 /点, 若删除失败, 则返回false, 否则返回true void DeleteSubTree (position t); /删除以 t 为根结点的子树 bool IsEmpty (); /判树空否, 若空则返回true, 否则返回false void Traversal (void (*visit)(position p); /遍历以 p 为根的子树 ;,13,二叉树的五种不同形态,L,L,R,R,二叉树 (Binary Tree),二叉树的定义 一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵分
6、别称为左子树和右子树的、互不相交的二叉树组成。,14,二叉树的性质,性质1 若二叉树结点的层次从 1 开始, 则在二叉树的第 i 层最多有 2i-1 个结点。( i1) 证明用数学归纳法 性质2 深度为 k 的二叉树最少有 k 个结点,最多有 2k-1个结点。( k1 ) 因为每一层最少要有1个结点,因此,最少结点数为 k。最多结点个数借助性质1:用求等比级数前k项和的公式 20 +21 +22 + +2k-1 = 2k-1,15,性质3 对任何一棵二叉树,如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有 n0n21 若设度为 1 的结点有 n1 个,总结点数为n, 总边数
7、为e,则根据二叉树的定义, n = n0+n1+n2 e = 2n2+n1 = n-1 因此,有 2n2+n1 = n0+n1+n2-1 n2 = n0-1 n0 = n2+1,16,定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的深度为 k,则共有 k 层。除第 k 层外,其它各层 (1k-1) 的结点数都达到最大个数,第k层从右向左连续缺若干结点,这就是完全二叉树。,17,性质4 具有 n (n0) 个结点的完全二叉树的深度为 log2(n+1) 设完全二叉树的深度为k,则有 2k-1-1 n 2k-1
8、变形 2k-1 n+12k 取对数 k-1 log2(n+1) k 有 log2(n+1) = k,上面k-1层结点数,包括第k层的最大结点数,23-1,24-1,18,性质5 如将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号1, 2, , n,则有以下关系: 若i = 1, 则 i 无双亲 若i 1, 则 i 的双亲为i2 若2*i = n, 则 i 的左子女为 2*i, 若2*i+1 = n, 则 i 的右子女为2*i+1 若 i 为奇数, 且i != 1, 则其左兄弟为i-1, 若 若 i 为偶数, 且i != n, 则其右兄弟为i+1,19,二叉树的抽象数据类型,t
9、emplate class BinaryTree /对象: 结点的有限集合, 二叉树是有序树 public: BinaryTree (); /构造函数 BinaryTree (BinTreeNode *lch, BinTreeNode *rch, T item); /构造函数, 以item为根, lch和rch为左、右子 /树构造一棵二叉树 int Height (); /求树深度或高度 int Size (); /求树中结点个数,20,bool IsEmpty (); /判二叉树空否? BinTreeNode *Parent (BinTreeNode *t); /求结点 t 的双亲 BinT
10、reeNode *LeftChild (BinTreeNode *t); /求结点 t 的左子女 BinTreeNode *RightChild (BinTreeNode *t); /求结点 t 的右子女 bool Insert (T item); /在树中插入新元素 bool Remove (T item); /在树中删除元素 bool Find (T /取得结点数据,21,BinTreeNode *getRoot (); /取根 void preOrder (void (*visit) (BinTreeNode *t); /前序遍历, visit是访问函数 void inOrder (vo
11、id (*visit) (BinTreeNode *t); /中序遍历, visit是访问函数 void postOrder (void (*visit) (BinTreeNode *t); /后序遍历, (*visit)是访问函数 void levelOrder (void (*visit)(BinTreeNode *t); /层次序遍历, visit是访问函数 ;,22,正则二叉树 理想平衡二叉树,满的,23,完全二叉树 一般二叉树 的顺序表示 的顺序表示,二叉树的顺序表示,24,极端情形: 只有右单支的二叉树,25,二叉树结点定义:每个结点有3个数据成员,data域存储结点数据,left
12、Child和rightChild分别存放指向左子女和右子女的指针。,二叉链表,二叉树的链表表示(二叉链表),26,三叉链表,二叉树的链表表示(三叉链表),每个结点增加一个指向双亲的指针parent,使得查找双亲也很方便。,27,二叉树链表表示的示例,二叉树 二叉链表 三叉链表,28,二叉链表的静态结构,29,二叉树的类定义,template struct BinTreeNode /二叉树结点类定义 T data; /数据域 BinTreeNode *leftChild, *rightChild; /左子女、右子女链域 BinTreeNode () /构造函数 leftChild = NULL;
13、 rightChild = NULL; BinTreeNode (T x, BinTreeNode *l = NULL, BinTreeNode *r = NULL) data = x; leftChild = l; rightChild = r; ;,30,template class BinaryTree /二叉树类定义 public: BinaryTree () : root (NULL) /构造函数 BinaryTree (T value) : RefValue(value), root(NULL) /构造函数 BinaryTree (BinaryTree /求结点数,31,BinTr
14、eeNode *Parent (BinTreeNode *current) return (root = NULL | root = current) ? NULL : Parent (root, current); /返回双亲结点 BinTreeNode *LeftChild (BinTreeNode *current) return (current != NULL)?current-leftChild : NULL; /返回左子女 BinTreeNode *RightChild (BinTreeNode *current) return (current != NULL)?current
15、-rightChild : NULL; /返回右子女 BinTreeNode *getRoot () const return root; /取根,32,void preOrder (void (*visit) (BinTreeNode *t) preOrder (root, visit); /前序遍历 void inOrder (void (*visit) (BinTreeNode *t) inOrder (root, visit); /中序遍历 void postOrder (void (*visit) (BinTreeNode *t) postOrder (root, visit); /
16、后序遍历 void levelOrder (void (*visit)(BinTreeNode *t); /层次序遍历 int Insert (const T /搜索,33,protected: BinTreeNode *root; /二叉树的根指针 T RefValue; /数据输入停止标志 void CreateBinTree (istream /查找,34,BinTreeNode *Copy (BinTreeNode *node); /复制 int Height (BinTreeNode *subTree); /返回树高度 int Size (BinTreeNode *subTree);
17、 /返回结点数 BinTreeNode *Parent (BinTreeNode * subTree, BinTreeNode *current); /返回父结点 BinTreeNode *Find (BinTreeNode * subTree, T /搜寻x,35,void Traverse (BinTreeNode *subTree, ostream /后序遍历,36,friend istream template BinTreeNode *BinaryTree: Parent (BinTreeNode *subTree, BinTreeNode *current) ,部分成员函数的实现,
18、37,/私有函数: 从结点 subTree 开始, 搜索结点 t 的双 /亲, 若找到则返回双亲结点地址, 否则返回NULL if (subTree = NULL) return NULL; if (subTree-leftChild = current | subTree-rightChild = current ) return subTree; /找到, 返回父结点地址 BinTreeNode *p; if (p = Parent (subTree-leftChild, current) != NULL) return p; /递归在左子树中搜索 else return Parent (
19、subTree-rightChild, current); /递归在左子树中搜索 ;,38,template void BinaryTree: destroy (BinTreeNode * subTree) /私有函数: 删除根为subTree的子树 if (subTree != NULL) destroy (subTree-leftChild); /删除左子树 destroy (subTree-rightChild); /删除右子树 delete subTree; /删除根结点 ;,39,template istream,40,二叉树遍历,二叉树的遍历就是按某种次序访问树中的结点,要求每个结
20、点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV,41,中序遍历二叉树算法的框架是: 若二叉树为空,则空操作; 否则 中序遍历左子树 (L); 访问根结点 (V); 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f,中序遍历 (Inorder Traversal),-,-,/,+,*,a,b,c,d,e,f,42,二叉树递归的中序遍历算法,template void BinaryTree:InOrder (BinTr
21、eeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) InOrder (subTree-leftChild, visit); /遍历左子树 visit (subTree); /访问根结点 InOrder (subTree-rightChild, visit); /遍历右子树 ;,43,前序遍历二叉树算法的框架是: 若二叉树为空,则空操作; 否则 访问根结点 (V); 前序遍历左子树 (L); 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f,前序遍历 (Preorder Trav
22、ersal),-,-,/,+,*,a,b,c,d,e,f,44,二叉树递归的前序遍历算法,template void BinaryTree:PreOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) visit (subTree); /访问根结点 PreOrder (subTree-leftChild, visit); /遍历左子树 PreOrder (subTree-rightChild, visit); /遍历右子树 ;,45,后序遍历二叉树算法的框架是: 若二叉树为空,则空操作;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2019 数据结构 电子 教案 深圳大学 自动化 课件 ds 05
链接地址:https://www.31doc.com/p-2781838.html