《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第6章 树与二叉树-2》由会员分享，可在线阅读，更多相关《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第6章 树与二叉树-2（30页珍藏版）》请在金锄头文库上搜索。
1、1,第6章 树与二叉树,第2讲,第6章 树与二叉树,2,本章分为56讲( 每讲2学时),第1讲 6.1 树的基本概念和术语 6.2 二叉树 -6.2.1 ， 6.2.2,第2讲 6.2 二叉树-6.2.3 6.3 遍历二叉树 - 6.3.1,6.3.2,6.3.3,第3讲 6.3 遍历二叉树-6.3.4,6.3.5 6.4 线索二叉树,3,本章分为56讲( 每讲2学时),第4讲 6.5 二叉树、树和森林 6.6 树和森林的孩子兄弟表示及遍历 -6.6.1,第5讲 6.6 树和森林的孩子兄弟表示及遍历-6.6.2 6.7 树的应用 -6.7.1,第6讲 6.7 树的应用 -6.7.2,4,6.2
2、.3 二叉树的二叉链表类定义,设二叉树以二叉链表为存储结构，可设计一个二叉树二叉链表类。二叉树结点的结构定义为结构体NodeType。在此基础上定义二叉链表类BiTree。 本小节分两部分介绍该类的有关概念。首先给出类的定义；然后详细介绍怎样输入数据建立一棵二叉树。,5,1二叉链表类的定义,其中根结点的指针root做数据成员，它既是NodeType类型的指针，又是受护类型protected的成员，以备以后继承。 本类出现了公有和私有两种函数成员。 公有是类对外的接口，可通过对象名调用。私有函数只允许本类的成员函数调用，一些带型参的递归函数被设为私有函数。 本类使用了函数重载。,6,/定义结点结
3、构体,/Binary Tree- #include #include typedef int ElemType; struct NodeType /定义结点结构体 ElemType data; NodeType *lch; NodeType *rch; ;,7,/定义二叉树类,class BiTree public: BiTree() root=NULL; /构造函数，空树 BiTree() /析构函数 destroy(root) ; root=NULL; void creat(); /建立二叉树 void preorder() /先根遍历调用 preorder(root); void ino
4、rder() /中根遍历调用 inorder(root); void postorder() /后根遍历调用 postorder(root);,8,protected: NodeType *root; /数据成员，树根指针 private: void inorder(NodeType *p); /中根递归遍历 void preorder(NodeType *p); /先根递归遍历 void postorder(NodeType *p);/后根递归遍历 void destroy(NodeType / BiTree End,9,/删除二叉树的所有结点，被析构函数调用 void BiTree:des
5、troy(NodeType ,10,2.二叉树二叉链表的一个生成算法,为方便上机实验，介绍一种容易理解的创建二叉树的算法。主要利用性质5，对任意二叉树，先按满二叉树对其所有结点进行编号，如图（a）所示。 此树并非完全二叉树，结点的编号并不连续。此例的原始数据序列如图（b），照此一一输入即可生成二叉链表。,11,/建立二叉树-算法6.1,void BiTree:creat() NodeType *q, *s20; ElemType x; int i,j; coutix; while (i!=0),12,si=q; if (i=1) root=q; /q为树根结点 else j=i/2; / j为
6、双亲结点编号 if (i%2)=0) sj-lch=q; else sj-rch=q; coutix; /while i / creat end 本算法循环的结束条件是输入两个零。 若输入的第1组数据就是两个零，将返回空指针。,13,6.3 遍历二叉树,二叉树最主要、最基本的运算是遍历。 遍历二叉树是指以一定的次序访问二叉树中的每个结点，并且每个结点仅被访问一次。 访问结点是指对结点进行各种操作的简称。 例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。 遍历二叉树的过程实质是把二 叉树的结点进行线性排列的过程。,14,遍历的顺序,由于二叉树有左、右子树，所以
7、 遍历的次序不同，得到的结果就不同。 令L代表遍历左子树，T代表访问根结点，R代表遍历右子树，则对一棵二叉树的遍历可以有6种不同次序： LTR、LRT、TLR、TRL、RLT、RTL。 常用次序是先左（L）后右（R），则只有3种不同的遍历次序： LTR、TLR和LRT。 分别称作中根遍历二叉树，先根遍历二叉树和后根遍历二叉树。,15,遍历的搜索线路,设想有一条搜索路线（用虚线表示），从根结点的左侧开始，自上而下自左至右搜索，最后由根结点的右侧向上出去。考虑空子树，搜索线途经每个有效结点都是3次。 搜索线第1次经过结点就访问， 先根遍历。输出:A、B、C、D。 搜索线第2次经过结点才访问， 中根
8、遍历。输出: B、A、D、C。 搜索线第3次经过结点才访问， 后根遍历。输出：B、D、C、A。,教师需 详细讲解,16,选择二叉链表存储结构：,二叉链表的结点结构： struct NodeType ElemType data; NodeType *lch; NodeType *rch; ; 二叉链表类： class BiTree public:.;,17,6.3.1 先根遍历,如果根不空： （1）访问根结点； （2）按先根次序遍历左子树； （3）按先根次序遍历右子树。 否则返回。 分辨： “访问”操作是针对一个结点； “遍历”操作是针对一棵树。,18,先根遍历的递归算法,算法6.2 void
9、BiTree:preorder(NodeType *p) if(p != NULL) coutdatalch); /先根遍历左子树 preorder(p-rch); /先根遍历右子树 本算法作为BiTree类的私有成员函数。,19,先根遍历的递归算法的详细执行情况,教师需 详细讲解,20,写主函数，简单验证二叉链表类,int main() BiTree tree0; /声明二叉树对象，空树 tree0.creat(); /输入数据，建立二叉树 cout“n 先序遍历结果：“ ; tree0. preorder(); /先根遍历二叉树 _getch(); return 0; /- 这样我们可以具
10、体的输入数据，在内存中建立二叉树，并且先根遍历输出观看该树的数据内容了。,21,6.3.2 中根遍历,中根遍历递归的思路与先根遍历十分相似，只是在根不空的情况下所应执行的3条操作稍做调整即可。 如果根不空： （1）按中根次序遍历左子树； （2）访问根结点； （3）按中根次序遍历右子树。 否则返回。,22,中根遍历递归算法,算法6.3 void BiTree:inorder(NodeType *p) if(p != NULL) inorder(p-lch); /中根遍历左子树 coutdatarch); /中根遍历右子树 算法作为BiTree类的私有成员函数,23,中根遍历非递归算法，采用栈为辅
11、助结构,算法6.4 void BiTree:inorderz() NodeType *q; SqStack s; /声明创建一个栈对象，并且初始化空栈 q=root; int bool=1; / bool=1 继续循环；bool=0为栈空，结束循环 cout“n 中根遍历: n“;,使用栈的模板类，它的源代码参见10.1节,24,coutlch; if (s.IsEmpty() bool=0; /若栈空bool=0 else q=s.Pop(); coutdatarch; while (bool); /栈不空继续循环，否则结束 coutendl; ,25,中根非递归遍历，辅助的栈变化,26,6
12、.3.3 后根遍历,后根遍历的思想： 如果根不空： （1）按后根次序遍历左子树； （2）按后根次序遍历右子树； （3）访问根结点。 否则返回。,27,后根递归遍历算法,算法6.5 void BiTree:postorder(NodeType *p) if (p != NULL) postorder(p-lch); /后根遍历左子树 postorder(p-rch); /后根遍历右子树 coutdata“ “; /访问根结点 ,28,后根递归非遍历算法,算法6.6 void BiTree:postorderz() SqStack s; SqStack s2; /声明创建两个栈对象并且初始化空栈
13、NodeType *q; q=root; int bool=1; coutlch; ,用两个栈，s存放结点地址，s2存放搜索线途经的次数。,29,if (s.IsEmpty() bool=0; else if(s2.GetTop()=1) s2.Pop(); s2.Push(2); /第2次经过，修改s2 q=s.GetTop(); /不出栈s，取栈顶指针值 q=q-rch; else q=s.Pop(); /第3次经过，出栈访问结点 s2.Pop(); /同步出栈s2 coutdata“ “; q=NULL; /else while (bool); coutendl; ,30,小结,熟练掌握二叉树的二叉链表存储结构，以及在此基础上的先根、中根和后根递归遍历算法。 熟悉二叉树的中根非递归遍历和后根非递归遍历算法和特点。 重点在于掌握二叉树的各种遍历算法的实质，这是基本要求。,
