叉树与树课件

《叉树与树课件》由会员分享，可在线阅读，更多相关《叉树与树课件（77页珍藏版）》请在装配图网上搜索。

1、叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件kikkiiimM010122叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件ADT BinTree isoperations 叉树与树PPT课件end ADT BinTree 此外作为抽象数据类型，二叉树还应该有插入、删除和检索节点等运算，由于于本章关系不大，故省略。 由于二叉树的概念是递归定义的，二叉树中的每个结点也可标识以这个结点为根的二叉树，所以二叉树类型和二叉树中结点二叉树类型和二叉树中结点类型在具体实现时常常看成是同一种类型。类型在具体实现时常常看成是同一种类型。叉树与

2、树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件acbd叉树与树PPT课件叉树与树PPT课件先根次序周游： void preOrder( BinTree t) 中根次序周游： void inOrder(BinTree t) 后根次序周游： void postOrder(BinTree t) 注意是抽象算法，需要根据二叉树的实现方式进行修改。叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件 叉树与树PPT课件st

3、ruct BinTreeNode;/ 二叉树中结点typedef struct BinTreeNode * PBinTreeNode; /结点的指针类型struct BinTreeNode DataType info;/ 数据域 PBinTreeNode llink;/ 指向左子结点 PBinTreeNode rlink;/ 指向右子结点 ; 由于递归是二叉树的固有特性，二叉树的许多处理都可以用递归算法来描述，因此，为了运算和参数传递的方便，不再对二叉树进行封装，直接将二叉树定义为指向结点的指针类型：typedef struct BinTreeNode *BinTree;在实际应用中，将二叉树

4、作为参数传递时，可能需要传递二叉树根结点指针的地址（避免被调用函数中修改根节点位置）。因此，为了说明方便，可以引入二叉树类型的指针类型：typedef BinTree *PBinTree;叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件为区分左右指针和线索，需要在每个结点里增加两个标志位ltag和rtag，令：ltag=0，则llink是指针，指向结点的左子结点；ltag =1，则llink是线索，指向结点的对称序的前驱结点；rtag=0，则rlink是指针，指向结点的右子结点；rtag =1，则rlink是线索，指向结点的对称序的后继结点。struc

5、t ThrTreeNode;/ 线索二叉树中的结点 */typedef struct ThrTreeNode * PThrTreeNode; / 指向线索二叉树结点的指针类型struct ThrTreeNode/ 线索二叉树中结点的定义 DataType info;PThrTreeNode llink, rlink;int ltag, rtag;typedef struct ThrTreeNode * ThrTree; / 线索二叉树类型的定义typedef ThrTree * PThrTree; / 线索二叉树类型的指针类型叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件2212) 1

6、 (iiiikkkk2212)2(iiiikkkk叉树与树PPT课件 2 3 5 9 10 7 8 14 12 11 16 叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件 2 3 9 10 5 8 14 12 11 16 7 4 叉树与树PPT课件 3 4 9 10 5 8 14 12 11 16 7 叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件ADT Tree

7、isoperations Tree createEmptyTree (void) 创建一棵空树。 Tree consTree(Node p ,Tree t1, Tree ti) 以P为根，t1 ti 为子树 创建一棵树。 int isNull ( Tree t ) 判断树t是否为空树。 Node root ( Tree t ) 返回树t的根结点。若为空树，则返回一特殊值。 Node parent (Node p ) 返回结点p的父结点。当指定的结点为根时，它没有父结点，返回一个特殊值。 Tree leftChild (Tree t ) 返回树t的长子树。当指定树没有子树时，返回一特殊值。 Tr

8、ee rightSibling (Tree t ) 返回树t的右兄弟树。当指定树没有右兄弟子树时，返回一特殊值。end ADT Tree叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件struct EdgeNode /子表中结点的结构 int nodeposition; /子结点在结点表中的位置 struct EdgeNode *link; / 指向下一个子表中的结点; struct ChiTreeNode /结点表中结点的结构 DataType info; / 结点本身的信息 struct Edg

9、eNode *children; / 本结点子表的头指针 ； struct ChiTree / 树结构 int MAXNUM / 树中最大结点个数 int root; / 根结点的下标 int n; / 实际结点个数 struct ChiTreeNode * nodelist; /结点表 ;typedef struct ChiTree * PChiTree;/指向树的指针叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件叉树与树PPT课件 叉树与树PPT课件叉树与树PPT课件(a) 二叉树 (b) 加连线 (c) 删与右子结点的连线 (d) 调整 叉树与树PPT课件叉树与树PPT课件