数据结构课件第6章树和二叉树幻灯片.ppt

数据结构课件第6章树和二叉树幻灯片.ppt

  1. 1、本文档共91页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
void createBiThrTree(BiThrTree T); void preOrderTraverse(BiThrTree T,void (*visit)(TElemType)); BiThrNode* inOrderThreading(BiThrTree T); void inTraverseThr(BiThrTree T,void (*visit)(TElemType)); 2. 实现 inthreading.cpp #include inthreading.h //按先序次序输入二叉树中结点的值(#表示空格),构造二叉线索树T void createBiThrTree(BiThrTree T){ TElemType ch; cinch; if(ch==#) // 空 T=NULL; else{ T=new BiThrNode; if(!T) exit(1); T-data=ch; // 生成根结点 createBiThrTree(T-lchild); // 构造左子树 if(T-lchild) // 有左孩子 T-ltag=Link; createBiThrTree(T-rchild); // 构造右子树 if(T-rchild) // 有右孩子 T-rtag=Link; } } // 先序递归遍历T,对每个结点调用函数Visit一次且仅一次 void preOrderTraverse(BiThrTree T,void (*visit)(TElemType)){ if(T){ // T不空 visit(T-data); // 先访问根结点 preOrderTraverse(T-lchild,visit); // 再先序遍历左子树 preOrderTraverse(T-rchild,visit); // 最后先序遍历右子树 } } BiThrTree pre; // 全局变量,始终指向刚刚访问过的结点 void inThreading(BiThrTree p){ // 中序遍历进行中序线索化 if(p){ inThreading(p-lchild); // 左子树线索化 if(!p-lchild){ // 没有左孩子 p-ltag=Thread; // 前驱线索 p-lchild=pre; // 左孩子指针指向前驱 } if(!pre-rchild){ // 前驱没有右孩子 pre-rtag=Thread; // 后继线索 pre-rchild=p; // 前驱右孩子指针指向后继(当前结点p) } pre=p; // 保持pre始终指向刚刚访问过的结点 inThreading(p-rchild); // 右子树线索化 } } //中序遍历二叉树T,并将其中序线索化, BiThrNode* inOrderThreading(BiThrTree T){ BiThrNode* Thrt=new BiThrNode; //Thrt指向头结点 Thrt-ltag=Link; Thrt-rtag=Thread; Thrt-rchild=Thrt; //右指针回指 if(!T) //若二叉树空,则左指针回指 Thrt-lchild=Thrt; else{ Thrt-lchild=T; pre=Thrt; inThreading(T); //中序遍历进行中序线索化 pre-rtag=Thread; //最后一个结点线索化 pre-rchild=Thrt; Thrt-rchild=pre; } return Thrt; } //中序遍历二叉线索树T(头结点)的非递归算法 void inTraverseThr(BiThrTree T,void (*visit)(TElemType)){ BiThrTree p; p=T-lchild; //p指向根结点 while(p!=T){ //空树或遍历结束时,p==T while(p-ltag==Link) p=p-lchild; visit(p-data); //访问左子树为空的结点 while(p-rtag==Threadp-rchild!=T){ p=p-rchild; visit(p-data); //访问后继结点 } p=p-rchild; } } 6.5 树和森林 6.5.1 树的存储结构 1. 双亲表示法 它是以一组连续的存储单元来存放树中的结点,每个结点有两个域:一个是d

文档评论(0)

开心农场 + 关注
实名认证
内容提供者

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

1亿VIP精品文档

相关文档