1数据结构(13)_二叉树的概念及常用操作实现

1. 树到二叉树的转换

思考：通用树结构的实现太过复杂（树中每个结点都可以有任意多的孩子，具有多种形态），工程中很少会用到如此复杂的树是否可以简化呢？
思路：减少树结点中孩子的数量。但这样树是否还能通用呢？

公司主营业务：网站设计、做网站、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。成都创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联公司推出克东免费做网站回馈大家。

1.1.树的两种表示法

双亲孩子表示法：
1 数据结构(13)_二叉树的概念及常用操作实现
孩子兄弟表示法：
1 数据结构(13)_二叉树的概念及常用操作实现
孩子兄弟表示法的特点：
1.能够表示任意的树形结构
2.每个结点包含一个数据成员和两个指针成员
3.孩子结点指针和兄弟结点指针构成“树杈”

2.2.二叉树

二叉树是由n(n>=0)个节点组成的有限集合，该集合或者为空，或者是由一个根结点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成。
1 数据结构(13)_二叉树的概念及常用操作实现
满二叉树：
如果二叉树中所有分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。
完全二叉树：
如果一棵具有N个结点高度为K的二叉树，它的每一个结点与高度为K的满二叉树中编号1~n的结点一一对应，则称这颗二叉树为完全二叉树。（从上到下，从左到右编号）。
完全二叉树的特性：
同样结点的二叉树，完全二叉树的高度最小；完全二叉树的叶结点一定出现在最下面两层。
1.最底层的叶结点一定出现在左边；
2.倒数第二层的叶结点一定出现在右边；
3.完全二叉树中度数为1的结点只有左孩子。
1 数据结构(13)_二叉树的概念及常用操作实现
总结：
1.通用树结构采用了双亲结点表示法进行描述；
2.孩子兄弟表示法也有能力描述任意类型的树结构；
3.孩子兄弟表示法能够将通用树转化为二叉树（最多有两个孩子）；

2.二叉树的深层特性

1.在二叉树的第i层最多有2^(i-1)个结点（i>=1）;
2.高度为K的二叉树最多有2^k - 1个结点（K>=0）;
3.对于任何一颗二叉树，如果其叶结点有n0个，度为2的非叶结点有n2个，则有n0 = n2 + 1;
推导证明：

  • 假设二叉树中为1的结点有n1个，总结点数为n，则：n = n0 + n1 + n2;
  • 假设二叉树中连接父子结点的边为e条，则： e = n1 + 2n2 (从上往下看，有一条边的结点+有两条边的结点)，同时从下往上看e = n-1(根结点之上没有与之相连的边)，故：

  • n1 + 2n2 = n-1 ==> n1 + 2n2 = n0 + n1 + n2 - 1 ==> n0 = n2 + 1
    4.具有n个结点的完全二叉树的告诉为【log2N】 + 1 （【x】表示不大于x的最大整数）
    1 数据结构(13)_二叉树的概念及常用操作实现
    5.
    1 数据结构(13)_二叉树的概念及常用操作实现

    3.二叉树的存储结构设计

    目标：完成二叉树和二叉树结点的存储设计；
    1 数据结构(13)_二叉树的概念及常用操作实现
    设计要点：
    1.BTree为二叉树，每个结点最多只有两个后继结点；
    2.BTreeNode只包含4个固有的公有成员：（数据成员、指向左孩子和右孩子的指针、指向父节点的指针）
    BTreeNode的设计
    直接继承自抽象树结点，使用工厂模式(标识使用的堆空间，方便使用智能指针进行释放)。
    1 数据结构(13)_二叉树的概念及常用操作实现

    template < typename T >
class BTreeNode : public TreeNode
{
public:
BTreeNode* left;
BTreeNode* right;

static BTreeNode* NewNode()
{
    BTreeNode* ret = new BTreeNode();

    if(ret != NULL)
    {
        ret->m_flag = true;  //在堆空间中申请了结点，则将该标识置为true
    }

    return ret;
}

~BTreeNode(){}
};

    BTree的设计
    继承自抽象树结构，并组合使用BTreeNode.
    1 数据结构(13)_二叉树的概念及常用操作实现

template < typename T >
class BTree : public Tree
{

};

二叉树的实现架构：
1 数据结构(13)_二叉树的概念及常用操作实现

4. 二叉树的常用操作

4.1 .二叉树的查找操作

