第5章 树及二叉树0524.ppt

  1. 1、本文档共161页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
三种遍历算法的执行轨迹 1. 遍历过程中,每个结点经历过3次: 1)从其双亲到该结点 2)从左子树返回 3)从右子树返回 2. 三种遍历序列即是访问的时刻不同而已 1)从其双亲到该结点—第一次访问(先序) 2)从左子树返回—第二次访问(中序) 3)从右子树返回—第三次访问(后序) template class T BiTree ::BiTree(BiNodeT * root){ creat(root);this-root=root; } void BiTree ::Creat(BiNodeT * root){ cinch; if (ch==#) root=NULL; else { root=new BiNodeT; root-data=ch; creat(root-lchild); creat(root-rchild); } } 建立二叉递归算法一 5.4 二叉树的存储 templateclass T BiTreeT::BiTree( ) { cout请输入创建一棵二叉树的结点数据endl; this-root = Creat( ); } BiNodeT* BiTreeT::Creat( ){ BiNodeT* root; T ch; cinch; if (ch==#) root = NULL; else{ root = new BiNodeT; //生成一个结点 root-data=ch; root-lchild = Creat( ); //递归建立左子树 root-rchild = Creat( ); //递归建立右子树 } return root; } 建立二叉递归算法二 5.4 二叉树的存储 二叉树算法设计拓展 遍历二叉树是二叉树各种操作的基础,遍历算法中对每个结点的访问操作可以是多种形式及多个操作,根据遍历算法的框架,适当修改访问操作的内容,可以派生出很多关于二叉树的应用算法。 void InOrder (BiNodeT *root) { if (root==NULL) return; else { InOrder(root-lchild); coutroot-data; InOrder(root-rchild); } } 二叉树算法设计拓展 设计算法求二叉树的结点个数。 int Count(BiNode *root) { if (!root) return 0; else { return Count(root-lchild) +Count(root-rchild)+1; } } 二叉树算法设计拓展 设计算法按前序次序打印二叉树中的叶子结点。 void PreOrder(BiNode *root) { if (root) { if (!root-lchild !root-rchild) coutroot-data; PreOrder(root-lchild); PreOrder(root-rchild); } } 二叉树算法设计拓展 设计算法求二叉树的深度。 int Depth(BiNode *root) { if (root= =NULL) return 0; else { hl= Depth(root-lchild); hr= Depth(root -rchild); return max(hl, hr)+1; } } 三叉链表 5.4 二叉树的存储 G F E D B A A B C D E F G ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ C 在二叉链表中,如何求某结点的双亲? 三叉链表 lchild data parent rchild 在二叉链表的基础上增加了一个指向双亲的指针域。 结点结构 其中:data、lchild和rchild三个域的含义同二叉链表的结点结构; parent域为指向该结点的双亲结点的指针。 5.4 二叉树的存储 A B C D E F

文档评论(0)

kehan123 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档