c语言实现平衡二叉树的各种算法(源码和总结)

雨点打透心脏的1/2处 2022-11-28 13:57 98阅读 0赞

今天在整理资料的时候，看到了大一时候学习数据结构的大作业，想着无事就给重新梳理了一遍，对二叉树的理解和印象又加深了许多，现在分享出来，记录一下我的学习经历。

## 实现平衡二叉树的各种算法 ##

#### （1）插入新结点 ####

首先在二叉树中寻找新结点的插入位置，根据它们的data值判断，找到对应的位置，插入后用pingheng()判断二叉树是否平衡，二叉树的不平衡分为四种情况：LL型、RR型、LR型、RL型，并且根据不同类型对二叉树进行调整。

#### （2）前序、中序、后序遍历二叉树算法（递归） ####

根据先序，中序，后序遍历的规则，采用递归算法对二叉树进行遍历。

#### （3）前序、中序、后序遍历二叉树的非递归算法 ####

非递归的二叉树遍历算法需要借助栈来实现，在本程序中，采用了STL中的stack类来辅助，用了stack.empty()、stack.front()、stack.push()、stack.pop()等包装好的函数进行栈的操作，从而实现二叉树的非递归遍历算法。

#### （4）层次遍历二叉树 ####

二叉树的层次遍历算法需要借助队列来实现，在本程序中，采用了STL中的queue类来辅助，用了queue.empty()、queue.front()、queue.push()、queue.pop()等包装好的函数进行队列的操作，从而实现二叉树的层次遍历算法。

#### （5）在二叉树中查找关键字 ####

根据平衡二叉树的储存规则，如查找的值比当前结点大，就在其右子树T->right，反之T->left，相等时返回返回值1，找不到返回0。

#### （6）交换给结点的左右子树 ####

运用递归思维，函数自己调用自己，从而将问题减少化，来改变这颗树的左右子树，即swap(T)函数交换自己的左右子树，再swap(T->left)、swap(T->right)去进行自己的左右子树的子树交换。

#### （7）求二叉树的深度 ####

用递归算法求深度，运用shendu(T)=MAX(shendu(T->left),shendu(T->right))+1来求得树的深度。

#### （8）求二叉树的叶子结点数 ####

用递归算法求叶子结点数，即num(T)=num(T->left)+num(T->right),当某个节点的 T->left、T->right都为NULL才加1。

#### （9）删除某结点 ####

首先根据删除的值在二叉树中找到对应的节点，并且对节点的情况在分情况，第一种是节点左右子树都是空的，那么直接删除这个节点；第二种是该节点的左子树存在，右子树为空，就查找该节点的左子树中的最大值来代替该节点的值，再把左子树的最大值节点删除；

第三种是该节点的右子树存在，左子树为空，就查找该节点的右子树中的最小值来代替该节点的值，再把右子树的最小值节点删除；第四种是该节点的左右子树都存在，就查找该节点的左子树中的最大值来代替该节点的值，再把左子树的最大值节点删除。用上一种办法解决，然后用pingheng()函数判断该二叉树是否平衡，不平衡的话在根据情况对二叉树进行调整。