1 数据结构(13)_二叉树的概念及常用操作实现
1.基于数据元素值的查找：
BTreeNode* find(const T& value) const
1 数据结构(13)_二叉树的概念及常用操作实现

    virtual BTreeNode* find(BTreeNode* node, const T& value) const
    {
        BTreeNode* ret = NULL;

        if(node != NULL)    // 判断是否为空树
        {
            if(node->value == value)    //比较根结点
            {
                ret = node;
            }
            else
            {
                if(ret == NULL)
                {
                    //递归查找左子树
                    ret = find(node->m_left, value);
                }

                if(ret == NULL)
                {
                    //递归查找右子树
                    ret = find(node->m_right, value);
                }
            }
        }

        return ret;
    }

        BTreeNode* find(const T& value) const
    {
        return find(root(), value);
    }

2.基于结点的查找：
BTreeNode find(TreeNode node) const
1 数据结构(13)_二叉树的概念及常用操作实现

        virtual BTreeNode* find(BTreeNode* node, BTreeNode* obj) const
    {
        BTreeNode* ret = NULL;

        if(node != NULL)    // 判断是否为空树
        {
            if(node == obj)    //比较根结点
            {
                ret = node;
            }
            else
            {
                if(ret == NULL)
                {
                    //递归查找左子树
                    ret = find(node->m_left, obj);
                }

                if(ret == NULL)
                {
                    //递归查找右子树
                    ret = find(node->m_right, obj);
                }
            }
        }

        return ret;
    }

        BTreeNode* find(TreeNode* node) const
    {
        return find(root(), dynamic_cast*>(node));
    }

4.2.二叉树的插入操作

思考：是否能在二叉树的任意结点处插入子结点？
因为二叉树的定义中，每个结点最多只能有两个子结点，所以必然不能在任意结点处插入，因此需要制定新的数据元素(新结点)的插入位置。
二叉树结点的位置定义：

enum BTreeNodePos
{
    ANY,
    LEFT,
    RIGHT
};

1 数据结构(13)_二叉树的概念及常用操作实现
1 数据结构(13)_二叉树的概念及常用操作实现
1.定义功能函数，指定位置的结点插入：
virtual bool insert(BTreeNode<T>* newnode, BTreeNode<T>* node, BTNodePos pos)
1 数据结构(13)_二叉树的概念及常用操作实现

    virtual bool insert(BTreeNode* n, BTreeNode* np, BTreeNodePos pos)
    {
        bool ret = true;

        //指定的插入位置为ANY(没有指定插入位置)
        if(pos == ANY)
        {
            if(np->m_left == NULL)    // 左子树结点为空，插入到左子树
            {
                np->m_left = n;
            }
            else if(np->m_right == NULL)  // ...
            {
                np->m_right = n;
            }
            else
            {
                ret = false;
            }
        }

        // 指定插入到左孩子结点
        if(pos == LEFT)
        {
            if(np->m_left == NULL)
            {
                np->m_left = n;
            }
            else
            {
                ret = false;
            }
        }

        // 指定插入到右孩子结点
        if(pos == RIGHT)
        {
            if(np->m_right == NULL)
            {
                np->m_right = n;
            }
            else
            {
                ret = false;
            }
        }

        return ret;
    }

2.插入新结点

bool insert(TreeNode* node, BTreeNodePos pos)
bool insert(TreeNode* node)

1 数据结构(13)_二叉树的概念及常用操作实现 

    //插入结点，并指定位置
    bool insert(TreeNode* node, BTreeNodePos pos)
    {
        bool ret = true;

        if(node != NULL)
        {
            if(root() == NULL)   //判断根结点处是否可以插入
            {
                node->m_parent = NULL;
                this->m_root = node;
            }
            else
            {
                BTreeNode* np  = find(node->m_parent);   //查找父节点是否存在

                if(np != NULL)
                {
                    // 调用二叉树插入操作功能函数
                    ret = insert(dynamic_cast*>(node), np, pos);
                }
                else
                {
                    THROW_EXCEPTION(InvaildParameterException, "invalid parent tree node...");
                }
            }
        }
        else
        {
            THROW_EXCEPTION(InvaildParameterException, "param con't be NULL...");
        }

        return ret;
    }

    //插入结点，无位置要求
    bool insert(TreeNode* node)
    {
        return insert(node, ANY);
    }

3.插入数据元素 

bool insert(const T& value,TreeNode* parent, BTreeNodePos pos)
bool insert(const T& value,TreeNode* parent)

