二叉树操作

二叉树操作 #include"stdio.h" #include"malloc.h" typedef char datatype; typedef char elemtype; typedef struct BiTNode { datatype data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree Initiate() { BiTree bt; //?õÊ???Á?Ò??Ã?øÍ??ÚµãµÄ?þ?æÊ? if((bt=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return 0; //bt->data='A'; bt->lchild=NULL; bt->rchild=NULL; return bt; } BiTree Create(elemtype x,BiTree lbt,BiTree rbt) { //Éú?ÉÒ??ÃÒÔxΪ?ù?ÚµãµÄÊý?ÝÓòÖµÒÔlbtºÍrbtΪ×óÓÒ×ÓÊ?µÄ?þ?æÊ? BiTree p; if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL; p->data=x; p->lchild=lbt; p->rchild=rbt; return p; } BiTree InsertL(BiTree bt,elemtype x,BiTree parent) { //ÔÚ?þ?æÊ?btÖеÄparentËùÖ??ÚµãºÍÆä×ó×ÓÊ?Ö??ä?åÈëÊý?ÝÔªËØΪxµÄ?Úµã BiTree p; if(parent==NULL) { printf("\n?åÈë?ö?í"); return NULL; } if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL; p->data=x; p->lchild=NULL; p->rchild=NULL; if(parent->lchild==NULL) parent->lchild=p; else { p->lchild=parent->lchild; parent->lchild=p; } return bt; } BiTree InsertR(BiTree bt,elemtype x,BiTree parent) { //ÔÚ?þ?æÊ?btÖеÄparentËùÖ??ÚµãºÍÆäÓÒ×ÓÊ?Ö??ä?åÈëÊý?ÝÔªËØΪxµÄ?Úµã BiTree p; if(parent==NULL) { printf("\n?åÈë?ö?í"); return NULL; } if((p=(BiTNode *)malloc(sizeof(BiTNode)))==NULL) return NULL; p->data=x; p->lchild=NULL; p->rchild=NULL; if(parent->rchild==NULL) parent->rchild=p; else { p->rchild=parent->rchild; parent->rchild=p; } return bt; } BiTree DeleteL(BiTree bt,BiTree parent) { //ÔÚ?þ?æÊ?btÖÐÉ??ý?áµãparentµÄ×ó×ÓÊ? BiTree p; if(parent==NULL||parent->lchild==NULL) { printf("\nÉ??ý?ö?í"); return NULL; } p=parent->lchild; parent->lchild=NULL; free(p);//µ?pΪ?ÇÒ?×Ó?áµãÊ???ÕâÑùÉ??ý?öÊÍ?ÅÁËËùÉ??ý×ÓÊ??ùµÄ?áµãµÄ? Õ?ä //ÈôÒªÉ??ý×ÓÊ??ÖÖ?µÄ?Úµã??ÐèÒªºóÃæ?éÉܵÄ?éÀú?Ù×?À?ʵÏÖ?? return bt; } BiTree DeleteR(BiTree bt,BiTree parent) { //ÔÚ?þ?æÊ?btÖÐÉ??ý?áµãparentµÄÓÒ×ÓÊ? BiTree p; if(parent==NULL||parent->rchild==NULL) { printf("\nÉ??ý?ö?í"); return NULL; } p=parent->rchild; parent->rchild=NULL; free(p); return bt; } void PreOrder(BiTree bt) { //ÏÈÐò?éÀú?þ?æÊ?bt if(bt==NULL)return; if(bt->data) printf("%c ",bt->data); //Visit(bt->data); PreOrder(bt->lchild); PreOrder(bt->rchild ); } void InOrder(BiTree bt) { //ÖÐÐò?éÀú?þ?æÊ?bt if(bt==NULL)return; InOrder(bt->lchild); printf("%c ",bt->data); InOrder(bt->rchild); } void PostOrder(BiTree bt) { //ºóÐò?éÀú?þ?æÊ?bt if(bt==NULL)return; PostOrder(bt->lchild); PostOrder(bt->rchild); printf("%c ",bt->data); } void main() { BiTree bt,x; printf(" A \n" " / \\ \n" " B C \n" " / \\ / \\ \n" " D E F G \n" " / \\ / \n" " H I J \n"); bt=Create('A',NULL,NULL); x=InsertL(bt,'B',bt); x=InsertL(bt,'D',bt->lchild); x=InsertR(bt,'E',bt->lchild); x=InsertL(bt,'H',(bt->lchild)->lchild); x=InsertL(bt,'I',(bt->lchild)->lchild); x=InsertL(bt,'J',(bt->lchild)->rchild); x=InsertR(bt,'C',bt); x=InsertL(bt,'F',bt->rchild); x=InsertR(bt,'D',bt->rchild); PreOrder(x);printf("\n"); InOrder(x);printf("\n"); PostOrder(bt);printf("\n"); }