二叉排序树的创建(4)

还添加了两个函数，分别用于计算每棵子树的深度和判断以某个节点为根的子树是否平衡

/**
 * 计算每个子树的深度
 * */
int compute_deep(PBNode root)
{
         if(root == NULL)
                  return 0;//空树的深度为0
         int deep = 1;
 
         int left_deep = compute_deep(root->l_tree);
         int rigth_deep = compute_deep(root->r_tree);
         root->deep = deep + (left_deep > rigth_deep ? left_deep : rigth_deep);
 
         return root->deep;
}
/**
 * 判断以node节点为根的子树是否平衡
 * */
bool is_balance(PBNode node)
{
         if(node->l_tree == NULL)
         {
                  if(node->r_tree == NULL)
                          return true;
                  return node->r_tree->deep == 2 ? false : true;
         }
         if(node->r_tree == NULL)
         {
                  return node->l_tree->deep == 2 ? false : true;
         }
        
         return abs(node->l_tree->deep - node->r_tree->deep) == 2 ? false : true;
}

为了判断是哪种类型，需要知道是右子树高还是左子树高，因此也加入了一个用于判断左右子树谁高的函数

//表示哪棵子树高
enum which_high{
         LEFT_HIGH,
         RIGHT_HIGH
};
/**
 *判断node节点的哪棵子树更高
 **/
enum which_high get_higher(PBNode node)
{
 