1 数据结构(13)_二叉树的概念及常用操作实现

    //插入数据元素，指定位置
    bool insert(const T& value,TreeNode* parent, BTreeNodePos pos)
    {
        bool ret = true;

        BTreeNode* node = BTreeNode::NewNode();

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

            insert(node, pos);
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create new tree node...");
        }

        return ret;
    }

    bool insert(const T& value,TreeNode* parent)
    {
        return insert(value, parent, ANY);
    }

测试技巧：从叶结点到根结点为线性数据结构，可以使用链表的遍历方式。
总结：
1.二叉树的插入操作需要指明插入的位置；
2.插入操作必须正确处理指向父节点的指针
3.插入数据元素时需要从堆空间中创建结点，让数据元素插入失败时，需要释放结点空间。

4.3. 二叉树中结点的删除与清除

4.3.1.结点删除操作

1 数据结构(13)_二叉树的概念及常用操作实现
1.删除操作功能定义
void remove(BTreeNode node, BTree& ret)
将node为根结点的子树从原来的二叉树中删除，ret作为子树返回(ret指向堆空间中的二叉树对象)
1 数据结构(13)_二叉树的概念及常用操作实现

    virtual void remove(BTreeNode* node, BTree*& ret)
    {
        ret = new BTree();

        if(ret != NULL)
        {
            if(root() == node)
            {
                this->m_root = NULL;
            }
            else
            {
                BTreeNode* np = dynamic_cast*>(node->m_parent);

                if(np->m_left == node)
                {
                    np->m_left = NULL;
                }
                else if(np->m_right == node)
                {
                    np->m_right = NULL;
                }

                node->m_parent = NULL;
            }

            ret->m_root = node;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create new tree...");
        }
    }

2.基于数据元素的删除
SharedPointer< Tree > remove(const T& value)

    SharedPointer< Tree > remove(const T& value)
    {
        BTree* ret = NULL;
        BTreeNode* node = find(value);

        if(node != NULL)
        {
            remove(node, ret);
            m_queue.clear();
        }

        return ret;
    }

3.基于结点的删除
SharedPointer< Tree > remove(TreeNode* node)

    SharedPointer< Tree > remove(TreeNode* node)
    {
        BTree* ret = NULL;
        node = find(node);

        if(node != NULL)
        {
            remove(dynamic_cast*>(node), ret);
            m_queue.clear();
        }

        return ret;
    }

测试技巧：直接打印已经删除的子树。
总结：
删除操作将目标界定啊所在的子树移除，必须完善处理父子结点的关系

4.3.2.结点清除操作

void clear() // 将二叉树中的所有节点清除(释放堆中的结点)
1 数据结构(13)_二叉树的概念及常用操作实现
1.清除操作功能定义
free(node) // 清除node为根结点的二叉树，释放二叉树中的每个结点
1 数据结构(13)_二叉树的概念及常用操作实现

    // 清空树的功能函数定义
    void free(BTreeNode* node)
    {
        if(node != NULL)
        {
            free(node->m_left);
            free(node->m_right);

            //cout << node->value << endl;
            if(node->flag())
            {
                delete node;
            }
        }
    }

    void clear()
    {
        free(root());
        this->m_root = NULL;
    }

测试技巧：可以在free函数中打印删除的每一个结点
总结：
清除操作用于销毁树中的每个结点，销毁时要判断是否释放对应的内存空间(工厂模式)。

4.4.二叉树的属性操作实现

1 数据结构(13)_二叉树的概念及常用操作实现

4.4.1.二叉树的结点数目

定义功能函数：cout(node) // 在node为根结点的二叉树中递归统计结点数目
1 数据结构(13)_二叉树的概念及常用操作实现

    // 获取树的结点个数，递归实现
    int count(BTreeNode* node) const
    {
        int ret = 0;

        if(node != NULL)
        {
            // 左子树的结点个数 + 右子树的结点个数 + 1(根结点)
            ret = count(node->m_left) + count(node->m_right) + 1;
        }

        return ret;
    }

    int count() const
    {
        return  count(root());
    }

4.4.2.二叉树的高度

定义功能函数：height(node) // 递归获取node为根结点的二叉树的高度
1 数据结构(13)_二叉树的概念及常用操作实现

    // 获取树的结点个数，递归实现
    int height(BTreeNode* node) const
    {
        int ret = 0;

        if(node != NULL)
        {
            int hl = height(node->m_left);
            int hr = height(node->m_right);

            // 左右子树高度的最大值 + 1(根结点)
            ret = ((hl > hr) ? hl : hr) + 1;
        }

        return ret;
    }

    int height() const
    {
        return  height(root());
    }

