北京房山网站建设景安安装wordpress

北京房山网站建设,景安安装wordpress,网络logo设计,手机上的网站在搜索一定量的资料后发现有两种构建方式#xff0c;其中一种是设置parent指针#xff0c;从而能在将节点穿插到最下面后进行回溯#xff0c;只实际上是最朴素的做法。我们采用第二种做法#xff0c;就是将AVL树的构建用递归回溯的方法进行#xff0c;顺序是这样#xff…在搜索一定量的资料后发现有两种构建方式其中一种是设置parent指针从而能在将节点穿插到最下面后进行回溯只实际上是最朴素的做法。我们采用第二种做法就是将AVL树的构建用递归回溯的方法进行顺序是这样首先插入节点接着检查这个节点是否满足balance不满足则进行旋转之后再更新节点的高度不管有没有旋转 这个递归实际上就是不断向下直到递归到了最底层然后将节点插入到最底层之后就会有一个回溯回溯过程刚好也能满足求高度的条件下面的节点的高度都已经求出来了因此能够顺便把沿途每个节点的高度都求出来但是我们每次并不急着求高度而是先判断符不符合要求并且进行旋转。因为如果我们先去求高度的话得到的点旋转后会变就会使得操作无效。这个过程之中我们便可以将沿路上的不满足平衡的节点全部都给弄平衡了。注意旋转中里面需要更新高度因为有的节点高度会变。还有很关键的一点AVL树某个节点为根变换时这个位置的根节点变了但其高度不变这可以避免退化出现平衡因子绝对值大于2的情况#include stdio.h #include stdlib.h #include string.h typedef struct AVLNode { char data; int height; struct AVLNode *lchild , *rchild; }AVLNode; int Height(AVLNode* node) { if(node NULL) return 0; else return node - height; } int Max(int a , int b) { if(a b) return a; else return b; } AVLNode* LL(AVLNode** T) { AVLNode* son (*T) - lchild; (*T) - lchild son - rchild; son - rchild (*T); (*T) - height Max(Height((*T) - lchild) , Height((*T) - rchild)) 1; son - height Max(Height(son - lchild) , Height(son - rchild)) 1; return son; } AVLNode* RR(AVLNode** T) { AVLNode* son (*T) - rchild; (*T) - rchild son - lchild; son - lchild (*T); (*T) - height Max(Height((*T) - lchild) , Height((*T) - rchild)) 1; son - height Max(Height(son - lchild) , Height(son - rchild)) 1; return son; } AVLNode* RL(AVLNode** T) { AVLNode* son (*T) - rchild - lchild; (*T) - rchild LL(((*T) - rchild)); (*T) RR(T); return son; } AVLNode* LR(AVLNode** T) { AVLNode* son (*T) - lchild - rchild; (*T) - lchild RR(((*T) - lchild)); (*T) LL(T); return son; } void Insert(AVLNode** T , char x) { if((*T) NULL) { AVLNode* p (AVLNode*) malloc (sizeof(AVLNode)); p - data x; p - lchild NULL; p - rchild NULL; p - height 1; (*T) p; return; } else { if(x (*T) - data) { Insert(((*T) - lchild) , x); if(Height((*T) - lchild) - Height(((*T) - rchild)) 1) { if((*T) - lchild - data x) (*T) LR(T); else (*T) LL(T); } } else if(x (*T) - data) { Insert(((*T) - rchild) , x); if(Height((*T) - lchild) - Height(((*T) - rchild)) -1) { if((*T) - rchild - data x) (*T) RR(T); else (*T) RL(T); } } (*T) - height Max(Height((*T) - lchild) , Height((*T) - rchild)) 1; } } void Print(AVLNode* T , int layer) { if(T ! NULL) { Print(T - rchild, layer 1); for(int i 0 ; i layer ; i ) printf( ); printf(%c\n , T - data); Print(T - lchild , layer 1); } } void Pre_print(AVLNode* T) { if(T ! NULL) { printf(%c , T - data); Pre_print(T - lchild); Pre_print(T - rchild); } } void Mid_print(AVLNode* T) { if(T ! NULL) { Mid_print(T - lchild); printf(%c , T - data); Mid_print(T - rchild); } } void Post_print(AVLNode* T) { if(T ! NULL) { Post_print(T - lchild); Post_print(T - rchild); printf(%c , T - data); } } int main() { char a[100]; scanf(%s , a); AVLNode* T NULL; for(int i 0 ; i strlen(a) ; i ) { Insert(T , a[i]); } printf(Preorder: ); Pre_print(T); printf(\n); printf(Inorder: ); Mid_print(T); printf(\n); printf(Postorder: ); Post_print(T); printf(\n); printf(Tree:\n); Print(T , 0); return 0; }