twobtree.txt

功能说明： 如果生成二叉树每次都手工输入整数

/*
作者名称： monkeylee
程序名称： 添删查改二叉树
功能说明： 如果生成二叉树每次都手工输入整数，建立二叉树，
   可以进行添加、遍历、查找、删除，如果插入的数和数中的数重复不予插入
创建时间： 2007.11.27
最后修改： 2007.12.1
修改原因： 
*/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

//自引用结构
struct treeNode{
 int data;     //节点值
 struct treeNode *leftPtr; //指向左子树的指针
 struct treeNode *rightPtr; //指向右子树的指针
}; /*结构定义结束*/

typedef struct treeNode TreeNode;
typedef TreeNode * TreeNodePtr;

/*函数原型*/
void insertNode(TreeNodePtr &treePtr,int value);  //插入节点
void inOrder(TreeNodePtr treePtr);     //中序遍历
int  instructions();         //菜单
void search(TreeNodePtr treePtr,int value);   //查找
void deleteNode(TreeNodePtr &treePtr,int value);  //删除

//----------------------------------------------------------------------------------
/*主函数*/
void main(){
 int item;      //要操作的数据
 int choices;     //存储随机制的变量
 TreeNodePtr rootPtr=NULL;  //树在开始的时候为空

 while(choices=instructions()){
  switch(choices){
  case 1:/*插入*/
   printf("输入要插入的整数>>");
   scanf("%d",&item);
   insertNode(rootPtr,item);
   break;

  case 2:/*遍历*/
   printf("中序遍历：");
   inOrder(rootPtr);
   printf("\n");
   break;

  case 3:/*查询*/
   printf("输入要找的数>>");
   scanf("%d",&item);
   search(rootPtr,item);
   break;

  case 4:/*删除*/
   printf("输入要删除的数字>>");
   scanf("%d",&item);
   deleteNode(rootPtr,item);
   break;

  default:/*输入错误*/
   printf("请输入正确的选项!\n");
  } /*结束switch*/
 }

 printf("\n");

} /*结束main函数*/
//----------------------------------------------------------------------------------
int instructions(){
 int choice;
 printf("菜单: 1.插入  2.遍历  3.查找  4.删除  0.退出\n>>");
 scanf("%d",&choice);
  return(choice);
} /*结束instructions*/
//----------------------------------------------------------------------------------
/*将节点插入到树中*/
void insertNode(TreeNodePtr &treePtr,int value){

 //生成新节点，找到一个要连的地方，然后创建新节点newNodePtr
 TreeNodePtr newNodePtr;
 if(newNodePtr=(TreeNodePtr)malloc(sizeof(TreeNode))){
  newNodePtr->data=value;
  newNodePtr->leftPtr=NULL;
  newNodePtr->rightPtr=NULL;
 } /*结束if*/
 else{
  printf("没有分配空间成功!\n");
  exit(0);
 } /*结束else*/
 

 /*如果树为空，直接连接新节点*/
 if(treePtr==NULL){
  treePtr=newNodePtr;
 } /*结束if*/

 /*如果树不为空*/
 else{

  /*要插入的数值小于当前节点终的数值*/
  if(newNodePtr->data<treePtr->data){
   insertNode(treePtr->leftPtr,newNodePtr->data);
  } /*结束if*/

  /*要插入的数值大于当前节点中的数值*/
  else if(newNodePtr->data>treePtr->data){
   insertNode(treePtr->rightPtr,newNodePtr->data);
  } /*结束else if*/


 } /*结束else*/
} /*结束insertNode()函数*/

//----------------------------------------------------------------------------------
/*对树进行中序遍历*/
void inOrder(TreeNodePtr treePtr){
 /*如果树不为空*/
 if(treePtr!=NULL){
  inOrder(treePtr->leftPtr);
  printf("%5d",treePtr->data);
  inOrder(treePtr->rightPtr);
 } /*结束if*/

} /*结束inOrder()函数*/

//----------------------------------------------------------------------------------
/*查找，从头节点开始*/
void search(TreeNodePtr treePtr,int value){
 TreeNodePtr currentPtr=treePtr;
 int n=1; //记录查询次数

 /*寻找*/
 while(currentPtr!=NULL && currentPtr->data!=value){
  printf("%d > ",currentPtr->data);
  if(value<currentPtr->data)
   currentPtr=currentPtr->leftPtr;
  else
   currentPtr=currentPtr->rightPtr;
  n++;
 } 

 if(currentPtr==NULL || currentPtr->data!=value){
  printf("没有找到!\n");
  printf("寻找路径=%d\n",n);
 }
 else if(currentPtr->data==value){
  printf("%d 找到!\n",value);
  printf("寻找路径=%d\n",n);

 }
}

