徐汇苏州网站建设,制作一个网站怎么做的,做微商网站,利津网站定制一、定义二叉树结点结构体
/*** 定义平衡二叉树结点
*/
struct avlbinarytree
{ //数据域NodeData* data;///树高int h;struct avlbinarytree* left;struct avlbinarytree* right;
};
typedef struct avlbinarytree AVLNode;
二、声明函数的操作
/*** 创建结点
*/
AV…一、定义二叉树结点结构体
/*** 定义平衡二叉树结点
*/
struct avlbinarytree
{ //数据域NodeData* data;///树高int h;struct avlbinarytree* left;struct avlbinarytree* right;
};
typedef struct avlbinarytree AVLNode;
二、声明函数的操作
/*** 创建结点
*/
AVLNode* create_avlbinarytree_node(NodeData* data);/**** 计算树高度
*/
int get_avltree_h(AVLNode* childRoot);/*** 添加结点
*/
void insert_avlbinarytree_node(AVLNode** tree,NodeData* data);/*** 平衡操作
*/
void do_avltree_roate(AVLNode** root);/*** 前序遍历
*/
void per_order_avlbinarytree(AVLNode* root);/*** LL型左孩子的左子树添加删除引起的失衡* 5 3* . . 平衡操作 . .* 3 6 -------------- 2 5 * . . . . .* 2 4 1 4 6* .* 1* * 平衡操作左子树整体右旋将根节点左孩子提到根节点原根结点变成新根节点的右孩子,新根结点的原右孩子变成原根节点的左孩子*
*/
void ll_roate_avl(AVLNode** root);/*** RR型右孩子的右子树添加删除引起的失衡* 2 4* . . . .* 1 4 ------- 2 6 * . . . . . * 3 6 1 3 5* . * 5*
*/void rr_roate_avl(AVLNode** root);
/*** LR型左孩子的右子树添加删除引起的失衡* 5 5 3* . . . . . .* 2 6 3 6 2 5 * . . ------ . . ------- . . .* . .* 4 1*平衡操作左子树先做一次RR左旋再做一次LL右旋
*/
void lr_roate_avl(AVLNode** root);/*** RL型右孩子的左子树添加删除引起的失衡* 2 2 4* . . . . . .* 1 5 ------- 1 4 ---- 2 5* . . . . . . .* 4 6 3 5 1 3 6* . .* 3 6* *平衡操作 先将右子树做一次LL右旋在做一次RR左旋
*/
void rl_roate_avl(AVLNode** root);三、平衡二叉树操作函数定义 /*** 创建结点*/
AVLNode *create_avlbinarytree_node(NodeData *data)
{AVLNode *node malloc(sizeof(AVLNode *));if (node NULL){perror(创建AVLNode结点失败);return NULL;}node-data malloc(sizeof(NodeData *));if (node-data NULL){perror(AVLNode数据域分配内存空间失败);return NULL;}*(node-data) *data;node-h 1;node-left NULL;node-right NULL;return node;
}
/*** 获取树高*/
int get_avltree_h(AVLNode *childRoot)
{if (childRoot NULL){return 0;}int l get_avltree_h(childRoot-left) 1;int r get_avltree_h(childRoot-right) 1;return l r ? l : r;
}void insert_avlbinarytree_node(AVLNode **tree, NodeData *data)
{if (*tree NULL){AVLNode *newNode create_avlbinarytree_node(data);*tree newNode;return;}/// 左子树if (*data *((*tree)-data)){insert_avlbinarytree_node(((*tree)-left), data);}//右子树if (*data *((*tree)-data)){insert_avlbinarytree_node(((*tree)-right), data);}
}void do_avltree_roate(AVLNode** root)
{int lh get_avltree_h((*root)-left);int rh get_avltree_h((*root)-right);/// 左子树高于右子树造成的不平衡if(lh-rh1){int llh get_avltree_h((*root)-left-left);int lrh get_avltree_h((*root)-left-right);bool isLL llh lrh ;if(isLL)ll_roate_avl(root);elselr_roate_avl(root);}/// 右子树高于左子树造成的不平衡if(rh-lh1){int rlh get_avltree_h((*root)-right-left);int rrh get_avltree_h((*root)-right-right);bool isRR rrh rlh ;if(isRR)rr_roate_avl(root);elserl_roate_avl(root); }
}void per_order_avlbinarytree(AVLNode *root)
{if (root NULL){return;}printf(d-avlbinarytree: %d\n, *(root-data));per_order_avlbinarytree(root-left);per_order_avlbinarytree(root-right);
}void ll_roate_avl(AVLNode **root)
{printf(lr_roate_avl----LL型\n);// (*root)-left temp-right;// temp-right (*root);// *root temp; AVLNode *temp (*root)-left-right;(*root)-left-right *root;*root (*root)-left;(*root)-right-left temp;
}void rr_roate_avl(AVLNode **root)
{printf(lr_roate_avl----RR型\n);AVLNode *temp (*root)-right-left;(*root)-right-left *root;*root (*root)-right;(*root)-left-right temp;
}void lr_roate_avl(AVLNode **root)
{printf(lr_roate_avl----LR型\n);AVLNode *leftTree (*root)-left;rr_roate_avl(leftTree);(*root)-left leftTree;ll_roate_avl(root);
}void rl_roate_avl(AVLNode **root)
{printf(lr_roate_avl----RL型\n);AVLNode *rightRoot (*root)-right;ll_roate_avl(rightRoot);(*root)-right rightRoot;rr_roate_avl(root);
}
四、平衡二叉树测试
void test_avlbinarytree()
{//RR型 {1,2,3,4,5,6};//LL型 {7,6,5,4,3,2,1};//LR型 {5,2,6,1,3,4};//RL型 {4,3,8,6,5,10};NodeData arr[] {4,3,8,6,5,10};int len sizeof(arr)/sizeof(arr[0]);int i;AVLNode* root NULL;for(i0;ilen;i){insert_avlbinarytree_node(root,arr[i]);do_avltree_roate(root);}printf(start 中序遍历---\n);per_order_avlbinarytree(root);int lh get_avltree_h(root-left);int rh get_avltree_h(root-right);printf(树高度lh %d, rh %d\n,lh,rh);}
