关键词：二叉树的克隆操作、二叉树比较操作、二叉树的相加操作

0. 二叉树的克隆操作

SharedPointer< BTree<T> > clone() const

• 克隆当前树的一份拷贝
• 返回值为堆空间中的一颗新二叉树（与当前树相等）
• 功能函数：clone(node)：拷贝node为根结点的二叉树（数据元素在对应位置相等）
  
  二叉树拷贝的递归调用

    BTreeNode<T>* clone(BTreeNode<T>* node) const
    {
        BTreeNode<T>* ret = NULL;

        if( node != NULL )
        {
            ret = BTreeNode<T>::NewNode();

            if( ret != NULL )
            {
                ret->value = node->value;

                ret->left = clone(node->left);
                ret->right = clone(node->right);

                if( ret->left != NULL )
                {
                    ret->left->parent = ret;
                }

                if( ret->right != NULL )
                {
                    ret->right->parent = ret;
                }
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create a BTreeNode...");
            }
        }

        return ret;
    }

    SharedPointer< BTree<T> > clone() const
    {
        BTree<T>* ret = new BTree<T>();

        if( ret != NULL )
        {
            ret->m_root = clone(root());
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create new BTree...");
        }

        return ret;
    }

1. 二叉树比较操作的定义

• 判断两个二叉树中的数据元素是否对应相等
  bool operator == (const BTree<T>& btree)
bool operator != (const BTree<T>& btree)
• 定义功能函数：equal(lh, rh)：判断lh为根结点的二叉树与rh为根结点的二叉树是否相等
  
  二叉树equal的递归调用

    bool equal(BTreeNode<T>* lh, BTreeNode<T>* rh) const
    {
        if( lh == rh)
        {
            return true;
        }
        else if( (lh != NULL) && (rh != NULL) )
        {
            return (lh->value == rh->value) && equal(lh->left, rh->left) && equal(lh->left, rh->left);
        }
        else
        {
            return false;
        }
    }

    bool operator == (const BTree<T>& btree)
    {
        return equal(root(), btree.root());
    }

    bool operator != (const BTree<T>& btree)
    {
        return !(*this == btree);
    }

2. 二叉树的相加操作

SharedPointer< BTree<T> > add(const BTree<T>& btree) const

• 将当前二叉树与参数btree中的数据元素在对应位置处相加
• 返回值（相加的结果）为堆空间中的一颗新二叉树
  
  二叉树相加操作示意图
• 定义功能函数：add(lh, rh)：将lh为根结点的二叉树与rh为根结点的二叉树相加
  
  二叉树相加操作的递归调用

    BTreeNode<T>* add(BTreeNode<T>* lh ,BTreeNode<T>* rh)const
    {
        BTreeNode<T>* ret = NULL;

        if( (lh == NULL) && (rh != NULL) )
        {
            ret = clone(rh);
        }
        else if( (lh != NULL) && (rh == NULL) )
        {
            ret = clone(lh);
        }
        else if( (lh != NULL) && (rh != NULL) )
        {
            ret = BTreeNode<T>::NewNode();

            if( ret != NULL )
            {
                ret->value = lh->value + rh->value;

                ret->left = add(lh->left, rh->left);
                ret->right = add(lh->right, rh->right);

                if( ret->left != NULL )
                {
                    ret->left->parent = ret;
                }

                if( ret->right != NULL )
                {
                    ret->right->parent = ret;
                }
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create a new node ...");
            }
        }

        return ret;
    }

    SharedPointer< BTree<T> > add(const BTree<T>& btree)const
    {
        BTree<T>* ret = new BTree<T>();

        if( ret != NULL )
        {
            ret->m_root = add(root(), btree.root());
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create new Btree ...");
        }

        return ret;
    }

3. 小结

• 比较操作判断两颗二叉树中的数据元素是否相等
• 克隆操作将当前二叉树在堆空间进行复制
• 相加操作将两棵二叉树中的数据元素在对应位置处相加
• 相加操作的结果保存在堆空间的一棵二叉树中

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4