         if(node->l_tree == NULL )
                  return RIGHT_HIGH;
         if(node->r_tree == NULL)
                  return LEFT_HIGH;
         if(node->l_tree->deep > node->r_tree->deep)
                  return LEFT_HIGH;
         return RIGHT_HIGH;
 
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
 
typedef struct b_node{
         int value;//节点的值
         int deep;//树的深度
         struct b_node *l_tree;//左子树
         struct b_node *r_tree;//右子树
         struct b_node *parent;//父亲节点

} BNode,*PBNode;
/**
 * 分配一个节点
 * */
PBNode allocate_node()
{
         PBNode node = NULL;
         node = (PBNode)malloc(sizeof(struct b_node));
         if(node == NULL)
                  return NULL;
         memset(node,0,sizeof(struct b_node));
         return node;
}
/**
 * 设置一个节点的值
 * */
void set_value(PBNode node,int value)
{
         if(node == NULL)   
                  return;
         node->value = value;
         node->deep = -1;
         node->l_tree = NULL;
         node->r_tree = NULL;
         node->parent = NULL;
}
/**
 * 计算每个子树的深度
 * */
int compute_deep(PBNode root)
{
         if(root == NULL)
                  return 0;//空树的深度为0
         int deep = 1;
 
         int left_deep = compute_deep(root->l_tree);
         int rigth_deep = compute_deep(root->r_tree);
         root->deep = deep + (left_deep > rigth_deep ? left_deep : rigth_deep);
 
         return root->deep;
}
/**
 * 判断以node节点为根的子树是否平衡
 * */
bool is_balance(PBNode node)
{
         if(node->l_tree == NULL)
         {
                  if(node->r_tree == NULL)
                          return true;
                  return node->r_tree->deep == 2 ? false : true;
         }
         if(node->r_tree == NULL)
         {
                  return node->l_tree->deep == 2 ? false : true;
         }
        
         return abs(node->l_tree->deep - node->r_tree->deep) == 2 ? false : true;
}
 
//表示最小非平衡树可能的四种状态
enum unbalance_type {
         TYPE_LL,
         TYPE_LR,
         TYPE_RL,
         TYPE_RR
};
/**
 * deal_unbalance调用的函数
 * 根据最小非平衡树的类型进行调整,使其平衡
 * unbalance为最小非平衡树的树根
 * type为最小非平衡树的类型
 * root为整棵树的树根,因为这个过程中,整棵树的树根可能都在随时变换
 * */
void adjust(PBNode *root,PBNode unbalance,enum unbalance_type type)
{
         int t = type;
         PBNode small;
         PBNode middle;
         PBNode big;
         switch (t)
         {
                  case TYPE_LL:
                          {
                                   //确定small、middle、big三个节点

                                   big = unbalance;
                                   middle = unbalance->l_tree;
                                   small = unbalance->l_tree->l_tree;
                                  
                                   //分配middle节点的孩子，给small和big

                                   big->l_tree = middle->r_tree;
                                  
                                   //将small和big作为midlle的左子和右子

                                   middle->r_tree = big;
                                   break;
                          }
                  case TYPE_LR:
                          {
                                   //确定small、middle、big三个节点

                                   big = unbalance;
                                   small = unbalance->l_tree;
                                   middle = unbalance->l_tree->r_tree;
 
                                   //分配middle节点的孩子，给small和big

                                   small->r_tree = middle->l_tree;
                                   big->l_tree = middle->r_tree;
 
                                   //将small和big作为midlle的左子和右子

                                   middle->l_tree = small;
                                   middle->r_tree = big;
                                   break;
                          }
                  case TYPE_RL:
                          {
                                   //确定small、middle、big三个节点

                                   small = unbalance;
                                   big = unbalance->r_tree;
                                   middle = unbalance->r_tree->l_tree;
 
                                   //分配middle节点的孩子，给small和big

                                   small->r_tree = middle->l_tree;
                                   big->l_tree = middle->r_tree;
                                  
                                   //将small和big作为midlle的左子和右子

                                   middle->l_tree = small;
                                   middle->r_tree = big;
                                   break;
                          }
                  case TYPE_RR:
                          {
                                   //确定small、middle、big三个节点

                                   small =unbalance;
                                   middle  = unbalance->r_tree;
                                   big = unbalance->r_tree->r_tree;
                                  
                                   //分配middle节点的孩子，给small和big

                                   small->r_tree = middle->l_tree;
                                  
                                   //将small和big作为midlle的左子和右子

                                   middle->l_tree = small;
                                   break;
                          }
 
         }
         //将最小非平衡子树的父亲节点指向middle（也就是将middle，调整后的子树的根结点）
         if(unbalance->parent == NULL)     //说明最小非平衡树的根节点就是整棵树的根结点

         {
                  printf("这里执行了！！！！！\n");
                  *root = middle;
         }
         else if(unbalance->parent->l_tree == unbalance)//根是父亲的左孩子

         {
                  unbalance->parent->l_tree = middle;
 
         }
         else if(unbalance->parent->r_tree == unbalance)//根是父亲的右孩子

         {
                  unbalance->parent->r_tree = middle;
         }
 
         //更改small、middle、big的父亲节点

         middle->parent = unbalance->parent;
         big->parent = middle;
         small->parent = middle;
 
}
//表示哪棵子树高
enum which_high{
         LEFT_HIGH,
         RIGHT_HIGH
};
 
 
/**
 *判断node节点的哪棵子树更高
 **/
enum which_high get_higher(PBNode node)
{
 