4.4.3.二叉树的度数

定义功能函数：degree(node) // 获取node为根结点的二叉树的度数
1 数据结构(13)_二叉树的概念及常用操作实现

    // 获取二叉树的度，递归实现
    int degree(BTreeNode* node) const
    {
        int ret = 0;

        if(node != NULL)
        {
        /*
         // 普通思路
            int dl = degree(node->m_left);  // 左子树的度
            int dr = degree(node->m_right); // 右子树的度
            ret = !!node->m_left + !!node->m_right;     //根结点的度

            if(dl > ret)
            {
                ret = dl;
            }
            else if(dr > ret)
            {
                ret = dr;
            }
        */
        /*
         * 优化效率，二叉树的最大度数为2，如果ret已经为2，则不需要继续遍历
            ret = !!node->m_left + !!node->m_right;     //根结点的度
            if(ret < 2)
            {
                int dl = degree(node->m_left);  // 左子树的度
                if(dl > ret)
                {
                    ret = dl;
                }

            }

            if(ret < 2)
            {
                int dr = degree(node->m_right);  // 左子树的度
                if(dr > ret)
                {
                    ret = dr;
                }

            }
        */

            // 优化冗余代码
            ret = !!node->m_left + !!node->m_right;     //根结点的度
            BTreeNode* child[] = {node->m_left, node->m_right};

            for(int i=0; i<2 && ret<2; i++)
            {
                int d = degree(child[i]);
                if(d > ret)
                {
                    ret = d;
                }
            }
        }

        return ret;
    }

    int degree() const
    {
        return degree(root());
    }

4.5.二叉树的层次遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有节点，使得每个结点被访问一次。
思考：通用树结构的层次遍历算法是否可以用在二叉树结构上？如果可以需要做什么改动？
不同之处在于二叉树最多只有两个孩子。
设计思路：
在树中定义一个新游标(BTreeNode*)，遍历开始将游标指向根结点(root())，获取游标指向的数据元素，通过结点中的child成员移动游标；
提供一组遍历相关的函数，按层次访问树中的数据元素。
1 数据结构(13)_二叉树的概念及常用操作实现
层次遍历算法：
原料：class LinkQueue; 游标：LinkQueue::front();
思想：

  • begin() 将根结点压人队列中
  • current() 访问队头指向的数据元素
  • next() 队头元素弹出，将队头元素的孩子(左孩子、右孩子)压入队列中(核心)

  • end() 判断队列是否为空
    1 数据结构(13)_二叉树的概念及常用操作实现

    bool begin()
{
    bool ret = (root() != NULL);

    if(ret)
    {
        m_queue.clear();
        m_queue.enqueue(root());    //把根结点压入队里
    }

    return ret;
}

bool end()
{
    return (m_queue.length() == 0);
}

bool next()
{
    bool ret = (m_queue.length() > 0);

    if(ret)
    {
        BTreeNode* node = m_queue.front();
        m_queue.dequeue();

        // 二叉树的左右孩子入队列
        if(node->m_left != NULL)
        {
            m_queue.enqueue(node->m_left);
        }
        if(node->m_right != NULL)
        {
            m_queue.enqueue(node->m_right);
        }
    }

    return ret;
}

// 获取游标所执行的元素
T current()
{
    if(!end())
    {
        return m_queue.front()->value;
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationException, "invalid operation ...");
    }
}

    使用示例：
    for(bt.begin(); !bt.end(); bt.next())
    {
    cout << bt.current() << " ";
    }

    5.二叉树的典型遍历方式

    问题：二叉树是否只有一种遍历方式(层次遍历)？
    典型的二叉树遍历方式：
    这里的先序、后序、中序指的的根结点的访问次序
    1.先序遍历(Pre-Order Traversal)
    1 数据结构(13)_二叉树的概念及常用操作实现

    // 先序遍历
void PreOrderTraversal(BTreeNode* node, LinkQueue*>& queue)
{
    if(node != NULL)
    {
        queue.enqueue(node);
        PreOrderTraversal(node->m_left, queue);
        PreOrderTraversal(node->m_right, queue);
    }
}

    2.中序遍历(In-Order TRaversal)
    1 数据结构(13)_二叉树的概念及常用操作实现

    // 中序遍历