## 实现代码 ##

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <stack>
    #include <queue>
    using namespace std;
    
    typedef struct Node
    { 
        int data;
        struct Node *left,*right;
        int height;
    } BTNode,*BITREE;
    
    
    
    BTNode* ll(BTNode* y);                 //当二叉树不平衡且为LL型时对二叉树的调整
    BTNode* rr(BTNode* y);                 //当二叉树不平衡且为RR型时对二叉树的调整
    BTNode * minValueNode(BTNode* node);         //寻找平衡二叉树的最小结点
    int MAX(int a, int b);                                     //求出最大值
    int cha(struct Node *N);              //平衡因子，即该结点的左子树和右子树的深度之差
    int chazhao(BITREE T,int e);              //判断平衡二叉树中是否有与e值相等的结点
    BTNode* newNode(int data);                   //分配一个新结点，并且赋值
    int pingheng(BTNode* N);                            //判断二叉树是否平衡
    BTNode* insert(BTNode* node, int data);                  //平衡二叉树的新结点插入
    BTNode* deleteNode(BTNode* root, int data);              //删除平衡二叉树的某结点
    void first(BITREE T);                             //平衡二叉树的递归前序遍历
    void in(BITREE T);                             //平衡二叉树的递归中序遍历
    void last(BITREE T);                             //平衡二叉树的递归后序遍历
    void feifirst(BITREE T);                          //平衡二叉树的非递归前序遍历
    void feiin(BITREE T);                          //平衡二叉树的非递归中序遍历
    void feilast(BITREE T);                               //平衡二叉树的非递归后序遍历
    void ceng(BITREE T);                                 //平衡二叉树的层次遍历
    void swap(BITREE &T);                                //交换平衡二叉树的左右子树
    int shendu(BITREE T);                                    //求平衡二叉树的深度
    int num(BITREE T);                                   //求平衡二叉树的叶子结点数
    
    
    
    int cha(struct Node *N)                          //平衡因子，即该结点左子树和右子树的深度之差
    { 
        if (N == NULL)
            return 0;
        return N->height;
    }
    int MAX(int a, int b)                               //求两个数之间的最大值
    { 
        return (a > b) ? a : b;
    }
    BTNode* newNode(int data)                               //分配一个新结点，并把参数值附给它
    { 
        struct Node* node = (BTNode*)malloc(sizeof(struct Node));
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        node->height = 1;
        return(node);
    }
    
    int pingheng(BTNode* N)                         //判断二叉树是否平衡
    { 
        if (N == NULL)
            return 0;
        return cha(N->left) - cha(N->right);
    }
    BTNode* insert(BTNode* node, int data)                  //平衡二叉树的新结点插入
    { 
        if (!node)
            return newNode(data);
        if (data < node->data)
            node->left = insert(node->left, data);
        else if (data > node->data)
            node->right = insert(node->right, data);
        else
            return node;
        node->height = 1 + MAX(cha(node->left), cha(node->right));
        int balance = pingheng(node);
        if (balance > 1 && data < node->left->data)         //LL型
            return ll(node);
        if (balance < -1 && data > node->right->data)       //RR型
            return rr(node);
        if (balance > 1 && data > node->left->data)         //LR型
        { 
            node->left = rr(node->left);
            return ll(node);
        }
        if (balance < -1 && data < node->right->data)     //RL型
        { 
            node->right = ll(node->right);
            return rr(node);
        }
        return node;
    }
    BTNode* deleteNode(BTNode* root, int data)              //\删除平衡二叉树的某结点
    { 
    
        if (!root)
            return root;
    
        if (data < root->data)
            root->left = deleteNode(root->left, data);
    
        else if (data > root->data)
            root->right = deleteNode(root->right, data);
    
        else
        { 
            if (!root->left || !root->right)
            { 
                BTNode* temp = root->left ? root->left : root->right;
    
                if (!temp)
                { 
                    temp = root;
                    root = NULL;
                }
                else
                    *root = *temp;
                free(temp);
            }
            else
            { 
                BTNode* temp = minValueNode(root->right);
                root->data = temp->data;
                root->right = deleteNode(root->right, temp->data);
            }
        }
        if (!root)
            return root;
        root->height = 1 + MAX(cha(root->left), cha(root->right));
        int balance = pingheng(root);
        if (balance > 1 && pingheng(root->left) >= 0)               //LL型
            return ll(root);
        if (balance > 1 && pingheng(root->left) < 0)                //LR型
        { 
            root->left = rr(root->left);
            return ll(root);
        }
    
        if (balance < -1 && pingheng(root->right) <= 0)             //RR型
            return rr(root);
    
        if (balance < -1 && pingheng(root->right) > 0)              //Rl型
        { 
            root->right = ll(root->right);
            return rr(root);
        }
    
        return root;
    }
    BTNode* ll(BTNode* y)                           //当二叉树不平衡且为LL型时对二叉树的调整
    { 
        BTNode *x = y->left;
        y->left = x->right;
        x->right = y;
        y->height = MAX(cha(y->left), cha(y->right)) + 1;
        x->height = MAX(cha(x->left), cha(x->right)) + 1;
        return x;
    }
    BTNode* rr(BTNode* y)                        //当二叉树不平衡且为RR型时对二叉树的调整
    { 
        BTNode *x = y->right;
        y->right = x->left;
        x->left = y;
        y->height = MAX(cha(y->left), cha(y->right)) + 1;
        x->height = MAX(cha(x->left), cha(x->right)) + 1;
        return x;
    }
    BTNode * minValueNode(BTNode* node)                     //寻找平衡二叉树的最小结点
    { 
        BTNode* current = node;
    
        while (current->left)
            current = current->left;
    
        return current;
    }
    
    void first(BITREE T)                                        //平衡二叉树的递归前序遍历
    { 
        if(T)
        { 
            printf("%d ",T->data);
            first(T->left);
            first(T->right);
        }
    }
    void in(BITREE T)                                               //平衡二叉树的递归中序遍历
    { 
        if(T)
        { 
            in(T->left);
            printf("%d ",T->data);
            in(T->right);
        }
    }
    void last(BITREE T)                                         //平衡二叉树的递归后序遍历
    { 
        if(T)
        { 
            last(T->left);
            last(T->right);
            printf("%d ",T->data);
        }
    }
    void feifirst(BITREE T)                                      //平衡二叉树的非递归前序遍历
    { 
        BITREE s,q;
        s=T;
        stack<BITREE> a;
        while(s||!a.empty())
        { 
            if(s)
            { 
                printf("%d ",s->data);
                a.push(s);
                s=s->left;
            }
            else
            { 
                q=a.top();
                s=q->right;
                a.pop();
            }
        }
        printf("\n");
    }
    void feiin(BITREE T)                                     //平衡二叉树的非递归中序遍历
    { 
        BITREE s,q;
        s=T;
        stack<BITREE> a;
        while(s||!a.empty())
        { 
            if(s)
            { 
                a.push(s);
                s=s->left;
            }
            else
            { 
                q=a.top();
                printf("%d ",q->data);
                s=q->right;
                a.pop();
            }
        }
        printf("\n");
    }
    void feilast(BITREE T)                               //平衡二叉树的非递归后序遍历
    { 
        BITREE s,q;
        stack<BITREE> a;
        s=T,q=NULL;
        while(s)
        { 
            a.push(s);
            s=s->left;
        }
        while(!a.empty())
        { 
            s=a.top();
            a.pop();
            if(!s->right||s->right==q)
            { 
                printf("%d ",s->data);
                q=s;
            }
            else
            { 
                a.push(s);
                s=s->right;
                while(s)
                { 
                    a.push(s);
                    s=s->left;
                }
            }
        }
        printf("\n");
    }
    void ceng(BITREE T)                                 //平衡二叉树的层次遍历
    { 
        queue<BITREE> s;
        s.push(T);
        while(!s.empty())
        { 
            BITREE q;
            q=s.front();
            if(q->left)
                s.push(q->left);
            if(q->right)
                s.push(q->right);
            printf("%d ",q->data);
            s.pop();
        }
        printf("\n");
    }
    int chazhao(BITREE T,int e)                         //判断平衡二叉树中是否有与e值相等的结点
    { 
        while(T)
        { 
            if(T->data==e)
                return 1;
            else if(T->data>e)
                T=T->left;
            else if(T->data<e)
                T=T->right;
        }
        return 0;
    }
    void swap(BITREE &T)                                //交换平衡二叉树的左右子树
    { 
        if(T)
        { 
            BITREE q;
            swap(T->left);
            swap(T->right);
            q=T->left;
            T->left=T->right;
            T->right=q;
        }
    
    }
    int shendu(BITREE T)                                    //求平衡二叉树的深度
    { 
        int n=0,m=0;
        if(!T)
            return 0;
        else
        { 
            n=shendu(T->left);
            m=shendu(T->right);
            return m>n?(m+1):(n+1);
        }
    }
    int num(BITREE T)                                   //求平衡二叉树的叶子结点数
    { 
        if(!T)
            return 0;
        if(!T->left&&!T->right)
            return 1;
        else
            return num(T->left)+num(T->right);
    }
    int main()
    { 
        BTNode *root = NULL;
        int n,x;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        { 
            scanf("%d",&x);
            root=insert(root,x);
        }
        printf("递归前序遍历结果为：");
        first(root);
        printf("\n");
        printf("递归中序遍历结果为：");
        in(root);
        printf("\n");
        printf("递归后序遍历结果为：");
        last(root);
        printf("\n");
        printf("非递归前序遍历结果为：");
        feifirst(root);
        printf("非递归中序遍历结果为：");
        feiin(root);
        printf("非递归后序遍历结果为：");
        feilast(root);
        printf("层次遍历结果为：");
        ceng(root);
        printf("输入你想搜索的结点值：");
        scanf("%d",&x);
        if(chazhao(root,x))
            printf("该节点存在平衡二叉树中。\n");
        else
            printf("该节点不存在平衡二叉树中。\n");
        printf("这颗平衡二叉树的深度为：%d \n",shendu(root));
        printf("这颗平衡二叉树的叶子结点数：%d \n",num(root));
        printf("请输入你想要删除的结点值：");
        scanf("%d",&x);
        root=deleteNode(root,x);
        printf("删除结点后的二叉树的中序遍历结果为：");
        feiin(root);
        swap(root);
        printf("交换后的二叉树的中序遍历结果为：");
        feiin(root);
        return 0;
    }