         if(node->l_tree == NULL )
                  return RIGHT_HIGH;
         if(node->r_tree == NULL)
                  return LEFT_HIGH;
         if(node->l_tree->deep > node->r_tree->deep)
                  return LEFT_HIGH;
         return RIGHT_HIGH;
 
}
/**
 * 处理不平衡问题,其中value为刚刚添加的节点的值
 * */
void deal_unbalance(PBNode *root,int value)
{
         PBNode p = *root;
         PBNode unbalance = NULL;
         while(p!= NULL && value != p->value)
         {
                  //判断是否平衡
                  if(!is_balance(p))    
                  {
                          unbalance = p;//注意这里不能break，因为要找最小的非平衡子树，如果一旦找到非平衡子树就调出，则可能不是最小的

                  }
                  if(value > p->value)
                  {
                          p = p->r_tree;
                  }
                  else if(value < p->value)
                  {
                          p = p->l_tree;
                  }
         }
         if(unbalance != NULL)//说明有不平衡存在

         {
                  //调用处理不平衡问题的函数
                  if(get_higher(unbalance) == LEFT_HIGH)//左节点较高

                  {
                          if(value < unbalance->l_tree->value)//说明为LL型

                          {
                                   adjust(root,unbalance,TYPE_LL);
 
                          }
                          else if(value > unbalance->l_tree->value)//说明为LR类型

                          {
                                   adjust(root,unbalance,TYPE_LR);
                          }
                  }
                  else //右节点较高

                  {
                          if(value < unbalance->r_tree->value)//说明为RL型

                          {
                                   adjust(root,unbalance,TYPE_RL);
                          }
                          else if(value > unbalance->r_tree->value)//说明为RR型

                          {
                                   adjust(root,unbalance,TYPE_RR);
                          }
                  }
         }
}
/**
 * 向二叉查找树中添加一个节点，使得新的二叉树依然时二叉查找树
 * 非递归方法实现
 * */
void insert_node(PBNode *root,int value)
{
         if(*root == NULL)
         {
                  *root = allocate_node();
                  set_value(*root,value);
         }
         else
         {
                  PBNode p = *root;
                  PBNode pp = NULL;//保存父亲节点
                  bool is_left = false;
                  while(p != NULL)
                  {
                          pp = p;
                          is_left = false;
                         
                          if(value < p->value)
                          {
                                   is_left = true;
                                   p = p->l_tree;
                          }
                          else if(value > p->value)
                          {
                                   p = p->r_tree;
                          }
                  }
                  PBNode node = allocate_node();
                  set_value(node,value);
                  node->parent = pp;//填父亲节点
                  if(is_left)
                  {
                          pp->l_tree = node;
                  }
                  else
                  {
                          pp->r_tree = node;
                  }
                 
 
         }
         //计算子树深度

         compute_deep(*root);
         //处理不平衡问题

         deal_unbalance(root,value);
         //处理完不平衡问题后还用重新计算子树深度

         compute_deep(*root);
 
 
}
 
/**
 * 插入法创建bst
 * */
void create_bst(PBNode *root,int value[],int len)
{
         int i = 0;
         for(;i < len;i++)
         {
                  insert_node(root,value[i]);
         }
}
/**
 * 先序遍历二叉树
 * */
void pre_traversal(PBNode root)
{
         if(root == NULL)
                  return;
         printf("%d  ",root->value);
         pre_traversal(root->l_tree);
         pre_traversal(root->r_tree);
}
/**
 * 中序遍历二叉树
 * */
void in_traversal(PBNode root)
{
         if(root == NULL)
                  return;
         in_traversal(root->l_tree);
         printf("%d  ",root->value);
         in_traversal(root->r_tree);
}
 
/**
 * 查找值为vlue的节点
 * */
PBNode get_node(PBNode root,int value)
{
         if(root == NULL)
                  return NULL;
         PBNode node = NULL;
         if(value < root->value)
         {
                  node = get_node(root->l_tree,value);
         }
         else if(value > root->value)
         {
                  node = get_node(root->r_tree,value);
         }
         else
         {
                  node = root;
         }
         return node;
}
/**
 * 找到最小非平衡子树
 * */
 
 
void free_node(PBNode *node);
 
/**
 * 释放节点空间
 * */
void free_node(PBNode *node)
{
         if(*node == NULL)
                  return;
         free(*node);
         *node = NULL;
}
/**
 * 销毁二叉树
 * */
void destory_tree(PBNode *root)
{
         if(*root == NULL)
                  return;
         destory_tree(&((*root)->l_tree));
         destory_tree(&((*root)->r_tree));
         free_node(root);
}
 
int main()
{
         int value[] = {7,4,6,3,12,5,1,14,10,8,9};
         int len = 11;
         PBNode root = NULL;
         create_bst(&root,value,len);
        
         printf("先序序列为：");
         pre_traversal(root);
         printf("\n");
         printf("中序序列为：");
         in_traversal(root);
         printf("\n");
 
         destory_tree(&root);//释放资源
         return 0;
}

链接： 密码：k752

如果对你有用，请赞一下吧~~

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-108009-4.html