void InOrderTraversal(BTreeNode* node, LinkQueue*>& queue)
{
    if(node != NULL)
    {
        InOrderTraversal(node->m_left, queue);
        queue.enqueue(node);
        InOrderTraversal(node->m_right, queue);
    }
}

    3.后续遍历(Post-Order Traversal)
    1 数据结构(13)_二叉树的概念及常用操作实现

    // 后序遍历
void PostOrderTraversal(BTreeNode* node, LinkQueue*>& queue)
{
    if(node != NULL)
    {
        PostOrderTraversal(node->m_left, queue);
        PostOrderTraversal(node->m_right, queue);
        queue.enqueue(node);
    }
}

    4.层次遍历(LevelOrder- Traversal)

    // 层次遍历
void LevelOrderTraversal(BTreeNode* node,LinkQueue*>& queue)
{
    if(node != NULL)
    {
        LinkQueue*> tmp;   // 定义辅助队列

        tmp.enqueue(node);   // 根结点入队列

        while(tmp.length()>0)   // end
        {
            BTreeNode* n = tmp.front();
            if(n->m_left != NULL)
            {
                tmp.enqueue(n->m_left);
            }
            if(n->m_right != NULL)
            {
                tmp.enqueue(n->m_right);
            }
            tmp.dequeue();      //队头元素出队列，并存入输出队列
            queue.enqueue(n);
        }
    }
}

    思考：是否可以将二叉树的典型遍历方式算法集成到BTree中，如果可以，代码需要做怎样的改动？
    设计要点：
    1.不能与层次遍历函数冲突，必须设计新的函数接口
    2.算法执行完成后，能够方便的获得遍历结果，遍历结果能反映结点访问的先后次序
    函数接口设计：
    SharedPoiner> traversal(BTTraversal order)
    1.根据参数order选择执行遍历算法(先序、中序、后序)
    2.返回值为堆中的数组对象(生命周期由智能指针管理)
    3.数据元素的次序反映遍历的先后次序

    void traversal(BTTraversal order,LinkQueue*>& queue)
{
    switch (order)
        {
            case PreOrder:
            PreOrderTraversal(root(),queue);
            break;

        case InOrder:
            InOrderTraversal(root(),queue);
            break;

        case PostOrder:
            PostOrderTraversal(root(),queue);
            break;

        case LevelOrder:
            LevelOrderTraversal(root(),queue);
            break;

        default:
            THROW_EXCEPTION(InvaildParameterException,"Parameter order is invalid ...");
            break;
        }
}

SharedPointer> traversal(BTTraversal order)
{
    DynamicArray* ret = NULL;
    LinkQueue*> queue;     //保存执行二叉树结点的指针

    traversal(order, queue);

    ret = new DynamicArray(queue.length());

    if(ret != NULL)
    {
        for(int i=0; ilength(); i++,queue.dequeue())
        {
            //cout << queue.front()->value << endl;
            ret->set(i, queue.front()->value);
        }
    }
    else
    {
        THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create dynamic array...");
    }

    return ret;
}

    典型遍历示例：

    SharedPointer> sp = NULL;
sp = bt.traversal(PostOder);

