二叉排序树吗_二叉排序树的查找

二叉排序树的创建 　　#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(“这里执行了！！！！！ 　　”); *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(” 　　”); printf(“中序序列为：”); in_traversal(root); printf(” 　　”); destory_tree(&root);//释放资源 return 0; }