二叉树的初始化及应用：二叉树的插入，删除，二叉树的前序后序遍历

#include "dStruct.h" //创建新节点 PBTNode createNewNode(char data) { PBTNode new = NULL; new = malloc(sizeof(BTNode)); if(new == NULL) return NULL; new->data = data; new->lchild = NULL; new->rchild = NULL; return new; } //插入左子结点 void insertLeftNode(PBTNode root,char data) { PBTNode new = NULL; if(root == NULL) return ; new = createNewNode(data); if(new == NULL) return ; if(root->lchild == NULL) { root->lchild = new; }else { new->lchild = root->lchild; root->lchild = new; } } //插入右子结点 void insertRightNode(PBTNode root,char data); //前（先）序构造二叉树 PBTNode createBTree(void) { PBTNode proot = NULL; char data; printf("enter your data.\n"); do{ data = getchar(); }while(data == '\n'); if(data == '#'){ printf("create node finish.\n"); return NULL; } proot = createNewNode(data); printf("please input leftchild node\n"); proot->lchild = createBTree(); printf("please input rightchild node\n"); proot->rchild = createBTree(); return proot; } void preOrderTraverse(PBTNode root) { if(root == NULL){ printf("BTree is NULL.\n"); return ; } printf("%c ",root->data); if(root->lchild !=NULL)preOrderTraverse(root->lchild); if(root->rchild !=NULL)preOrderTraverse(root->rchild); } PBTNode searchBTNode(PBTNode root,char data) { if(root == NULL){ printf("BTree is NULL.\n"); return NULL; } if(root->data == data)return root; if(root->lchild != NULL)return searchBTNode(root->lchild,data); if(root->rchild != NULL)return searchBTNode(root->rchild,data); printf("%c is not in BTree.\n",data); return NULL; } PBTNode searchBTFNode(PBTNode root,char data) { PBTNode p; if(root == NULL){ printf("BTree is NULL.\n"); return NULL; } if(root->data == data){ return root; } else{ if((p = searchBTFNode(root->lchild,data)) != NULL)return p; else return searchBTFNode(root->rchild,data); } } void clearBTree(PBTNode *root) { PBTNode p,q; printf("clear-----\n"); if((*root) == NULL) return; p=(*root)->lchild; q=(*root)->rchild; free(*root); (*root) = NULL; clearBTree(&p); clearBTree(&q); } int deleteBTNode(PBTNode *root ,char data) { PBTNode p,pnode;//pnode用来指向深度最深的父结点 int cnt; if(*root == NULL){ printf("BTree is NULL.\n"); return -1; } if((*root)->data == data){ if((*root)->lchild == NULL && (*root)->rchild == NULL){ p = *root; *root = NULL; free(p); return 1; } if((*root)->lchild == NULL || (*root)->rchild == NULL){ p = *root; (*root) = (*root)->lchild == NULL?(*root)->rchild:(*root)->lchild; p->lchild = p->rchild = NULL; free(p); return 1; } if((*root)->lchild != NULL &&(*root)->rchild != NULL){ p = (*root); *root = findDeepestNode(*root,&pnode,&cnt); (*root)->rchild = p->rchild; (*root)->lchild = p->lchild; //将深度最深的叶子结点的父结点指向该结点的指针指向空 if(pnode->lchild != NULL && pnode->lchild == (*root))pnode->lchild = NULL; else if(pnode->rchild ==NULL && pnode->rchild == (*root))pnode->rchild = NULL; p->rchild = p->lchild =NULL; free(p); p = NULL; return 1; } } else{ if(deleteBTNode(&((*root)->lchild),data) == 1) return 1; if(deleteBTNode(&((*root)->rchild),data) == 1) return 1; } return 0 ; } //返回深度最深的叶子结点的地址，并将该结点的父结点的地址存在pnode中 PBTNode findDeepestNode(PBTNode root,PBTNode *pnode,int *cnt){ PBTNode pl,pr,lpnode,rpnode; int lcnt,rcnt; lcnt = rcnt = 0; if(root == NULL)return NULL; *cnt = 1; if(root->lchild == NULL && root->rchild == NULL)return root; if(root->lchild != NULL){ lpnode = root; pl = findDeepestNode(root->lchild,&lpnode,&lcnt); } if(root->rchild != NULL){ rpnode = root; pr = findDeepestNode(root->rchild,&rpnode,&rcnt); } if(lcnt > rcnt){ *cnt += lcnt; *pnode = lpnode; return pl; } else{ *cnt += rcnt; *pnode = rpnode; return pr; } }