先序线索化以及遍历.rar

// 先序线索化.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" typedef struct BiThrNode { char data; struct BiThrNode *lchild,*rchild; int LTag,RTag; }Btree; Btree *T,*P,*pre; Btree *CreateBiTree(Btree *T)//按先序序列先序建立二叉树 { char ch; scanf("%c",&ch); if (ch==' ') T=NULL; else { T=(Btree *)malloc(sizeof(BiThrNode)); T->data=ch; T->lchild=CreateBiTree(T->lchild); T->rchild=CreateBiTree(T->rchild); } return (T); } Btree *PreThreading(Btree *P)//先序的线索化 { if (P) { if (P->lchild) {P->LTag=0;} if (!P->lchild) {P->LTag=1;P->lchild=pre;} if (P->rchild) {P->RTag=0;} if (!P->rchild) P->RTag=1; if (pre&&pre->RTag==1) {pre->rchild=P;} pre=P; if (P->LTag==0) PreThreading(P->lchild); if (P->RTag==0) PreThreading(P->rchild); } return (P); } void preorder(Btree *p)//遍历先序线索二叉树 { printf("%c",p->data); while (p->rchild) { if (p->LTag==0) {p=p->lchild;} else p=p->rchild; printf("%c",p->data); } } main() { Btree *tree1;Btree *tree2;Btree *tree3; tree1=NULL;tree2=NULL;tree3=NULL; printf("请输入树中的元素（输入的必须是一个满二叉树，以空格表示空树）："); tree2=CreateBiTree(tree1); tree3=PreThreading(tree2); printf("先序线索化以后的先序遍历如下："); preorder(tree3); printf("\n"); }