中序线索化二叉树出错
求指教,中序线索化二叉树后,二叉树中左子树指向的前驱和右子树指向的后继的指针还为空,比如按先序遍历输入二叉树AB##CD##E##,#为空结点。void MidThreadTree(ThreadTree T,ThreadTree pre)中那个地主有问题,求分析程序代码:
#include <stdio.h> #include <stdlib.h> typedef enum _PointerTag{ Link, //Link=0指针 Thread //Thread线索 }PointerTag; typedef struct _ThreadNode{ char elem; PointerTag ltag,rtag; struct _ThreadNode *lchild,*rchild; }ThreadNode,*ThreadTree; /* 创建二叉树 */ void CreateThreadTree(ThreadTree *T) { char ch; ch = getchar(); if(ch == '#')*T = NULL; else { *T = (ThreadNode *)malloc(sizeof(ThreadNode)); printf("0x%x\r\n",*T); (*T)->elem = ch; CreateThreadTree(&((*T)->lchild)); CreateThreadTree(&((*T)->rchild)); } } /* 先序遍历二叉树 */ void PreThreadTreeOrder(ThreadTree T) { if(T) { printf("%3c",T->elem); PreThreadTreeOrder(T->lchild); PreThreadTreeOrder(T->rchild); } } /* 中序遍历二叉树 */ void MidThreadTreeOrder(ThreadTree T) { if(T) { MidThreadTreeOrder(T->lchild); printf("%3c",T->elem); MidThreadTreeOrder(T->rchild); } } /* 后序遍历二叉树 */ void PostThreadTreeOrder(ThreadTree T) { if(T) { PostThreadTreeOrder(T->lchild); PostThreadTreeOrder(T->rchild); printf("%3c",T->elem); } } /* 中序线索化二叉树 */ void MidThreadTree(ThreadTree T,ThreadTree pre) { if(T) { //printf("pre = 0x%x\r\n",pre); MidThreadTree(T->lchild,pre); if(T->lchild == NULL) { T->ltag = Thread; T->lchild = pre; } else T->ltag = Link; if(T->rchild == NULL)T->rtag = Thread; else T->rtag = Link; if(pre) { if(pre->lchild == NULL)pre->ltag = Thread; else pre->ltag = Link; if(pre->rchild == NULL)pre->rtag = Thread; else pre->rtag = Link; if(pre && pre->rtag == Thread)pre->rchild = T; } pre = T; MidThreadTree(T->rchild,pre); } } /* 在中序线索化二叉树中寻找结点的前驱 */ ThreadTree MidFindPreElem(ThreadTree T) { ThreadTree pre; pre = T->lchild; if(T->ltag == Thread)return pre; else { while(pre->rtag == Link) { pre = pre->rchild; } } return pre; } /* 在中序线索化二叉树中寻找结点的后继 */ ThreadTree MidFindNextElem(ThreadTree T) { ThreadTree next; next = T->rchild; if(T->rtag == Thread)return next; else { while(next->ltag == Link) { next = next->lchild; } } return next; } /* 遍历中序线索化二叉树 */ void MidThreadTreeTraverse(ThreadTree T) { ThreadTree p; if(T) { p = T; while(p->ltag == Thread)p = p->lchild; while(p) { printf("%3c\r\n",p->elem); printf("0x%x",p); p = MidFindNextElem(p); printf("\t0x%x\r\n",p); } } } /* 寻找中序线索化二叉树中的某个结点 */ ThreadTree MidFindThreadTreeElem(ThreadTree T,char elem) { ThreadTree p; if(T) { p = T; while(p->ltag == Thread)p = p->lchild; while(p && p->elem != elem) { p = MidFindNextElem(p); } } return p; } void OperateThreadTree(void) { ThreadTree T,p,pre=NULL; printf("按先序次序输入二叉树的结点(结点为字符,字符'#'表示空树):\r\n"); CreateThreadTree(&T); printf("先序遍历二叉树的结点: \r\n"); PreThreadTreeOrder(T); printf("\r\n"); printf("中序遍历二叉树的结点: \r\n"); MidThreadTreeOrder(T); printf("\r\n"); printf("后序遍历二叉树的结点: \r\n"); PostThreadTreeOrder(T); printf("\r\n"); p = T; printf("AAAAAAAAAAAAAAAAAA\r\n"); printf("pre = 0x%x\r\n",pre); printf("0x%x\r\n",T); printf("0x%x\r\n",T->lchild); printf("0x%x\r\n",T->lchild->lchild); MidThreadTree(T,pre); printf("\r\n\r\n"); printf("BBBBBBBBBBBBBBBBBB\r\n"); printf("pre = 0x%x\r\n",pre); printf("0x%x\r\n",T); printf("0x%x\r\n",T->lchild); printf("0x%x\r\n",T->lchild->lchild); printf("中序线索二叉树的遍历:\r\n"); MidThreadTreeTraverse(T); printf("\r\n"); } int main(void) { OperateThreadTree(); return NULL; }