C语言数据结构之线索二叉树及其遍历(二,二叉树,线索,编程语言)

#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 typedef char ElemType; typedef int Status; /* 定义枚举类型，其值只能是Link和Thread * Link表示的该指针指示的是孩子 * Thread表示的是还指针指示的是前驱或者是后缀 * */ typedef enum { Link,Thread }PointerTag; typedef struct ThrBiTrNode{ ElemType data; struct ThrBiTrNode *lchild, *rchild; PointerTag rTag, lTag; }ThrBiTrNode, *ThrBiTree; ThrBiTree Pre; Status InitThreadBinaryTree(ThrBiTree* T){ *T = NULL; return OK; } //先序建立二叉树,lchild和rchild都是指示做孩子和右孩子，所以lTag和rTag为Link Status ThreadBinaryTree_PreOrderInput(ThrBiTree* T){ ElemType c; scanf("%c", &c); if( ' ' == c ){ *T = NULL; } else{ *T = (ThrBiTrNode*)malloc(sizeof(ThrBiTrNode)); if( !*T ){ return ERROR; } (*T)->data = c; (*T)->lTag = Link; (*T)->rTag = Link; ThreadBinaryTree_PreOrderInput(&(*T)->lchild); ThreadBinaryTree_PreOrderInput(&(*T)->rchild); } return OK; } //<<中序遍历>>对二叉树进行<<线索化>>，但是没有提供Pre的初始值，只是给出了 //中间的过程，递归的思想和思考方式。 //1 线索化左子树 //2 对双亲节点处理//递归中的base //3 线索化右子树 Status InOrderThread(ThrBiTree T){ if( T != NULL ){ InOrderThread(T->lchild); //线索化左子树 //对双亲节点进行线索化处理 if( T->lchild == NULL ){ //如果左孩子为空，则将lchild作为索引 //Pre指向刚刚访问的节点 T->lTag = Thread; T->lchild = Pre; } if( Pre->rchild == NULL ){ //直到现在才知道Pre的后缀是T，所以 //要对Pre进行设置,如果Pre的rchild为空 //则将Pre的rchild设置为后缀，指向T Pre->rTag = Thread; Pre->rchild = T; } Pre = T; //标记当前的节点称为刚刚访问过的节点 //Pre最后会指向树的中序遍历的最后的 //一个节点 InOrderThread(T->rchild); //线索化右子树 } return OK; } //创建中序线索二叉树,为上个函数提供Pre Status CreateInOrderThreadBinaryTree(ThrBiTree T, ThrBiTree* headOfTree){ *headOfTree = (ThrBiTrNode*)malloc(sizeof(struct ThrBiTrNode)); if( !headOfTree ) return ERROR; (*headOfTree)->lTag = Link; //将要指向T (*headOfTree)->rTag = Thread; //将头节点的rchild用于索引 (*headOfTree)->rchild = *headOfTree; //指向自身 if( T == NULL ){ (*headOfTree)->lchild = *headOfTree; //若T为空树，则头节点的lchild //指向自身 } else{ (*headOfTree)->lchild = T; Pre = *headOfTree; //赋值了全局变量Pre InOrderThread(T); //中序线索化 //printf("\n%c\n",Pre->data); //执行完InOrderThread之后Pre指向最后 //一个节点 Pre->rTag = Thread; Pre->rchild = *headOfTree; //(*headOfTree)->rchild = Pre; } return OK; } //对中序线索化后的线索二叉树使用<<非递归>>的代码进行中序遍历 //并且原来的递归形式的代码在这里是不再可以进行遍历。 // 如果二叉树没有被线索化，也可以使用<<非递归>>的代码进行遍 // 历的，但是那就需要借助于<<栈>>,但是在线索化之后，对线索 // 化的二叉树进行<<非递归>>的遍历就不再需要栈的辅助。 Status visit(ElemType c){ printf("%c ", c); return OK; } Status InOrderTeaverse_NoRecursion(ThrBiTree T, ThrBiTree headOfTree){ //headOfTree是T的头节点的指针，headOfTree->lchild = T; while( T != headOfTree ){ while( T->lTag == Link ){ //找到树(子树)的最左节点 //用while接替if// //用if理解while// T = T->lchild; } visit(T->data); while( T->rTag == Thread && T->rchild != headOfTree){ //这个while和下面的T=T->rchild //可用ifelse语句理解。 //if(rchild是线索 && 不是最后一个节点) //else(rchild不是线索)-->走到右孩子 //也就是代码T=T->rchild T = T->rchild; visit(T->data); } T = T->rchild; } return OK; } //求中序线索二叉树中中序序列下的第一个节点 ThrBiTrNode* SeekFirstNode_InOrderThrBiTree(ThrBiTree T){ if( T != NULL ){ while( T->lTag == Link ){ T = T->lchild; } return T; } return ERROR; } //求中序线索二叉树中节点P在中序序列下的下一个节点 ThrBiTrNode* GetNextNode(ThrBiTrNode* CurrentP){ if( CurrentP->rTag == Link ){ //有右孩子的时候，那么下一个就是以 //右孩子为root的树的最左下角元素。 //即seekFirstNode的返回值。 return SeekFirstNode_InOrderThrBiTree(CurrentP->rchild); } else{ //没有右孩子，则rchild指向后缀 return CurrentP->rchild; } } //使用上面两个函数，SeekFirstNode_InOrderThrBiTree和GetNextNode来实现对 //中序先做二叉树的遍历 Status InOrderTraverse_NoRecursion_Method(ThrBiTree T, ThrBiTree head){ for( T = SeekFirstNode_InOrderThrBiTree(T) ; T != head ; T = GetNextNode(T) ) visit(T->data); return OK; } //test /* ShowThread函数的目的是想在将T中序线索化之后，使用函数InOrderTraverse * 函数中序遍历，输出一下节点中的信息以检验线索化，但是失败。原因是：在 * 线索化之后，空指针域都被应用，所有InOrderTraverse函数中的if( T )是满 * 足不了的，故失败。 Status ShowThread(ThrBiTree C){ printf("%d %d %d %d\n",(C->lchild)->data,(C->rchild)->data,C->lTag,C->rTag); printf("%d %d\n",C->lTag,C->rTag); return OK; * */ //中序遍历二叉树 Status InOrderTraverse(ThrBiTree T){ if( T ){ InOrderTraverse(T->lchild); visit(T->data); InOrderTraverse(T->rchild); } return OK; } int main(){ ThrBiTree T,R,Head = NULL; InitThreadBinaryTree(&T); printf("Please Input Binary Tree By PreOrder\n "); ThreadBinaryTree_PreOrderInput(&T); printf(" InOrder Traverse before Thread with Recursion\n"); InOrderTraverse(T); printf("\n"); CreateInOrderThreadBinaryTree(T,&Head); printf(" InOrder Traverse after Thread with no-Recursion\n"); InOrderTeaverse_NoRecursion(T,Head); printf("\n"); printf("The root is %c \n", T->data); //不能够通过指针形参的值改变指针实参的值 //或者说，对指针形参的改变不会作用到指针 //实参上。 ThrBiTrNode *firstOfInOrder = NULL,*secondOfInOrder = NULL; if( SeekFirstNode_InOrderThrBiTree(T) != ERROR ){ firstOfInOrder = SeekFirstNode_InOrderThrBiTree(T); printf("the value of First Node of InOrderThreadBinaryTree is %c\n", firstOfInOrder->data); } secondOfInOrder = GetNextNode(firstOfInOrder); printf("the value of Node after D is: %c \n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after B is: %c \n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after E is: %c \n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after A is: %c \n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after C is: %c \n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after G is: %c \n", secondOfInOrder->data); secondOfInOrder = GetNextNode(secondOfInOrder); printf("the value of Node after root is: %c \n", secondOfInOrder->data); printf(" InOrder Traverse after Thread with no-Recursion Method_2\n"); InOrderTraverse_NoRecursion_Method(T,Head); return 0; }