//----------------------------------------------------------------
/*将节点删除*/
void deleteNode(TreeNodePtr &rootPtr,int value)
{
 TreeNodePtr prePtr=rootPtr;  //父节点
 TreeNodePtr currentPtr=rootPtr; //要删除节点
 TreeNodePtr maxPtr=NULL;  //左子树的最大值

 /*寻找要删除节点，由currentPtr指向*/
 while(currentPtr!=NULL && currentPtr->data!=value)
 {
  prePtr=currentPtr;

  //比根节点的值小
  if(value<currentPtr->data)
   currentPtr=currentPtr->leftPtr;

  //比根节点的值大
  else
   currentPtr=currentPtr->rightPtr;
 }/*结束while*/

 //如果找到了,必须说明currentPtr！=NULL，假如NULL也不存在currentPtr->data
 if(currentPtr!=NULL && currentPtr->data==value)
 {

  //1.如果当前节点就是叶子节点
  if(currentPtr->leftPtr==NULL && currentPtr->rightPtr==NULL)
  {
   //如果整个树只有一个节点
   if(currentPtr==rootPtr)
   {
    rootPtr=NULL;
    free(currentPtr);
   }

   else
   {
    //把父节点的所有子树置空
    if(currentPtr==prePtr->leftPtr)
     prePtr->leftPtr=NULL;
    else
     prePtr->rightPtr=NULL;
    free(currentPtr);
   }/*结束else*/

  }/*结束if*/

  //2.如果只有一个右孩子
  else if(currentPtr->leftPtr==NULL && currentPtr->rightPtr!=NULL)
  {
   //如果删除的正好是根节点
   if(currentPtr==rootPtr)
   {   
    rootPtr=currentPtr->rightPtr;
    free(currentPtr);
   }

   //如果要删除的是左孩子
   else if(currentPtr==prePtr->leftPtr)
   {
    prePtr->leftPtr=currentPtr->rightPtr;
    free(currentPtr);
   }/*结束if*/

   //删除的是右孩子
   else if(currentPtr==prePtr->rightPtr)
   {
    prePtr->rightPtr=currentPtr->rightPtr;
    free(currentPtr);
   }/*结束else*/

  }/*结束else if*/

  //3.如果只有一个左孩子
  else if(currentPtr->leftPtr!=NULL && currentPtr->rightPtr==NULL)
  {
   if(currentPtr==rootPtr)
   {
    rootPtr=currentPtr->leftPtr;
    free(currentPtr);
   }
   //如果删除的是左孩子
   else if(currentPtr==prePtr->leftPtr)
   {
    prePtr->leftPtr=currentPtr->leftPtr;
    free(currentPtr);
   }
   //如果要删除的是左孩子
   else if(currentPtr==prePtr->rightPtr)
   {
    prePtr->rightPtr=currentPtr->leftPtr;
    free(currentPtr);
   }/*借书if*/

  }/*结束else if*/

  //4.如果有两孩子

  else if(currentPtr->leftPtr!=NULL && currentPtr->rightPtr!=NULL)
  {
   maxPtr=currentPtr->leftPtr;

   while(maxPtr->rightPtr!=NULL)
   {
    maxPtr=maxPtr->rightPtr;
   }
   //如果删除的是根节点
   if(currentPtr==rootPtr)
   {
    rootPtr=currentPtr->leftPtr;
    maxPtr->rightPtr=currentPtr->rightPtr;
    free(currentPtr);
   }
   //如果删除的是左子树
   if(currentPtr==prePtr->leftPtr)
   {
    prePtr->leftPtr=currentPtr->leftPtr;
    maxPtr->rightPtr=currentPtr->rightPtr;
    free(currentPtr);
   }/*结束if*/

   else if(currentPtr==prePtr->rightPtr)
   {
    prePtr->rightPtr=currentPtr->leftPtr;
    maxPtr->rightPtr=currentPtr->rightPtr;
    free(currentPtr);

   }/*结束else*/

  }/*结束else*/

 }/*结束if*/
 
 else
 {
  printf("没有找到!\n");
 }
 
}/*结束deleteNode函数*/