数据结构之二叉树之平衡二叉树

￡神魔★判官ぃ 2022-06-10 07:57 199阅读 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;
    }