AVL添加

平衡二叉樹，是一種二叉排序樹，其中每個結點的左子樹和右子樹的高度差至多等于1。
它是一種高度平衡的二叉排序樹。現二叉平衡樹結點定義如下：

typedef struct node {int val;struct node *left;struct node *right;struct node *parent;int height; } node_t;

請實現平衡二叉樹的插入算法：

向根為 root 的平衡二叉樹插入新元素 val，成功后返回新平衡二叉樹根結點

node_t *avl_insert(node_t *root, int val);#include <stdlib.h> #include <stdio.h> #include "avl.h"int get_height(node_t *p){if(!p)return 0;elsereturn p->height; }

示例代碼如下:

一定要超級仔細, 不然絕對后悔!

node_t* avl_insert(node_t *root, int val){ //首先清晰字母定義; //val新插入結點元素值,height高度!!! //定義查找過程中出現的距離插入結點最近的平衡因子不為零的結點A //定義A的孩子結點為B,需要旋轉的結點 //定義插入節點為s,s的值為val //平衡因子:左子樹減去右子樹深度 node_t *s, *A, *B, *C, *p, *fp;//依次:插入點, 失衡點(也可能是旋轉點),旋轉點,旋轉點(也可能是插入點=s),動點,跟蹤點int i, k;//平衡因子 s = (node_t *)malloc(sizeof(node_t));if(!s) return NULL;s->val = val;s->left = s->parent = s->right = NULL;s->height = 1;//類似于指針跟蹤技術,p為動指針,A為跟蹤指針 A = root; A->parent = NULL;p = root; p->parent = NULL;//找出A if(!p)root = s;else{while(p){//先找出最近的A->height!=0的結點, 就是最后的失衡點i = get_height(p->left) - get_height(p->right); if(i){A = p;A->parent = p->parent;}//fp跟蹤p,因為下一步p會往下移動,p最終指向s的那一層 fp = p;if(val < p->val)p = p->left;elsep = p->right;}//p最終指向NULL就推出循環 } //插入, 此時fp是p的前一個結點,p指向空 if(val < fp->val)fp->left = s;elsefp->right = s;//確定旋轉結點B,修改A的平衡因子if(val < A->val)B = A->left;elseB = A->right;A->height++;//修改路徑B到s的高度, B在A的下一層 p = B; // p最終指向s, 之前指向的是s這一層,但是是空while(p != s){p->height++;if(val < p->val)p = p->left; elsep = p->right; }//最終s的高度沒有++的 //調整完高度就修改結點和指針, 首先需要判斷失衡類型//分為LL,LR,RR,RL//結點A,B平衡因子在修改指針的過程中會變化,但是路徑上的結點不會//指針修改包括s結點指針和原來雙親結點指針 i = get_height(A->left) - get_height(A->right);k = get_height(B->left) - get_height(B->right); if(i == 2 && k == 1){//LL//B作為旋轉結點//先改結點指針, 此時s插入在B的左子樹下, 原來可以認為B左右子樹,A右子樹均為空A->left = B->right;B->right = A;//考慮原來A結點的指針,改成B后相應的指針也要改變,下面同理if(A->parent == NULL)root = B;else if(A->parent->left == A)A->parent->left = B;elseA->parent->right = B; }else if(i == -2 && k == -1){//RRA->right = B->left;B->left = A;if(A->parent == NULL)root = B;else if(A->parent->left == A)A->parent->left = B;elseA->parent->right = B; }else if(i == 2 && k == -1){//LR//此時認為C的左右子樹空,B逆時針旋轉,A順時針旋轉, s插入C的左子樹或者右子樹 //如果C結點也是空,也就是說B右子樹空,那么直接插入C=s為B右子樹,此時A右子樹也是空的 C = B->right;B->right = C->left;A->left = C->right;C->left = B;C->right = A;if(A->parent == NULL)root = C;else if(A->parent->left == A)A->parent->left = C;elseA->parent->right = C;}else if(i == -2 && k == 1){//RL //和LR一樣,畫圖來看就好C = B->left;A->right = C->left;B->left = C->right;C->left = A;C->right = B;if(A->parent == NULL)root = C;else if(A->parent->left == A)A->parent->left = C;elseA->parent->right = C;}return root; }

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的AVL添加平衡二叉树，是一种二叉排序树，其中每个结点的左子树和右子树的高度差至多等于1。-icoding-数据结构-C-typedef struct node{ int val；的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。