数据结构之二叉树之平衡二叉树 ￡神魔★判官ぃ 2022-06-10 07:57 151阅读 0赞 **建立平衡二叉树：** **建利平衡二叉树的关键的是要搞清楚关键步骤，首先判断平衡因子，如果等于2或者-2，就要开始旋转了，旋转主要有四种类型，左左旋，左右旋，右右旋，右左旋。这里就不一一解释了，网上好多介绍如何旋转的。** **ps：对于我来说的难点。函数里面调用函数，始终有点晕，搞不清楚原理。从网上看了好多代码，最后终于搞清了原理，也最终写出了平衡二叉树**。 直接上代码： #include <stdio.h> #include <stdlib.h> typedef struct BiTNode { int data; int bf; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //计算深度的函数， int BiTDepth(BiTree root) { int depth,rdepth,ldepth; if(!root) depth = 0; else { ldepth = BiTDepth(root->lchild); rdepth = BiTDepth(root->rchild); if(ldepth>rdepth) depth = ldepth + 1; else depth = rdepth +1; } return depth; } //计算平衡因子的函数。 int max(BiTree root) { return BiTDepth(root->lchild)-BiTDepth(root->rchild); } BiTree R_Rotate(BiTree root) { BiTree L=root->lchild; /*L 指向*T 左子树根结点*/ root->lchild=L->rchild; /*L 的右子树挂接*T 的左子树*/ L->rchild = root; root=L; return root; /* *L 指向新的根结点*/ } BiTree L_Rotate(BiTree root) { BiTree Lr=root->rchild; /*Lr 指向*T 右子树根结点*/ root->rchild=Lr->lchild; /*L 的左子树挂接*p 的右子树*/ Lr->lchild=root; root=Lr; //printf("%d ",root->rchild->data); return root; /* *L 指向新的根结点*/ } //左平衡函数 //先判断不平衡节点的下一个节点的平衡因子。如果平衡因子为1，说明左边插入，说明是左左型， //如果是-1，说明是右右型，右边插入 BiTree Leftbalance(BiTree root) { BiTree l = root->lchild; switch(l->bf) { case 1: root = R_Rotate(root); break; case -1: l = L_Rotate(l); root->lchild = l; root = R_Rotate(root); break; } return root; } // 右平衡函数，同理左平衡函数。 BiTree Rightbalance(BiTree root) { BiTree r = root->rchild; switch(r->bf) { case -1: root = L_Rotate(root); break; case 1: r = R_Rotate(r); root->rchild = r; root = L_Rotate(root); break; } return root; } //创建二叉树的过程。函数里面调用函数 //新建的节点平衡因子一定为0 ，建好后，返回上一个节点。即新节点的双亲节点，并计算该节点的平衡因子， //不断向上找。直到找到平衡因子为2或-2的节点，然后进行平衡。 BiTree Creat(BiTree root,int m) { if(root == NULL) { root = (BiTree)malloc(sizeof(BiTNode)); root->data = m; root->lchild = root->rchild = NULL; root-> bf = 0; return root; } else if(m<root->data) { root->lchild = Creat(root->lchild,m); root->bf = max(root); if(root->bf==2) root = Leftbalance(root); } else { root->rchild = Creat(root->rchild,m); root->bf = max(root); if(root->bf==-2) root = Rightbalance(root); } return root; } int main() { int n; scanf("%d",&n); BiTree root = NULL; while(n--) { int m; scanf("%d",&m); root = Creat(root,m); } printf("%d\n",root->data); return 0; }
还没有评论，来说两句吧...