niushao 2020-02-20
//数据类型 struct node{ int v, height; node *lchild, *rchild; }; //新建一个结点 node* newNode(int v){ node* Node = new node; Node->v = v; Node->height = 1; Node->lchild = Node->rchild = NULL; return Node; } //获取结点root的高度 int getHeight(node* root){ if(root == NULL) return 0; return root->height; } //计算平衡因子 int getBalanceFactor(node* root){ return getHeight(root->lchild) - getHeight(root->rchild); } //结点root所在子树的height等于其左子树的height与右子树的height的较大值加1 void updateHeight(node* root){ root->height = max(getHeight(root->lchild), getHeight(root->rchild); }
void search(node* root, int x){ if(root == NULL){ printf("search failed\n"); return; } if(x == root->data){ printf("%d\n". root->data); }else if(x < root->data){ search(root->lchild, x); }else{ search(root->rchild, x); } }
void L(node* &root){ node* temp = root->rchild; root->rchild = temp->lchild;//步骤一 temp->lchild = root;//步骤二 updateHeight(root);//更新结点高度 updateHeight(temp); root = temp;//步骤三 }
void R(node* &root){ node* temp = root->lchild; root->lchild = temp->rchild; temp->rchild = root; updateHeight(root); updateHeight(temp); root = temp; }
//不考虑平衡的二叉排序树的插入操作 void insert(node* &root, int v){ if(root == NULL){ root = newNode(v); return; } if(v < root->v){ insert(root->lchild, v); }else{ insert(root->rchild, v); } } void insert(node* &root, int v){ if(root == NULL){ root = newNode(v); return; } if(v < root->v){ insert(root->lchild, v); updateHeight(root); if(getBalanceFactor(root) == 2){ if(getBalanceFactor(root->lchild) == 1){ R(root); }else if(getBalanceFactor(root->lchild) == -1){ L(root->lchild); R(root); } }else{ insert(root->rchild, v); updateHeight(root); if(getBalanceFactor(root) == -2){ if(getBalanceFactor(root-rchild) == -1){ L(root); }else if(getBalanceFactor(root-rchild) == 1){ R(root->rchild); L(root); } } } } }
node* Create(int data[], int n){ node* root = NULL; for(int i = 0; i < n; i++){ insert(root, data[i]); } return root; }