61树的类型定义

61树的类型定义内容摘要：

iTree( Tlchild)。 //构造左子树 CreateBiTree( Trchild)。 //构造右子树 } return(OK)。 } // CreateBiTree 统计二叉树中叶子结点的个数 算法基本思想 : 先序 (或中序或后序 )遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此， 需在遍历算法中增添一个“计数”的参数 ，并将算法中“ 访问结点 ”的操作改为： 若是叶子，则计数器增 1。 void CountLeaf (BiTree T, intamp。 count){ if ( T ) { if ((!Tlchild)amp。 amp。 (!Trchild)) count++。 // 对叶子结点计数 CountLeaf( Tlchild, count)。 CountLeaf( Trchild, count)。 } // if } // CountLeaf 求二叉树的深度 (后序遍历 ) 算法基本思想 : 从二叉树深度的定义可知， 二叉树的深度应为其左、右子树深度的最大值加 1。 由此， 需先分别求得左、右子树的深度， 算法中 “访问结点”的操作为： 求得左、右子树深度的最大值，然后加 1。 首先分析 二叉树的深度 和它的 左 、 右子树深度 之间的关系。 int Depth (BiTree T ){ // 返回二叉树的深度 if ( !T ) depthval = 0。 else { depthLeft = Depth( Tlchild )。 depthRight= Depth( Trchild )。 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 } return depthval。 } 线索二叉树  何谓线索二叉树。  线索链表的遍历算法  如何建立线索链表。 一、何谓线索二叉树。 遍历二叉树的结果是， 求得结点的一个线性序列。 A B C D E F G H K 例如 : 先序 序列 : A B C D E F G H K 中序 序列 : B D C A H G K F E 后序 序列 : D C B H K G F E A 指向该线性序列中的“前驱”和 “后继” 的 指针 ，称作“ 线索 ” 与其相应的二叉树，称作 “ 线索二叉树 ” 包含 “线索” 的存储结构，称作 “ 线索链表 ” A B C D E F G H K ^ D ^ C ^ ^ B E ^ 对 线索链表 中结点的约定： 在二叉链表的结点中 增加两个标志域 ， 并作如下规定： 若该结点的左子树不空， 则 Lchild域的指针指向其左子树， 且左标志域的值为“ 指针 Link”或 0； 否则， Lchild域的指针指向其“前驱”， 且左标志的值为“ 线索 Thread”或 1。 若该结点的右子树不空， 则 rchild域的指针指向其右子树， 且右标志域的值为 “ 指针 Link”或 0； 否则， rchild域的指针指向其“后继”， 且右标志的值为“ 线索 Thread”或 1。 如此定义的二叉树的存储结构称作“ 线索链表 ”。 线索链表的结点结构 ltag和 rtag是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前驱或后继的线索。 lchild LTag data RTag rchild 0 l c h i l dL T ag =1 l c h i l d0 r c h i l dRT ag =1 r c h i l d域指向结点的左孩子域指向结点的前驱域指向结点的右孩子域指向结点的后继typedef struct BiThrNod { TElemType data。 struct BiThrNode *lchild, *rchild。 // 左右指针 PointerThr LTag, RTag。 // 左右标志 } BiThrNode, *BiThrTree。 线索链表 的类型描述： typedef enum { Link, Thread } PointerThr。 // Link==0:指针， Thread==1:线索 ABCDEFGHI 例如： 二、线索链表的遍历算法 : for ( p = firstNode(T)。 p。 p = Succ(p) ) Visit (p)。 由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。 例如 : 对中序线索化链表的遍历算法 ※ 中序遍历的第一个结点。 ※ 在中序线索化链表中结点的后继。 左子树上处于 “最左下” （没有左子树）的结点。 若 无右子树， 则为 后继线索 所指结点； 否则为 对其 右子树 进行中序 遍历 时访问的 第一个结点。 void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) { p = Tlchild。 // p指向根结点 while (p != T) { // 空树或遍历结束时， p==T while (pLTag==Link) p = plchild。 // 第 一个结点 Visit(pdata)。 while (pRTag==Thread amp。 amp。 prchild!=T) { p = prchild。 Visit(pdata)。 } // 访问后继结点 p = prchild。 // p进至其右子树根 } } // InOrderTraverse_Thr 在中序遍历过程中修改结点的 左、右指针域，以保存当前访问结 点的“前驱”和“后继”信息。 遍历过 程中，附设指针 pre, 并始终保持指 针 pre指向当前访问的、指针 p所指 结点的前驱。 三、如何建立线索链表。 void InThreading(BiThrTree p) { if (p) { // 对以 p为根的非空二叉树进行线索化 InThreading(plchild)。 // 左子树线索化 if (!plchild) // 建前驱线索 { pLTag = Thread。 plchild = pre。 } if (!prerchild) // 建后继线索 { preRTag = Thread。 prerchild = p。 } pre = p。 // 保持 pre 指向 p 的前驱 InThreading(prchild)。 // 右子树线索化 } // if } // InThreading Status InOrderThreading(BiThrTree amp。 Thrt, BiThrTree T) { // 构建中序线索链表 if (!(Thrt = (BiThrTree)malloc(sizeof( BiThrNode)))) exit (OVERFLOW)。 ThrtLTag = Link。 ThrtRTag =Thread。 Thrtrchild = Thrt。 if (!T) Thrtlchild = Thrt。 else { Thrtlchild = T。 pre = Thrt。 InThreading(T)。 prerchild = Thrt。 preRTag = Thread。 Thrtrchild = pre。 } return OK。 } // InOrderThreading 树和森林 的表示方法 树的三种存储结构 一、 双亲表示法 二、 孩子链表表示法 三、 树的二叉链表 (孩子 兄弟） 存储表示法 A B C D E F G 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 r=0 n=7 data parent 一、双亲表示法 : typedef struct PTNode { Elem data。 int parent。 // 双亲位置域 } PTNod。