完全、平衡二叉树的判断与树拷贝、子树判断

太过爱你忘了你带给我的痛 2022-07-03 14:59 170阅读 0赞

## 完全二叉树的判断 ##

完全二叉树的n-1层是一颗满二叉树，最后一层的节点依次从左到右。所以只要n-1层第一次出现只有一个左孩子没有有孩子的情况或者没有左孩子的情况就做一个标记，往后的遍历的过程中如果还出现了有节点有孩子的情况就可以判断出此树非完全二叉树，否则就是完全二叉树。  
**代码实现如下：**

bool IsCompBinaryTree(BtNode *p)
    {
        if (p == NULL)
            return false;
        queue<BtNode*> qu;
        qu.push(p);
        int tag = 0;
        while (!qu.empty()&&tag!=1)
        {
            BtNode*tmp = qu.front();
            qu.pop();
            if (tmp->leftchild != NULL)
            {
                qu.push(tmp->leftchild);
                if (tmp->rightchild != NULL)
                {
                    qu.push(tmp->rightchild);
                }
                else
                {
                    tag=1;
                }
            }
            else
            {
                tag = 1;
            }
        }
        while (!qu.empty())
        {
            BtNode*tmp = qu.front();
            qu.pop();
            if (tmp->leftchild != NULL || tmp->rightchild != NULL)
            {
                return false;
            }
        }
        return true;
    }

## 平衡二叉树的判断 ##

平衡二叉树：左子树和右子树的高度之差不超过一，并且左右子树又分别的平衡二叉树。所以根据概念可以使用递归的思想，这里需要使用一个函数计算树的高度。  
**树高度计算代码：**

int GetDepth(BtNode*root)
    {
        if (root == NULL)
            return 0;
        int left_depth = GetDepth(root->leftchild);
        int right_depth = GetDepth(root->rightchild);
        return left_depth > right_depth ? left_depth + 1 : right_depth+1;
    }

**平衡二叉树判断的代码实现：**

bool IsBalanceBinaryTree(BtNode *p)
    {
        if (p == NULL)
            return true;
        int l_depth = GetDepth(p->leftchild);
        int r_depth = GetDepth(p->leftchild);
        int res = l_depth - r_depth;
        if (res > 1 || res < -1)
            return false;
        return IsBalanceBinaryTree(p->leftchild) && IsBalanceBinaryTree(p->rightchild);
    }

## 子树判断 ##

判断一课树是否为另外一课树的子树，方法很简单，先通过函数FindValue找到子树根节点在目标树中的位置，然后再判断n层子树是否分别想等于目标树。  
**FindValue实现：**

BtNode *FindValue(BtNode *root,Elemtype value)
    {
        if (root==NULL)
            return NULL;
        if (root->data == value)
            return root;
        BtNode *p = FindValue(root->leftchild, value);
        if (p == NULL)
        {
            p = FindValue(root->rightchild, value);
        }
        return p;
    }

**子树判断代码实现：**

bool IsEquel(BtNode*ptr, BtNode*sub,int k)
    {
        if (ptr == NULL&&sub != NULL)
            return false;
        if (k == 0)
            return true;
        return ptr->data == sub->data&&IsEquel(ptr->leftchild, sub->leftchild, k - 1) &&
            IsEquel(ptr->rightchild, sub->rightchild, k - 1);
    }
    bool Is_SubTree(BtNode *ptr, BtNode *sub)
    {
        if (sub == NULL || ptr == NULL)
            return false;
        BtNode*p = FindValue(ptr, sub->data);
        if (p == NULL)
            return false;
        int sub_depth = GetDepth(sub);
        return IsEquel(p, sub,sub_depth);
    }

## 树与树之间的复制 ##

树之间的copy需要节点的购买，然后将这些节点按照别拷贝树的结构创建。  
**BuyNode代码：**

BtNode* BuyBtNode()
    {
        BtNode *s = new BtNode();
        s->data =0;
        s->leftchild = NULL;
        s->rightchild = NULL;
        return s;
    }

**Copy代码：**

BtNode * Copy(BtNode *ptr)
    {
    
        if (ptr == NULL)
            return NULL;
    
        BtNode*proot = BuyBtNode();
        proot->data = ptr->data;
        proot->leftchild = Copy(ptr->leftchild);
        proot->rightchild = Copy(ptr->rightchild);
        return proot;
    }