树的递归遍历和非递归遍历

我们知道树的遍历方式分为深度优先和广度优先,而每种方式又可以采用递归和非递归的方式进行. 递归的好处在于容易理解,但是深度太深的话,容易造成栈溢出.因此我们可以用模拟的方式来实现遍历.

1. 首先我们给出树节点的定义方式

class TreeNode
{
public:
    explicit TreeNode(int value,
             TreeNode * parent,
             TreeNode * sibling,
             TreeNode * firstChild);

    virtual ~TreeNode();
    int value_;
    TreeNode * pParent_;
    TreeNode * pFirstChild_;
    TreeNode * pSibling_;
};

我们定义了父节点,第一个孩子节点和兄弟节点这样的方式比较容易表示多叉树.

C++11

class TreeNodeMorden;
using NodeSharedPtr = std::shared_ptr<TreeNodeMorden>;
using NodeWeakPtr = std::weak_ptr<TreeNodeMorden>;
class TreeNodeMorden
{
public:
    TreeNodeMorden(int value,
             NodeWeakPtr parent,
             NodeSharedPtr sibling,
             NodeSharedPtr firstChild);

    virtual ~TreeNodeMorden();
    int value_;
    NodeWeakPtr  pParent_;
    NodeSharedPtr  pFirstChild_;
    NodeSharedPtr  pSibling_;
};

C++11通过使用std::shared_ptr与 std::weak_ptr 可以更方便的管理对象的生命周期,而不用担心内存泄露的问题.相对于使用原始指针方便了很多.

2. 树的深度优先遍历

递归版本

void DepthFirstTraversalRecusion(TreeNode* pRoot,std::vector<int>& vInt,std::vector<std::vector<int>>& allValue)
{
    if(pRoot)
    {
        vInt.push_back(pRoot->value_);
        DepthFirstTraversalRecusion(pRoot->pFirstChild_,vInt,allValue);
        DepthFirstTraversalRecusion(pRoot->pSibling_,vInt,allValue);

        //My Func Begin
        if(nullptr == pRoot->pFirstChild_)
        {

            {
                std::vector<int> lineVec;
                TreeNode* pCur = pRoot;
                while (nullptr != pCur)
                {
                    lineVec.push_back(pCur->value_);
                    pCur = pCur->pParent_;
                }
                std::reverse(lineVec.begin(), lineVec.end());
                allValue.push_back(lineVec);
            }

        }
        //My Func End
    }
}

在 My Func Begin 和 My Func End 之间的是我们的不同的处理,所以这个递归的版本非常的简单.

void DepthFirstTraversalLoop(TreeNode* pRoot,std::vector int>& vInt,std::vector std::vector int>>& allValue)
{
    std::stack TreeNode*> nodeStack;

    {
        //Loop Copy Begin
        TreeNode * pCur = pRoot;
        while(pCur)
        {
            vInt.push_back(pCur->value_);
            nodeStack.push(pCur);
            pCur = pCur->pFirstChild_;
        }
        //Loop Copy End
    }

    while(!nodeStack.empty())
    {
        //Stack Loop Begin
        TreeNode * pCur = nodeStack.top();
        nodeStack.pop();

        //My Func Begin
        if(nullptr == pCur->pFirstChild_)
        {
            TreeNode* pIndex = pCur;
            std::vector<int> lineVec;
            while(nullptr != pIndex)
            {
                lineVec.push_back(pIndex->value_);
                pIndex = pIndex->pParent_;
            }
            std::reverse(std::begin(lineVec),std::end(lineVec));
            allValue.push_back(lineVec); 
        }
        //My Func End

        if(nullptr != pCur->pSibling_)
        {
            //Loop Copy Begin
            pCur = pCur->pSibling_;
            while(pCur)
            {
                vInt.push_back(pCur->value_);
                nodeStack.push(pCur);
                pCur = pCur->pFirstChild_;
            }
            //Loop Copy End
        }
    }
}

在 My Func Begin 和 My Func End 之间的是我们的不同的处理, 循环的版本有两部分非常的相似( Loop Copy Begin & Loop Copy End),我采用Copy&Paste的方式进行,因为代码不多且容易理解,所以采用了这样的方式.

3. 树的广度优先遍历

递归版本

void BreadthFirstTraversalRecusion(TreeNode* pRoot,std::vector<int>& vInt,std::vector <std::vector <int>>& allValue)
{
    if(pRoot)
    {
        vInt.push_back(pRoot->value_);

        BreadthFirstTraversalRecusion(pRoot->pSibling_,vInt,allValue);
        BreadthFirstTraversalRecusion(pRoot->pFirstChild_,vInt,allValue);

        if(nullptr == pRoot->pFirstChild_)
        {
            //My Func Begin
            {
                std::vector <int> lineVec;
                TreeNode* pCur = pRoot;
                while (nullptr != pCur)
                {
                    lineVec.push_back(pCur->value_);
                    pCur = pCur->pParent_;
                }
                std::reverse(lineVec.begin(), lineVec.end());
                allValue.push_back(lineVec);
            }
            //My Func End
        }
    }
}

在 My Func Begin 和 My Func End 之间的是我们的不同的处理,所以这个递归的版本非常的简单. 仔细比较深度递归和广度递归,只是先传入FirstChild和先传入Sibling的区别.

非递归版本

void BreadthFirstTraversalLoop(TreeNode* pRoot,std::vector<int>& vInt,std::vector<std::vector <int>>& allValue)
{
    std::stack<TreeNode*> nodeStack;

    vInt.push_back(pRoot->value_);
    nodeStack.push(pRoot);

    while(!nodeStack.empty())
    {
        //Stack Loop Begin
        TreeNode * pCur = nodeStack.top();
        nodeStack.pop();
        if(nullptr != pCur->pFirstChild_)
        {
            pCur = pCur->pFirstChild_;
            vInt.push_back(pCur->value_);
            nodeStack.push(pCur);
            {
                while(pCur->pSibling_)
                {
                    vInt.push_back(pCur->pSibling_->value_);
                    nodeStack.push(pCur->pSibling_);
                    pCur = pCur->pSibling_;
                }
            }
        }
        //Stack Loop End
        //My Func Begin
        else
        {
            std::vector <int> lineVec;
            TreeNode* pIndex = pCur;
            while(nullptr != pIndex)
            {
                lineVec.push_back(pIndex->value_);
                pIndex = pIndex->pParent_;
            }
            std::reverse(std::begin(lineVec),std::end(lineVec));
            allValue.push_back(lineVec);     
        }
        //My Func  End
    }

    std::reverse(std::begin(allValue),std::end(allValue));
}

在 My Func Begin 和 My Func End 之间的是我们的不同的处理.

整体的代码在 https://github.com/DennisCoder1024/TreeStruct