线索二叉树的遍历应用

线索二叉树的遍历，就是在已经建立后的线索二叉树中，根据线索查找结点的前驱和后继。利用在线索二叉树中查找结点的前驱和后继的思想，遍历线索二叉树。#include <stdio.h> #include <stdlib.h> #include <malloc.h> #define MAXSIZE 100 typedef char ElemType; typedef enum {Link,/*指向孩子结点*/Thread/*指向前驱或后继*/ } PointerTag; typedef struct Node {ElemType data;struct Node *lchild;struct Node *rchild;PointerTag ltag,rtag; }*BitThrTree,BitThrNode;BitThrTree pre; void CreateBitTree2(BitThrTree *T,char str[]);//创建搜索二叉树 void InThreading(BitThrTree p);//中序线索化二叉树 int InOrderThreading(BitThrTree *Thrt,BitThrTree T);//通过中序遍历二叉树T，使T中序线索化。Thrt是指向头结点的指针 int InOrderTraverse(BitThrTree T,int (*visit)(BitThrTree e));//中序遍历线索二叉树 int Print(BitThrTree T);//打印二叉树的结点和线索标志 BitThrNode* FindPoint(BitThrTree T,ElemType e);//在线索二叉树中查找结点为e的指针 BitThrNode* InOrderPre(BitThrNode *p);//中序前驱 BitThrNode* InOrderPost(BitThrNode *p);//中序后继 void DestroyBitTree(BitThrTree *T);//销毁二叉树#include "LinkBiTree.h"void CreateBitTree2(BitThrTree *T,char str[])//创建搜索二叉树 {char ch;BitThrTree stack[MAXSIZE];int top = -1;int flag,k;BitThrNode *p;*T = NULL,k = 0;ch = str[k];while(ch != '\0'){switch(ch){case '(':stack[++top] = p;flag = 1;break;case ')':top–;break;case ',':flag = 2;break;default:p = (BitThrTree)malloc(sizeof(BitThrNode));p->data = ch;p->lchild = NULL;p->rchild = NULL;if(*T == NULL){*T = p;}else{switch(flag){case 1:stack[top]->lchild = p;break;case 2:stack[top]->rchild = p;break;}if(stack[top]->lchild){stack[top]->ltag = Link;}if(stack[top]->rchild){stack[top]->rtag = Link;}}}ch = str[++k];} } void InThreading(BitThrTree p)//中序线索化二叉树 {if(p)//左子树线索化{InThreading(p->lchild);if(!p->lchild)//前驱线索化{p->ltag = Thread;p->lchild = pre;}if(!pre->rchild)//后继线索化{pre->rtag = Thread;pre->rchild = p;}pre = p;InThreading(p->rchild);//右子树线索化} } int InOrderThreading(BitThrTree *Thrt,BitThrTree T)//通过中序遍历二叉树T，使T中序线索化。Thrt是指向头结点的指针 {if(!(*Thrt = (BitThrTree)malloc(sizeof(BitThrNode)))){exit(-1);//为头结点分配单元}(*Thrt)->ltag = Link;//修改前驱线索标志(*Thrt)->rtag = Thread;//修改后继线索标志(*Thrt)->rchild = *Thrt;//将头结点的rchild指针指向自己if(!T)//如果二叉树为空，则将lchild指针指向自己{(*Thrt)->lchild = *Thrt;}else{(*Thrt)->lchild = T;//将头结点的左指针指向根结点pre = *Thrt;//将pre指向已经线索化的结点InThreading(T);//中序遍历进行中序线索化/*将最后一个结点线索化*/pre->rchild = *Thrt;//将最后一个结点的右指针指向头结点pre->rtag = Thread;//修改最后一个结点的rtag标志域(*Thrt)->rchild = pre;//将头结点的rchild指针指向最后一个结点}return 1; } int InOrderTraverse(BitThrTree T,int (*visit)(BitThrTree e))//中序遍历线索二叉树 {BitThrTree p;p = T->lchild ;//p指向根结点while(p != T)//空树或遍历结束时，p == T{while(p->ltag == Link){p = p->lchild ;}if(!visit(p))//打印{return 0;}while(p->rtag == Thread && p->rchild != T)//访问后继结点{p = p->rchild ;visit(p);}p = p->rchild ;}return 1; } int Print(BitThrTree T)//打印二叉树的结点和线索标志 {static int k = 1;printf("%2d\t%s\t %2c\t %s\t\n",k++,T->ltag == 0 ? "Link":"Thread",T->data ,T->rtag == 1 ? "Thread":"Link");return 1; } BitThrNode* FindPoint(BitThrTree T,ElemType e)//在线索二叉树中查找结点为e的指针 {BitThrTree p;p = T->lchild ;while(p != T){while(p->ltag == Link){p = p->lchild ;}if(p->data == e){return p;}while(p->rtag == Thread && p->rchild != T){p = p->rchild ;if(p->data == e){return p;}}p = p->rchild ;}return NULL; } BitThrNode* InOrderPre(BitThrNode *p)//中序前驱 {if(p->ltag == Thread)//如果p的标志域ltag为线索，则p的左子树结点为前驱{return p->lchild ;}else{pre = p->lchild ;//查找p的左孩子的最右下端结点while(pre->rtag == Link)//右子树非空时，沿右链往下查找{pre = pre->rchild ;}return pre;//pre就是最右下端结点} } BitThrNode* InOrderPost(BitThrNode *p)//中序后继 {if(p->rtag == Thread)//如果p的标志域rtag为线索，，则p的右子树结点为后驱{return p->rchild ;}else{pre = p->rchild ;//查找p的右孩子的最左下端结点while(pre->ltag == Link)//左子树非空时，沿左链往下查找{pre = pre->lchild ;}return pre;//pre就是最左下端结点} } void DestroyBitTree(BitThrTree *T)//销毁二叉树 {if(*T){if(!(*T)->lchild){DestroyBitTree(&((*T)->lchild));}if(!(*T)->rchild){DestroyBitTree(&((*T)->rchild));}free(*T);*T = NULL;} }#include "LinkBiTree.h"int main(void) {BitThrTree T,Thrt;BitThrNode *p,*pre,*post;CreateBitTree2(&T,"(A(B(,D(G)),C(E(,H),F)))");printf("线索二叉树的输出序列：\n");InOrderThreading(&Thrt,T);printf("序列前驱标志结点后继标志\n");InOrderTraverse(Thrt,Print);p = FindPoint(Thrt,'D');pre = InOrderPre(p);printf("元素D的中序直接前驱元素是：%c\n",pre->data);post = InOrderPost(p);printf("元素D的中序直接后驱元素是：%c\n",post->data);p = FindPoint(Thrt,'E');pre = InOrderPre(p);printf("元素E的中序直接前驱元素是：%c\n",pre->data);post = InOrderPost(p);printf("元素E的中序直接后驱元素是：%c\n",post->data);DestroyBitTree(&Thrt);return 0; }

走过的路成为背后的风景，不能回头不能停留，若此刻停留，

相关文章：

你感兴趣的文章：

标签云：