第5章二叉树与树ppt课件

kikkiiimM010122ADT BinTree isoperations BinTree createEmptyBinTree(void)创建一棵空的二叉树。创建一棵空的二叉树。BinTree consBinTree(BinTreeNode root,BinTree left,BinTree right)返回一棵二叉树，其根结点是返回一棵二叉树，其根结点是root，左右二叉树分别为，左右二叉树分别为left和和right。int isNull(BinTree t)判断二叉树判断二叉树t是否为空。是否为空。BinTreeNode root(BinTree t)返回二叉树返回二叉树t的根结点。若为空二叉树，则返回一特殊值。的根结点。若为空二叉树，则返回一特殊值。acbd先根次序周游：void preOrder(BinTree t)中根次序周游：void inOrder(BinTree t)后根次序周游：void postOrder(BinTree t)注意是抽象算法，需要根据二叉树的实现方式进行修改。在数组溢出时，通过程序扩充空间。struct BinTreeNode;/二叉树中结点typedef struct BinTreeNode *PBinTreeNode;/结点的指针类型struct BinTreeNode DataType info;/数据域 PBinTreeNode llink;/指向左子结点 PBinTreeNode rlink;/指向右子结点;由于递归是二叉树的固有特性，二叉树的许多处理都可以用递归算法来描述，因而，为了运算和参数传递的方便，不再对二叉树进行封装，直接将二叉树定义为指向结点的指针类型：typedef struct BinTreeNode *BinTree;在实际应用中，将二叉树作为参数传递时，可能需要传递二叉树根结点指针的地址避免被调用函数中修改根节点位置）。因而，为了说明方便，可以引入二叉树类型的指针类型：typedef BinTree *PBinTree;为区分左右指针和线索，需要在每个结点里增加两个标志位ltag和rtag，令：ltag=0，则llink是指针，指向结点的左子结点；ltag=1，则llink是线索，指向结点的对称序的前驱结点；rtag=0，则rlink是指针，指向结点的右子结点；rtag=1，则rlink是线索，指向结点的对称序的后继结点。struct ThrTreeNode;/线索二叉树中的结点*/typedef struct ThrTreeNode*PThrTreeNode;/指向线索二叉树结点的指针类型struct ThrTreeNode/线索二叉树中结点的定义 DataType info;PThrTreeNode llink,rlink;int ltag,rtag;typedef struct ThrTreeNode*ThrTree;/线索二叉树类型的定义typedef ThrTree*PThrTree;/线索二叉树类型的指针类型根堆。本节主要讨论小根堆。根堆。本节主要讨论小根堆。2212)1(iiiikkkk2212)2(iiiikkkk 2 3 5 9 10 7 8 14 12 11 16 n删除S中的最小元素。nend ADT PriorityQueue 2 3 9 10 5 8 14 12 11 16 7 4 3 4 9 10 5 8 14 12 11 16 7 nstruct HtNode *ht;/存放2*m-1个结点的数组n;ntypedef struct HtTree *PHtTree;/哈夫曼树类型的指针类型ADT Tree 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的长子树。当指定树没有子树时，返回一特殊值。的长子树。当指定树没有子树时，返回一特殊值。Tree rightSibling(Tree t)返回树返回树t的右兄弟树。当指定树没有右兄弟子树时，返回一特殊值。的右兄弟树。当指定树没有右兄弟子树时，返回一特殊值。end ADT Treen程序实现递程序实现递归）：归）：void postOrder(Tree t)n程序实现非递归）：void levelOrder(Tree t)ntypedef struct ParTree *PParTree;/树类型的指针类型struct EdgeNode /子表中结点的结构 int nodeposition;/子结点在结点表中的位置 struct EdgeNode *link;/指向下一个子表中的结点;struct ChiTreeNode /结点表中结点的结构 DataType info;/结点本身的信息 struct EdgeNode *children;/本结点子表的头指针；struct ChiTree /树结构 int MAXNUM /树中最大结点个数 int root;/根结点的下标 int n;/实际结点个数 struct ChiTreeNode *nodelist;/结点表;typedef struct ChiTree*PChiTree;/指向树的指针n;ntypedef struct CSNode*CSTree;/树类型定义，。树林F(R)，其中树T1的根为r，r的子树为F(L)。(a)二叉树 (b)加连线 (c)删与右子结点的连线 (d)调整