for(int i=0; i<(*sp).length(); i++)
{
    cout << (*sp)[i] << " ";
}

    总结：
    1.二叉树的典型遍历都是以递归方式进行的；
    2.BTree以不同的函数接口支持典型遍历，防止与层次遍历冲突；

    6.二叉树的克隆、比较和相加

    6.1.二叉树克隆

    克隆当前树的一份拷贝，返回值为堆空间中的一颗新树(与当前树相等)。
    SharedPointer> clone() const
    功能函数定义：clone(node)
    递归克隆node为根结点的二叉树(数据元素在对应位置相等)
    1 数据结构(13)_二叉树的概念及常用操作实现

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

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

        if(ret != NULL)
        {
            ret->value = node->value;   // 克隆根结点
            ret->m_left = clone(node->m_left);      //递归克隆左子树
            ret->m_right = clone(node->m_right);    //递归克隆右子树

            //连接父子关系
            if(ret->m_left != NULL)
            {
                ret->m_left->m_parent = ret;
            }
            if(ret->m_right != NULL)
            {
                ret->m_right->m_parent = ret;
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create new tree node...");
        }
    }

    return ret;
}

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

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

    return ret;
}

    6.2.二叉树比较

    判断两颗二叉树中的数据元素是否对应相等：
    bool operater == (const BTree& btree)
    bool operater == (const BTree& btree)
    1 数据结构(13)_二叉树的概念及常用操作实现
    功能函数定义：equal(lh, rh)
    递归判断lh为根结点的二叉树和rh为根结点的二叉树是否相等。
    1 数据结构(13)_二叉树的概念及常用操作实现

    bool equal(BTreeNode* lh, BTreeNode* rh)
{
    bool ret = true;

    if(lh == rh)    // 自比较或者两棵树都为空
    {
        ret = true;
    }
    else if((lh != NULL) && (rh != NULL))   //参与比较的两棵树都不为空
    {
        // 递归比较根结点、左子树、右子树
        ret = ((lh->value == rh->value) && (equal(lh->m_left, rh->m_left)) && equal(lh->m_right, rh->m_right));

    }
    else    // 两棵树中有一颗为空
    {
        ret = false;
    }

    return ret;
}

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

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

    6.3.二叉树相加

    将当前二叉树与参数btree中的数据元素在对应的位置处相加，返回值(相加的结果)为堆空间中的一颗新二叉树。
    SharedPointer> add(const BTree& btree) const
    1 数据结构(13)_二叉树的概念及常用操作实现
    二叉树相加操作功能函数定义：add(lh, rh),将lh为根节点的二叉树与rh为根结点的二叉树相加。
    1 数据结构(13)_二叉树的概念及常用操作实现

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

    if((lh != NULL) && (rh == NULL))    // 二叉树lh不为空
    {
        ret = clone(lh);
    }
    if((lh == NULL) && (rh != NULL))    // 二叉树rh不为空
    {
        ret = clone(rh);
    }
    if((lh != NULL) && (rh != NULL))    // 二叉树都不为空
    {
        ret = BTreeNode::NewNode();

        if(ret != NULL)
        {
            ret->value = lh->value + rh->value;    // 根结点相加
            ret->m_left = add(lh->m_left, rh->m_left);            // 左子树递归相加
            ret->m_right = add(lh->m_right, rh->m_right);         // 右子树递归相加

            //连接父子关系
            if(ret->m_left != NULL)
            {
                ret->m_left->m_parent = ret;
            }
            if(ret->m_right != NULL)
            {
                ret->m_right->m_parent = ret;
            }
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create new tree node...");
        }
    }

    return ret;
}

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

    if(ret != NULL)
    {
        ret->m_root = add(root(), btree.root());
    }
    else
    {
        THROW_EXCEPTION(NoEnoughMemoryException, "no memory to create new node...");
    }
    return ret;
}

    7.二叉树线索化实现

    1.什么是线索化二叉树？
    将二叉树转换为双向链表的过程(非线性-->线性)的过程称为线索化。
    能够反映某种二叉树的遍历次序（结点的先后访问次序）
    技巧：利用结点的right指针指向遍历中的后继结点，left指针指向前驱结点。
    为什么要要进行线索化？
    二叉树的遍历操作都采用递归进行(比较低效)，如果需要经常遍历，将二叉树进行线索化后作为双向链表存在，后续直接访问双向链表将提高效率。
    2.如何对二叉树进行线索化？
    1 数据结构(13)_二叉树的概念及常用操作实现
    使用某种遍历算法对二叉树进行遍历，在遍历的同时将遍历顺序存储到队列，然后使用left和right指针连接队列中的结点。
    1 数据结构(13)_二叉树的概念及常用操作实现
    3.目标

  • 新增功能函数traversal(order, queue),同时新增遍历方式（层次遍历）LeverOrder

  • 新增共有函数BTreeNode* thread(BTTraversal order)
    4.层次遍历实现
    (1)将根结点压入队列
    (2)访问队头元素指向的二叉树结点
    (3)队头元素弹出，将队头元素的孩子压入队列
    (4)判断队列是否为空(非空：执行2，空：结束)
    1 数据结构(13)_二叉树的概念及常用操作实现
    1 数据结构(13)_二叉树的概念及常用操作实现

    // 层次遍历
