二叉树基本操作C序.doc

输入如下二叉树测试C语言源程序。程序运行中创建二叉树时输入结点编号顺序为： AA↙ A B↙ *↙ C↙ D↙ EBN*↙ E BN *↙ *↙ E↙ FC*↙ F C F↙ G↙ H↙ *↙ GD*↙ G D K↙ *↙ *↙ *↙ KH K H 源程序如下： #include stdio.h #include malloc.h #include ctype.h #include string.h #define NULL 0 //定义空指针 #define MAXCHARLENGTH 100 //定义结点编号字符串最大长度 typedef struct LinkNode{ //二叉树中的结点数据结构，结点编号为字符串 char data[MAXCHARLENGTH]; struct LinkNode *lchild,*rchild; }Node; /*先序创建二叉树 *输入单个“*”号表示无此结点 */ Node *CreatBinTree(Node *p){ char ch[MAXCHARLENGTH]=exit,tuichu[MAXCHARLENGTH]=exit,nullnode[MAXCHARLENGTH]=*; printf(请输入二叉树中结点对应的字符（输入“*”表示无此结点）：); scanf(%s,ch); if(stricmp(ch,nullnode)==0){ p=NULL; } else{ p=(Node*)malloc(sizeof(Node)); memmove(p-data,ch,MAXCHARLENGTH); p-lchild=CreatBinTree(p-lchild); p-rchild=CreatBinTree(p-rchild); } return p; } /*确定二叉树的深度 *变量valdeepth保存左子树和右子树中的较大深度 */ int getdeepth(Node *tree){ int valdeepth=0,leftdeepth=0,rightdeepth=0; if(tree==NULL){ //若指针为空，则返回 valdeepth=0; } else{ leftdeepth=getdeepth(tree-lchild); rightdeepth=getdeepth(tree-rchild); valdeepth=1+(leftdeepthrightdeepth?leftdeepth:rightdeepth); } return valdeepth; } /*确定二叉树中结点ch的层数 *字符串ch存储查找结点编号，不区分大小写 *传址参数result保存结点ch的层数，result值为1时表示在相应子树中没找到该结点 *传值参数lev为中间变量，初始值为1，记录层数 */ void level(Node *tree,char *ch,int result,int lev){ if(tree==NULL){ result=-1; //指针为空，表示已达叶子结点，result赋值为-1，表示没找到回朔递归 return; } else if(stricmp(tree-data,ch)==0){ result=lev; //在二叉树中找到了结点ch，把中间变量lev中保存的到结点ch的层数存到result中后回朔递归 return; } else{ level(tree-lchild,ch,result,lev+1); //若子树根结点不是查找的结点ch则递归调用函数level（）在左子树中查找 if(result==-1){ level(tree-rchild,ch,result,lev+1); //若子树根结点不是查找的结点ch则递归调用函数level（）在右子树中查找 } } } /*先序遍历二叉树 *传址参数num存储二叉树中结点个数 */ void PreOrder(Node *tree,int num){ if(tree==NULL){ return; } else{ printf(%s ,tree-data); num++; PreOrder(tree-lchild,num); PreOrder(tree-rchild,num); } } /*后序遍历二叉树 *传址参数num存储二叉树中结点个数 */ void PostOrder(Node *