btreebalance.cpp

随机生成用户要求个数的整数

/*
程序作者： monkeylee
程序名称： 二叉树平衡因子
程序功能： 随机生成用户要求个数的整数，生成二叉树（无重复），
   可以进行生成、遍历、查找二叉树，而且进行动态的查找，
   如果没有找到节点就把这个值接到树上
   能够显示节点的产生顺序、平衡因子（失败），节点值
创建时间： 2007.12.01
最后更新： 2007.12.03
*/

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

//自引用结构
struct treeNode
{
 int data;     //节点值
 int balance;    //平衡因子
 int order;     //生成顺序
 struct treeNode *left;  //指向左子树的指针
 struct treeNode *right;  //指向右子树的指针
 struct treeNode *father;
}; /*结构定义END */

typedef struct treeNode TreeNode;
typedef TreeNode * TreeNodePtr;

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

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

 while(choices=instructions())
 {
  switch(choices)
  {
  case 1:
   rootPtr=NULL;
   printf("输入要生成二叉树的节点数>>");
   scanf("%d",&n);
   if(n<=0)
   {
    printf("输入节点数必须大于等于1\n");
    break;
   }
   srand(time(NULL));
   for(i=1;i<=n;i++)
   {
    item=rand()%(10*n);
    insertNode(rootPtr,item,i);
   }/*END for*/
   break;


  case 2:
   printf("中序遍历:\n");
   if(rootPtr==NULL)
    break;
   inOrder(rootPtr);
   printf("\n");
   break;
  case 3:
   printf("输入要找的数>>");
   scanf("%d",&item);
   search(rootPtr,item,i);
   i++;
   break;

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

 printf("\n");

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

 //生成新节点，找到一个要连的地方
 TreeNodePtr currentPtr=rootPtr;
 TreeNodePtr newPtr;
 TreeNodePtr prePtr=rootPtr;
 if(newPtr=(TreeNodePtr)malloc(sizeof(TreeNode)))
 {
  newPtr->data=value;
  newPtr->balance=0;
  newPtr->order=order;
  newPtr->left=NULL;
  newPtr->right=NULL;
  newPtr->father=NULL;
 }/*END if*/

 else
 {
  printf("没有分配空间成功!\n");
  exit(0);
 }/*END else*/
 

 /*如果树为空*/
 if(rootPtr==NULL)
 {
  rootPtr=newPtr;
 }/*END if*/

 /*如果树不为空*/
 else
 {
  //找到了要插入的位置由currentPtr来指向
  while(currentPtr!=NULL && prePtr->data!=value)
  {
   prePtr=currentPtr;
   if(value<currentPtr->data)
   {
    currentPtr=currentPtr->left;
   }
   else 
   {
    currentPtr=currentPtr->right;
   }
  }
  //-----------------------------------------------------------------左节点
  //如果最后插入到前一个节点的左节点
  if(value<prePtr->data)
  {
   //把新节点连上
   prePtr->left=newPtr;
   newPtr->father=prePtr;

   //如果插入节点有个兄弟节点，则只需改变新节点的父节点的平衡因子，其它不用管
   if(prePtr->right!=NULL)
   {
     prePtr->balance++;
   }

   /*如果插入节点没有兄弟节点，修改新节点父节点的平衡因子，再往上面追溯
   这里分两种情况，所追溯的节点没有兄弟节点则肯定修改平衡因子，但是如果
   所追溯的节点有个兄弟节点，又要分两种情况讨论，如果所追溯的是它父节点的
   左孩子，那么如果它的父节点的平衡因子改变之后仍然小于等于0，则追溯停止
   如果大于0则还要继续往上追溯，直到找到一个节点又两个孩子，如果从左节点上去的
   则如果平衡因子大于0继续否则停止，如果是从右节点上去的，如果其父节点平衡因子大于等于
   0则停止否则继续追溯*/

   //插入节点没有兄弟节点
   else
   {
    currentPtr=newPtr->father; //初始化currentPtr指向新插入节点的父节点
    prePtr=newPtr;    //初始化prePtr指向新节点

    //一直向上追溯，一直到父节点才停
    while(currentPtr->father!=NULL)
    {

     //如果currentPtr所指向的节点有两个孩子，则有可能停了下来
     if(currentPtr->left!=NULL && currentPtr->right !=NULL)
     {
      //如果从左路上去
      if(currentPtr->left==prePtr)
      {
       currentPtr->balance++;
       if(currentPtr->balance<=0)
        break;
      }

      //如果从右路上去
      else
      {
       currentPtr->balance--;
       if(currentPtr->balance>=0)
        break;
       
      }
      currentPtr=currentPtr->father; //向上移动
      prePtr=prePtr->father;   //向上移动
     }
     //如果所指向的节点currentPtr所指向的节点只有一个孩子则改变了平衡因子继续
     else
     {
      if(currentPtr->left==prePtr)
       currentPtr->balance++;
      else
       currentPtr->balance--;
      
      currentPtr=currentPtr->father; //向上移动
      prePtr=prePtr->father;   //向上移动
     }

    }/*END  while*/


    //处理currentPtr指到了根节点的情况
    if(currentPtr->father==NULL)
    {
     if(currentPtr->left==prePtr)
      currentPtr->balance++;
     else 
      currentPtr->balance--;
    }

   }/*END  else*/

  }/*END  else*/

 //-----------------------------------------------------------------右节点
  //如果插入的节点在前一个节点的右节点上
  else if(value>prePtr->data)
  {
   //连接新节点
   prePtr->right=newPtr;
   newPtr->father=prePtr;

   //如果在一个非叶子节点上插入，则只改变父节点的平衡因子
   if(prePtr->left!=NULL )
   {
     prePtr->balance--;
   }

   //如果在一个叶子节点上插入，
   else
   {
    currentPtr=newPtr->father; //初始化currentPtr
    prePtr=newPtr;    //初始化prePtr

    while(currentPtr->father!=NULL)
    {
     //如果currentPtr有两个节点
     if(currentPtr->left!=NULL && currentPtr->right !=NULL)
     {
      if(currentPtr->left==prePtr)
      {
       currentPtr->balance++;
       if(currentPtr->balance<=0)
        break;
      }
      else
      {
       currentPtr->balance--;
       if(currentPtr->balance>=0)
        break;
       
      }
      prePtr=currentPtr;
      currentPtr=currentPtr->father;
     }
     //currentPtr节点只有一个节点
     else
     {
      if(currentPtr->left==prePtr)
       currentPtr->balance++;
      else
       currentPtr->balance--;
      prePtr=currentPtr;
      currentPtr=currentPtr->father;
     }

    }/*END  while*/
    if(currentPtr->father==NULL)
    {
     if(currentPtr->left==prePtr)
      currentPtr->balance++;
     else 
      currentPtr->balance--;
    }

   }/*END else*/

  }/*END else if*/

 }/*END else*/
}/*END insertNode()函数*/


//----------------------------------------------------------------------------------

/*对树进行中序遍历*/
void inOrder(TreeNodePtr rootPtr){
 /*如果树不为空*/
 if(rootPtr!=NULL){
  inOrder(rootPtr->left);
  printf("[生成顺序=%-3d] [节点值=%-5d] [平衡因子=%-3d]\n",rootPtr->order,rootPtr->data,rootPtr->balance);
  inOrder(rootPtr->right);
 }/*END if*/

}/*END inOrder()函数*/

//----------------------------------------------------------------------------------
/*查找从头节点一直到查找值过程*/
void search(TreeNodePtr &rootPtr,int value,int i){
 TreeNodePtr prePtr=rootPtr;
 TreeNodePtr currentPtr=rootPtr;
 TreeNodePtr newPtr;
 int n=1;
 while(currentPtr!=NULL && currentPtr->data!=value){
  printf("%d > ",currentPtr->data);
  prePtr=currentPtr;
  if(value<currentPtr->data)
   currentPtr=currentPtr->left;
  else
   currentPtr=currentPtr->right;
  n++;
 }/*寻找*/

 //如果没有找到节点
 if(currentPtr==NULL){
  printf("没有找到,将这个值插入...\n");
  insertNode(rootPtr,value,i);
 }
}