• 1. 数据结构中国地质大学信息工程学院 2015年秋
  • 2. 第五章 树
  • 3. 3内容提要5.1 树的基本概念 5.2 二叉树 5.3 二叉树的存储表示 5.4 二叉树的遍历及其应用 5.6 树与森林 5.7 树与森林的遍历及其应用 5.8 堆及其应用 5.9 Huffman树及其应用
  • 4. 4非线性结构 非线性结构是指在结构中至少存在一个数据元素,它具有两个或两个以上的直接前驱或直接后继。 树、二叉树:一对多 图、网络: 多对多211413121123467891055125643125436113318146651921
  • 5. 55.1 树的基本概念 例 客观世界中的树形结构: 人类社会的家谱,族谱; 各种组织机构的表示; 计算机领域: 编译程序的语法结构; 数据库系统中的信息组织; 磁盘文件的目录; 软件工程中的模块划分。祖父伯父父亲叔父堂兄你堂姐堂弟侄儿
  • 6. 6树结构示例1-模块划分
  • 7. 7树结构示例2:DNS命名语法: 主机名.单位名.类型名.国家代码 例如:rsc.cug.edu.cn以树型结构实现域名的搜索: www.cug.edu.cn在该树从根到叶子的各层结点就应是root、cn、edu、cug、www。 叶节点www另有一个数据域,存放中国地质大学站点的IP地址202.114.200.245
  • 8. 81.树的定义自由树: 一棵自由树 Tf 可定义为一个二元组 Tf = (V, E) 其中V = {v1, ..., vn} 是由 n (n>0) 个元素组成的有限非空集合,称为顶点集合。E = {(vi, vj) | vi, vj V, 1≤i, j≤n} 是n-1个序对的集合,称为边集合,E 中的元素 (vi, vj)称为边或分支。
  • 9. 9有根树一棵有根树T,简称为树,它是n (n≥0) 个结点的有限集合。当n = 0时,T 称为空树;否则,T 是非空树,记作 r 是一个特定的称为根(root)的结点,它只有直接后继,但没有直接前驱; 根以外的其他结点划分为 m (m  0) 个互不相交的有限集合T1, T2, …, Tm,每个集合又是一棵树,并且称之为根的子树。 每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继。
  • 10. 10树的固有特性:递归树的定义是递归的,即用树来定义树。 例ABEIDLHKCGFJAT={A,B,C,D,E,F,G,H,I,J,K,L}T1={B,E,F,J} T2={C,G,K,L} T3={D,H,I} T11={E,J} T12={F} ……
  • 11. 112.树的基本术语结点:包含数据项及指向其他结点的分支ABEHJDLIKCGFM结点的度(degree)该结点所拥有的子树的个数。树的度树中各结点的度的最大值。叶结点(leaf)分支结点(branch)度为0的结点,终端结点。度不为0的结点,非终端结点。
  • 12. 12树的基本术语(续1)孩子(子女、儿子)、双亲(父母、父亲)结点 树中一个结点的子树的根节点称为该结点的孩子。children 相应的,这个结点称为它的孩子结点的双亲。parent兄弟结点(sibling)同一个双亲的孩子之间互称兄弟。堂兄弟其双亲在同一层的结点互为堂兄弟。ABEHJDLIKCGFM
  • 13. 13树的基本术语(续2)祖先(ancestor) 一个结点的祖先是指从树的根到该结点所经分支上的所有结点。子孙(descendant)一个结点的子树的所有结点都称为该结点的子孙。有序树:树中结点的各棵子树 T0, T1, …是有次序的,即为有序树。 无序树:树中结点的各棵子树之间的次序是不重要的,可以互相交换位置。 森林:森林是m(m≥0)棵树的集合。
  • 14. 14树的基本术语(续3)结点的层数(级, level )规定树的根结点的层数为1, 其余结点的层数等于它的双亲结的层数加1。树的深度(depth)树中所有结点的最大层数。1层2层4层3层depth = 4DACBIJHGFEMLKheight = 4
  • 15. 15树的基本术语(续4)结点的高度规定树的叶结点的高度为1, 其双亲结点的高度等于它的高度加1。树的高度(height)等于根结点的高度, 即根结点所有子女高度的最大值加1。树的高度等同于其深度; 区别:定义的方向,高度是自底向上。
  • 16. 16两种数据结构的比较=线性结构==树形结构=第一个数据元素 (无前驱)最后一个数据元素 (无后继)多个叶子节点 (无后继)其它数据元素 (一个前驱,一个后继)树中其它节点 (一个前驱,多个后继)根节点 (无前驱)
  • 17. 173.树的ADT说明: 树是由n (≥0) 个结点组成的有限集合。 Position表示树中结点的地址。 在顺序存储方式下是下标型 在链表存储方式下是指针型 T 是树结点中存放数据的类型,要求所有结点的数据类型都是一致的。template class Tree { public: Tree (); 生成树的结构并初始化 ~Tree (); 释放树所占存储空间
  • 18. 18树的ADT(续1)position Root() ; //返回根结点地址;若树为空,则返回0 BuildRoot (const T& value); //建立树的根结点 position FirstChild(position p); //返回 p 第一个子女地址, 无子女返回 0 position NextSibling(position p); //返回 p 下一兄弟地址, 若无下一兄弟返回 0 position Parent(position p); //返回 p 双亲结点地址, 若 p 为根返回 0 T getData(position p); //返回结点 p 中存放的值
  • 19. 19树的ADT(续2)bool InsertChild(position p, T& value); //在结点 p 下插入值为 value 的新子女, //若插入失败, 函数返回false, 否则返回true bool DeleteChild (position p, int i); //删除结点 p 的第 i 个子女及其全部子孙结点, //若删除失败, 则返回false, 否则返回true void DeleteSubTree (position t); //删除以 t 为根结点的子树 bool IsEmpty (); //判树空否, 若空则返回true, 否则返回false void Traversal (void (*visit)(position p)); //遍历以 p 为根的子树 };
  • 20. 205.2 二叉树( Binary Tree)二叉树的定义二叉树是n(n≥0)个节点的有限的有序集合。当n=0时,为空二叉树;当n>0时,由两部分组成: 有且只有一个根节点root; 两棵互不相交的二叉树——左子树和右子树。 二叉树的度小于等于2; 两棵子树有左、右之分,不能互换; 递归也是二叉树固有的特性。
  • 21. 21二叉树的五种不同形态LLRR
  • 22. 221.二叉树的性质性质1:包含n(n>0)个元素的二叉树边数为n-1证明:二叉树中每个元素(除了根节点)有且只有一个父节点。在子节点和父节点间有且只有一条边,因此边数为n-1。ABDCFIH
  • 23. 23二叉树的性质(续1)性质2:一棵非空二叉树的第i层上最多有2i-1个节点(i≥1)证明:(数学归纳法) 当i=1,第1层上最多有21-1=1个节点,此时,只有根节点,所以结论正确。 假设对于第i=t命题成立,即非空二叉树第t层最多有2t-1个节点, 因为二叉树的每个节点最多有2个孩子节点,即每个节点的度至多为2,所以第t+1层上总数最多是第t层节点数的2倍,即最多为2×2t-1=2(t+1)-1,与结论相符,得证。
  • 24. 24二叉树的性质(续2)性质3:深度为 k 的二叉树最少有 k 个结点,最多有 2k-1个结点( k≥0 )证明:因为每层至少要有1个元素,因此元素数最少为h; 设深度为h的二叉树中的最多节点数为M,则证毕。
  • 25. 25二叉树的性质(续3)性质4:对于一棵非空二叉树,如果叶节点数为n0,度为2的节点数为n2,则有n0=n2+1。证明:(1)从节点类型: 叶节点:个数为n0 度为1的节点:个数为n1; 度为2的节点:个数为n2 ; 所以,总的节点数:n=n0+n1+n2 ①
  • 26. 26 (2)从分支情况: 根节点(1个):无分支进入它; 除根节点外,其它节点都是由一个分支进入的(即除根节点外,一个分支带一个节点) 所以,总的节点数:n=分支数+1又由于分支均由度为1和度为2的节点发出: 度为1的节点发出1×n1个 度为2的节点发出2×n2个所以,n=n1+2n2+1 ②由 ① 、②两式可得 n0+n1+n2 =n1+2n2+1 所以, n0= n2+1
  • 27. 27课堂练习 在一棵度为3的树中,若有2个度为3的节点,有1个度为2的节点,则有____个度为0的节点。   A.4   B.5    C.6   D.7 2004年软件设计师试题解:总节点数:n=n0+n1+n2+n3 =n0+0+1+2=n0+3 又 n=分支数+1=2*3+1*2+1=9 所以, n0=6C
  • 28. 28满二叉树和完全二叉树1、满二叉树(Full Binary Tree)的定义一棵高度为h,且有2h-1个节点的二叉树称为满二叉树。 特点:每一层上的节点数都是最大节点数。ABDGCFEIHLJMKON12345678 9 10 11 12 13 14 15 可对满二叉树的节点进行编号,从根节点起,自上而下,自左至右。 例n0=n2+1
  • 29. 29完全二叉树(Complete Binary Tree) 例 高度为h,有n个节点的二叉树,当且仅当其每一个节点都与高度为h的满二叉树中编号从1至n的节点一一对应,称为完全二叉树。 ……………. 1 ….………… 2 …………… 3……………. 4ABDGCFEIHJ12345678 9 10
  • 30. 30完全二叉树的特点(1)叶子节点只可能出现在层次最大的两层上。(2)对任一节点,其左分支下的子孙的最大层次不小于其右分支下的子孙的最大层次。 例非完全二叉树非完全二叉树ABDGCFEJ123456783ABDCFIH124578
  • 31. 31完全二叉树的两个性质性质5:具有n个节点的完全二叉树的深度h为 证明:根据二叉树的特性3,可得02h-1-1 所以 2h-1-1
  • 32. 32由性质5可得:包含n个元素的二叉树的高度最大为n,最小 。理想平衡二叉树
  • 33. 33性质6:如果将一棵有n个节点的完全二叉树自顶向下,同一层自左向右连续给节点编号1,2,…,n。设该完全二叉树中一元素的序号为i,1≤i≤n。则有下列关系成立: (2)当2i>n时,该元素无左孩子。否则,其左孩子的编号为2i;(3)若2i+1>n,该元素无右孩子。否则,其右孩子的编号为2i+1。(1)若i=1,则节点i为根,无双亲;若i>1,则节点i的双亲节点编号为 ;ABDGCFEIHJ12345678 9 10
  • 34. 34(4)若 i 为奇数, 且i != 1, 则其左兄弟为 i-1(5)若 i 为偶数, 且i != n, 则其右兄弟为 i+1(6)结点 i 所在层次为12348567910
  • 35. 352.二叉树的ADTtemplate class BinaryTree { public: BinaryTree (); //构造函数 BinaryTree (BinTreeNode *lch, BinTreeNode *rch, T item); //构造函数, 以item为根, lch和rch为左、右子树 //构造一棵二叉树 int Height (); //求树深度或高度 int Size (); //求树中结点个数
  • 36. 36二叉树的ADT(续1) bool IsEmpty (); //判二叉树空否? BinTreeNode *Parent (BinTreeNode *t); //求结点 t 的双亲 BinTreeNode *LeftChild (BinTreeNode *t); //求结点 t 的左子女 BinTreeNode *RightChild (BinTreeNode *t); //求结点 t 的右子女 bool Insert (T item); //在树中插入新元素 bool Remove (T item); //在树中删除元素 bool Find (T& item); //判断item是否在树中 bool getData (T& item); //取得结点数据
  • 37. 37二叉树的ADT(续2) BinTreeNode *getRoot (); //取根 void preOrder (void (*visit) (BinTreeNode *t)); //前序遍历, visit是访问函数 void inOrder (void (*visit) (BinTreeNode *t)); //中序遍历, visit是访问函数 void postOrder (void (*visit) (BinTreeNode *t)); //后序遍历, (*visit)是访问函数 void levelOrder (void (*visit)(BinTreeNode *t)); //层次遍历, visit是访问函数 };
  • 38. 385.3 二叉树的存储表示二叉树的存储结构 顺序存储方式:数组方式 链式存储方式:链表方式 适用情况 顺序存储:二叉树的大小和形态在数据处理过程中,不发生剧烈、动态的变化 链式存储:与之相反的情况
  • 39. 391. 顺序存储方式 用一组连续的存储单元来存放二叉树中的数据元素(借用一维数组来描述)。 一个有n个节点的二叉树,可以把它的节点顺序存入一维数组bt[n]中,其中编号为i的节点存入bt[i]中。 根据完全二叉树的特性6,节点在一维数组中的相对位置,即数组下标反映了完全二叉树节点之间的逻辑关系。
  • 40. 40完全二叉树的顺序存储ABDGCFEIHJ12345678 9 10ABCDEFGHIJ012345678910数组下标
  • 41. 41一般二叉树的顺序存储12345678 9 10 11 12 13ABCEDFGABC^DE^^^F^^G012345678910111213
  • 42. 42顺序存储的最坏情况 在最坏的情况下,一棵高度为h,且只有h个节点的右单支树(树中无度为2的节点)却需要分配2h个存储单元。A^B^^^C^^^^^^^D012345678910111213141512345678 9 10 11 12 13 14 15CABD【结论】二叉树的顺序存储结构适合完全二叉树的存储,但对一般的二叉树并不理想。
  • 43. 432. 链式存储方式1、二叉链表 节点结构 链表表示 当二叉树采用二叉链表存储结构时,如果其节点的左孩子或右孩子不存在,则相应的指针域为空; 设置一个头指针,指向二叉树的根节点,它可以唯一地确定一棵二叉树。leftChild data rightChilddataleftChildrightChild
  • 44. 44二叉链表示例ADBCEF^ABC^^D^E^^F^t 【思考】 有多少个指针域的值为0(NULL)?
  • 45. 45二叉链表的性质 在含有n个节点的二叉链表中有n+1个空指针域。证明:n个节点共有指针域2n个 n个节点共有分支n-1个 所以,n个节点共有空指针域2n-(n-1)=n+1个 必须从根节点开始,每遍历一个节点就要进行判断,看它的左、右孩子是不是已知的节点。 【思考】 怎样在二叉链表中寻找某个节点的父节点?
  • 46. 46三叉链表:便于查找父节点leftChild data parent rightChildparentdataleftChildrightChild三叉链表每个结点增加一个指向双亲的指针parent,使得查找双亲也很方便。
  • 47. 47三叉链表示例 例ADBCEF^A^BC^^D^E^^F^t
  • 48. 48静态链表结构二叉链表的静态结构ABCDFErootdata parent leftChild rightChild0 1 2 3 4 5A -1 1 -1 B 0 2 3 C 1 -1 -1 D 1 4 5 E 3 -1 -1 F 3 -1 -1
  • 49. 493.二叉树的类定义template struct BinTreeNode { //二叉树结点类定义 T data; //数据域 BinTreeNode *leftChild, *rightChild; //左子女、右子女链域 BinTreeNode () //构造函数 { leftChild = NULL; rightChild = NULL; } BinTreeNode (T x, BinTreeNode *l = NULL, BinTreeNode *r = NULL) { data = x; leftChild = l; rightChild = r; } };
  • 50. 50template class BinaryTree { public: BinaryTree () : root (NULL) { } //构造函数 BinaryTree (T value) : RefValue(value), root(NULL) { } //构造函数 BinaryTree (BinaryTree& s); //复制构造函数 ~BinaryTree () { destroy(root); } //析构函数 bool IsEmpty () { return root == NULL;} //判二叉树空否 int Height () { return Height(root); } //求树高度 int Size () { return Size(root); } //求结点数二叉树的类定义
  • 51. 51 BinTreeNode *Parent (BinTreeNode *t) { return (root == NULL || root == t) ? NULL : Parent (root, t); } //返回双亲结点 BinTreeNode *LeftChild (BinTreeNode *t) { return (t != NULL)?t->leftChild : NULL; } //返回左子女 BinTreeNode *RightChild (BinTreeNode *t) { return (t != NULL)?t->rightChild : NULL; } //返回右子女 BinTreeNode *getRoot () const { return root; } //取根二叉树的类定义(续1)
  • 52. 52 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); } //后序遍历 void levelOrder (void (*visit)(BinTreeNode *t)); //层次遍历 int Insert (const T item); //插入新元素 BinTreeNode *Find (T item) const; //搜索二叉树的类定义(续2)
  • 53. 53protected: BinTreeNode *root; //二叉树的根指针 T RefValue; //数据输入停止标志 void CreateBinTree (istream& in, BinTreeNode *& subTree); //从文件读入建树 bool Insert (BinTreeNode *& subTree, T& x); //插入 void destroy (BinTreeNode *& subTree); //删除 bool Find (BinTreeNode *subTree, T& x); //查找 二叉树的类定义(续3)
  • 54. 54 BinTreeNode *Copy (BinTreeNode *r); //复制 int Height (BinTreeNode *subTree); //返回树高度 int Size (BinTreeNode *subTree); //返回结点数 BinTreeNode *Parent (BinTreeNode * subTree, BinTreeNode *t); //返回父结点 BinTreeNode *Find (BinTreeNode * subTree, T& x) const; //搜寻x二叉树的类定义(续4)
  • 55. 55二叉树的类定义(续5) void Traverse (BinTreeNode *subTree, ostream& out); //前序遍历输出 void preOrder (BinTreeNode& subTree, void (*visit) (BinTreeNode *t)); //前序遍历 void inOrder (BinTreeNode& subTree, void (*visit) (BinTreeNode *t)); //中序遍历 void postOrder (BinTreeNode& Tree, void (*visit) (BinTreeNode *t)); //后序遍历
  • 56. 56 friend istream& operator >> (istream& in, BinaryTree& Tree); //重载操作:输入 friend ostream& operator << (ostream& out, BinaryTree& Tree); //重载操作:输出 }; 二叉树的类定义(续6)
  • 57. 57二叉树基本操作遍历:每个元素仅被访问一次,是基础操作! 确定其高度 确定其元素数目 复制 在屏幕或纸上显示二叉树 确定两棵二叉树是否一样 删除整棵树 若为数学表达式,计算该数学表达式 若为数学表达式树,给出对应的带括号的表达式
  • 58. 58课后作业P246 5.4 5.9