void LevelOrderTraversal(BTreeNode* node,LinkQueue*>& queue)
{
    if(node != NULL)
    {
        LinkQueue*> tmp;   // 定义辅助队列

        tmp.enqueue(node);   // 根结点入队列

        while(tmp.length()>0)   // end
        {
            BTreeNode* n = tmp.front();
            if(n->m_left != NULL)
            {
                tmp.enqueue(n->m_left);
            }
            if(n->m_right != NULL)
            {
                tmp.enqueue(n->m_right);
            }
            tmp.dequeue();      //队头元素出队列，并存入输出队列
            queue.enqueue(n);
        }
    }
}

    5.线索化实现
    函数接口：BTreeNode* thread(BTTraversal order)
    (1)根据参数order选择线索化的次序（先序、中序、后续、层次）
    (2)连接线索化后的结点；
    (3)返回线索化后指向链表首节点的指针，并将对应的二叉树变为空树
    1 数据结构(13)_二叉树的概念及常用操作实现
    6.队列中结点的连接

  • 初始操作，定义一个slider指针并指向队列头部元素，队列头部元素的left指针指向NULL并出队列；

  • slider的right指针指向新的队列头部元素，队头元素的left指针指向slider，slider记录队头元素，队头元素出队列。
    1 数据结构(13)_二叉树的概念及常用操作实现

    void traversal(BTTraversal order,LinkQueue*>& queue)
{
    switch (order)
        {
            case PreOrder:
            PreOrderTraversal(root(),queue);
            break;

        case InOrder:
            InOrderTraversal(root(),queue);
            break;

        case PostOrder:
            PostOrderTraversal(root(),queue);
            break;

        case LevelOrder:
            LevelOrderTraversal(root(),queue);
            break;

        default:
            THROW_EXCEPTION(InvaildParameterException,"Parameter order is invalid ...");
            break;
        }
}

BTreeNode* connect(LinkQueue*>& queue)
{
    BTreeNode* ret = NULL;

    if(queue.length() > 0)
    {
        //返回队列的队头元素指向的结点作为双向链表的首结点
        ret = queue.front();

        //创建一个游标结点，指向队列队头
        BTreeNode* slider = queue.front();
        //将队头元素出队
        queue.dequeue();
        //双向链表的首结点的前驱设置为空
        ret->m_left = NULL;

        while(queue.length() > 0)
        {
            //当前游标结点的后继指向队头元素
            slider->m_right = queue.front();
            //当前队头元素的前驱指向当前游标结点
            queue.front()->m_left = slider;
            //将当前游标结点移动到队头元素
            slider = queue.front();
            //将当前队头元素出队，继续处理新的队头元素
            queue.dequeue();
        }
        //双向链表的尾结点的后继为空
        slider->m_right = NULL;
    }

    return ret;
}

BTreeNode* thread(BTTraversal order)
{
    BTreeNode* ret = NULL;
    LinkQueue*> queue;

    traversal(order, queue);    //遍历二叉树，并按遍历次序将结点保存到队列
    ret = connect(queue);    //连接队列中的结点成为双向链表
    this->m_root = NULL;    //将二叉树的根节点置空

    m_queue.clear();    //将游标遍历的辅助队列清空

    //返回双向链表的首结点
    return ret;
}

    总结：
    1.线索化是将二叉树转化为双向链表的过程，线索华后结点间的先后次序符合某种遍历次序；
    2.线索化将破坏原二叉树间的父子关系，同时线索化后二叉树将不再管理结点中的生命周期（二叉树已经不存在，只有双向链表）。

    8.二叉树的经典面试题分析

    8.1.单度结点删除

    要求：编写一个函数用于删除二叉树中的所欲单度结点，结点删除后，其唯一的子结点代替它的位置
    1 数据结构(13)_二叉树的概念及常用操作实现

    8.1.1.结点中包含指向父节点的指针

    定义功能函数：delOdde(node) // 递归删除node为根结点的二叉树中的单度结点
    1 数据结构(13)_二叉树的概念及常用操作实现

    template 
BTreeNode* delOdd1(BTreeNode* node)
{
BTreeNode* ret = NULL;
if(node != NULL)    //递归出口
{
    // 判断单度结点
    if( ((node->m_left != NULL) && (node->m_right == NULL)) ||
        ((node->m_left == NULL) && (node->m_right != NULL)) )
    {
        BTreeNode*  parent = dynamic_cast*>(node->m_parent);
        BTreeNode* node_child = (node->m_left != NULL) ? node->m_left : node->m_right;

        if(parent != NULL)
        {
            // 删除单度结点，并使用唯一的子结点代替它的位置
            BTreeNode*& parent_child = (parent->m_left == node) ? parent->m_left : parent->m_right;
            parent_child = node_child;      // 处理指向子结点的指针
            node_child->m_parent = parent;  // 处理指向父结点指针
        }
        else
        {
            node_child->m_parent = NULL;
        }

        if(node->flag())
        {
            delete node;    // 如果节点创建字堆空间，释放内存
        }
        ret = delOdd1(node_child);  // 最后删除该单度结点
    }
    else    // 非单度结点
    {
        delOdd1(node->m_left);
        delOdd1(node->m_right);
        ret = node;
    }
}
return ret;
}

    8.1.2.结点中只包含左右孩子指针

    定义功能函数：delOdde(node) // 递归删除node为根结点的二叉树中的单度结点，其中node为结点指针的引用
    1 数据结构(13)_二叉树的概念及常用操作实现

    template 