## 调试分析 ##

#### （1）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析 ####

我觉得平衡二叉树的难点在于怎样对树进行调整，我在遇到这样的问题的时候，先是在网上查询了相关的文献资料，在资料的帮助下，理解了LL型，LR型，RL型，RR型等情况的树的调整方案和思维，并且把他们应用到了本次的程序的实现中，借此解决了这个难题。

#### （2）使用的测试数据（要求多组） ####

第一组：  
6  
25 12 63 9 100 88  
递归前序遍历结果为：25 12 9 88 63 100  
递归中序遍历结果为：9 12 25 63 88 100  
递归后序遍历结果为：9 12 63 100 88 25  
非递归前序遍历结果为：25 12 9 88 63 100  
非递归中序遍历结果为：9 12 25 63 88 100  
非递归后序遍历结果为：9 12 63 100 88 25  
层次遍历结果为：25 12 88 9 63 100  
输入你想搜索的结点值：63  
该节点存在平衡二叉树中。  
这颗平衡二叉树的深度为：3  
这颗平衡二叉树的叶子结点数：3  
请输入你想要删除的结点值：9  
删除结点后的二叉树的中序遍历结果为：12 25 63 88 100  
交换后的二叉树的中序遍历结果为：100 88 63 25 12

第二组：  
7  
24 4 89 14 34 65 100  
递归前序遍历结果为：24 4 14 65 34 89 100  
递归中序遍历结果为：4 14 24 34 65 89 100  
递归后序遍历结果为：14 4 34 100 89 65 24  
非递归前序遍历结果为：24 4 14 65 34 89 100  
非递归中序遍历结果为：4 14 24 34 65 89 100  
非递归后序遍历结果为：14 4 34 100 89 65 24  
层次遍历结果为：24 4 65 14 34 89 100  
输入你想搜索的结点值：2  
该节点不存在平衡二叉树中。  
这颗平衡二叉树的深度为：4  
这颗平衡二叉树的叶子结点数：3  
请输入你想要删除的结点值：4  
删除结点后的二叉树的中序遍历结果为：14 24 34 65 89 100  
交换后的二叉树的中序遍历结果为：100 89 65 34 24 14

#### 三、算法的效率分析和改进设想 ####

平衡二叉树在传统的二叉树上进行了改进，避免了因二叉树中左右子树深度相差过多，在操作时出现的效率不稳定性，使得操作的时间稳定在O（log2N），大大降低了操作的时间复杂度。