二叉树建立与遍历（c++描述）

#include "stdafx.h" #include "bstree.h" #include"Crtdbg.h" #include<stdio.h> #include<malloc.h> #define MAXSIZE 50 FILE*fp; /*创建搜索树*/ void bstree::CreateTree() { char c; while((c=getchar())!=stopkey) { putchar(c); InsertNode(c,root); } } /*删除搜索树中的节点*/ void bstree::DeleteNode(const char key,bstnode*&rootnode) { //bstnode*newnode=new bstnode; //newnode=SearchTree(key,rootnode); //if(newnode->lchild==NULL&&newnode->rchild==NULL) //{ // delete newnode; //} //else if(newnode->lchild==NULL) //{ //} } /*插入节点到搜索树中*/ void bstree::InsertNode(char c,bstnode*&rootnode) { bstnode*newnode; if(rootnode==NULL) { rootnode=new bstnode(c); } else { if(rootnode->data>c) { InsertNode(c,rootnode->lchild); } else if(rootnode->data<c) { InsertNode(c,rootnode->rchild); } else { return; } } } /*搜索树*/ bstnode*bstree::SearchTree(const char key,bstnode*&rootnode) { static int i=0; if(rootnode==NULL) { return NULL; } if(key>rootnode->data) { i++; SearchTree(key,rootnode->rchild); } else if(key<rootnode->data) { i++; SearchTree(key,rootnode->lchild); } else { printf("search %d times\n",i); return rootnode; } //printf("search %d times,can't find\n",i); return NULL; } /*遍历树*/ void bstree::PrintAll(bstnode*&rootnode) { if(rootnode!=NULL) { printf("%c{",rootnode->getdata()); if(rootnode->lchild) { PrintAll(rootnode->lchild); } else { printf(" "); } if(rootnode->rchild) { PrintAll(rootnode->rchild); } else { printf(" "); } printf("}"); } } /*求最小*/ char bstree::Min(bstnode*&rootnode) { if(rootnode==NULL) { return 0; } if(rootnode->lchild==NULL) { return rootnode->data; } return Min(rootnode->lchild); } int _tmain() { int i; char c; bstree*bst=new bstree; printf("start create tree:\n"); bst->CreateTree(); printf("the tree is:\n"); bst->PrintAll(bst->GetRoot()); printf("search key:\n"); scanf("%c",&c); scanf("%c",&c); bst->SearchTree(c,bst->GetRoot()); c=bst->Min(bst->GetRoot()); printf("the min is:%c\n",c); while(c=getchar()!='#'); return 0; }