void delOdd2(BTreeNode*& node)
{
if(node != NULL)    // 递归出口
{
    // 判断单度结点
    if( ((node->m_left != NULL) && (node->m_right == NULL)) ||
        ((node->m_left == NULL) && (node->m_right != NULL)) )
    {
        // 删除单度结点，并使用唯一的子结点代替它的位置
        BTreeNode* node_child = (node->m_left != NULL) ? node->m_left : node->m_right;
        if(node->flag())
        {
            delete node;
        }
        node = node_child;      // 因为没有指向父结点的指针，所以只需要处理指向子结点的指针
        delOdd2(node);
    }
    else    // 非单度结点
    {
        delOdd2(node->m_left);
        delOdd2(node->m_right);
    }
}
}

    8.2.中序线索化二叉树

    要求：编写一个函数用于中序线索化二叉树，不能使用其他的数据结构。
    1 数据结构(13)_二叉树的概念及常用操作实现

    8.2.1.解法1

    在中序遍历的同时进行线索化
    思路：使用辅助指针，在中序遍历时指向当前结点的前驱结点，访问当前结点时，连接与前驱结点的先后次序。
    1 数据结构(13)_二叉树的概念及常用操作实现
    定义功能函数：inOrderThread(node,pre),其中node为根结点，也是中序遍历访问的结点，pre为中序遍历时的前驱结点指针。
    1 数据结构(13)_二叉树的概念及常用操作实现

template 
// 其中node为根结点，也是中序遍历访问的结点，pre为中序遍历时的前驱结点指针
void inOrderThread(BTreeNode* node,BTreeNode*& pre)   
{
    if(node != NULL)
    {
        inOrderThread(node->m_left,pre);
        node->m_left = pre;
        if(pre != NULL)
        {
            pre->m_right = node;
        }
        pre = node;
        inOrderThread(node->m_right,pre);
    }
}

template 
BTreeNode* inOrderThread1(BTreeNode* node)
{
    BTreeNode* pre = NULL;
    inOrderThread(node,pre);

    while((node != NULL) && (node->m_left != NULL))
    {
        node = node->m_left;
    }

    return node;
}

8.2.2.解法2

中序遍历的结点正好是结点的水平次序
思路：
1.使用辅助指针，指向转换后双向链表的头节点和尾节点；
2.根结点与左右子树转为的双向链表连接，称为完整双向链表。
1 数据结构(13)_二叉树的概念及常用操作实现
定义功能函数：inOrderThread(node, head, tail)：
Node为根结点，也是中序遍历的访问结点，head转后成功后指向双向链表的首节点，tail转换成功后指向双向链表的尾节点。
1 数据结构(13)_二叉树的概念及常用操作实现

template 
// Node为根结点，也是中序遍历的访问结点，head转换成功后指向双向链表的首节点，tail转换成功后指向双向链表的尾节点
void inOrderThread(BTreeNode* node,BTreeNode*& head,BTreeNode*& tail)
{
    if(node != NULL)
    {
        BTreeNode* h = NULL;
        BTreeNode* t = NULL;
        inOrderThread(node->m_left,h,t);
        node->m_left = t;
        if(t != NULL)
        {
            t->m_right = node;
        }

        head = (h != NULL) ?  h : node;

        h = NULL;
        t = NULL;

        inOrderThread(node->m_right,h,t);
        node->m_right = h;
        if(h != NULL)
        {
            h->m_left = node;
        }
        tail = (t != NULL) ?  t : node;
    }
}

template 
BTreeNode* inOrderThread2(BTreeNode* node)
{
    BTreeNode* head = NULL;
    BTreeNode* tail = NULL;
    inOrderThread(node,head,tail);

    return head;
}

网页标题：1数据结构(13)_二叉树的概念及常用操作实现
地址分享：http://scjbc.cn/article/gsgscd.html

其他资讯

联系小谭

企业微信号
友情链接： 关键词排名优化   成都托管服务器   网站制作   达州网站建设   消防工程   瑞杰企业管理   温江做网站   重庆网站建设网络公司   绵竹做网站   响应式建站   

123ABC 成都网站建设，成都定制网站建设——全心全意建网站公司