이 진 트 리 옮 겨 다 니 기 알고리즘 집합 (앞 뒤 순서 옮 겨 다 니 는 재 귀 와 비 재 귀 알고리즘, 층 차 옮 겨 다 니 기 알고리즘)

11331 단어
   :
#ifndef BinaryTree_H
#define BinaryTree_H

#include <stdlib.h>
#include <stack>

class BinaryTree
{
private:
    typedef int Item;
    typedef struct TreeNode
    {
        Item        Node;
        TreeNode*   pRight;
        TreeNode*   pLeft;

        TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
            : Node(node)
            , pRight(pright)
            , pLeft(pleft)
        {
        }

    }TreeNode, *PTreeNode;

public:
    enum TraverseType
    {
        PREORDER    = 0,        //   
        INORDER        = 1,        //   
        POSTORDER    = 2,        //   
        LEVELORDER    = 3            //   
    };

    BinaryTree(Item Array[], int nLength);
    ~BinaryTree();

    PTreeNode GetRoot()
    {
        return m_pRoot;
    }

    //         
    //                ,       
    void Traverse(TraverseType traversetype, bool bRec = true);

private:
    PTreeNode   CreateTreeImpl(Item Array[], int nLength);
    void        DetroyTreeImpl(PTreeNode pTreenode);

    void        PreTraverseImpl(PTreeNode pTreenode);        //        
    void        InTraverseImpl(PTreeNode pTreenode);        //        
    void        PostTraverseImpl(PTreeNode pTreenode);        //        

    void        NoRecPreTraverseImpl(PTreeNode pTreenode);    //         
    void        NoRecInTraverseImpl(PTreeNode pTreenode);    //         
    void        NoRecPostTraverseImpl(PTreeNode pTreenode);    //         

    void        LevelTraverseImpl(PTreeNode pTreenode);

    PTreeNode   m_pRoot;        //    

    //   STL   stack           stack  
    typedef std::stack<BinaryTree::PTreeNode> TreeNodeStack;
};

#endif


    :
#include <iostream>
#include <assert.h>
#include <queue>
#include "BinaryTree.h"

BinaryTree::BinaryTree(Item Array[], int nLength)
    : m_pRoot(NULL)
{
    assert(NULL != Array);
    assert(nLength > 0);

    m_pRoot = CreateTreeImpl(Array, nLength);
}

BinaryTree::~BinaryTree()
{
    DetroyTreeImpl(m_pRoot);
}

//          
BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
{
    int mid = nLength / 2;
    PTreeNode p = new TreeNode(Array[mid]);

    if (nLength > 1)
    {
        p->pLeft    = CreateTreeImpl(Array, nLength / 2);
        p->pRight   = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
    }

    return p;
}

void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
{
    if (NULL != pTreenode->pLeft)
    {
        DetroyTreeImpl(pTreenode->pLeft);
    }
    if (NULL != pTreenode->pRight)
    {
        DetroyTreeImpl(pTreenode->pRight);
    }

    delete pTreenode;
    pTreenode = NULL;
}

//         
//                ,       
void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)
{
    switch (traversetype)
    {
    case PREORDER:    //   
        {            
            if (true == bRec)
            {
                std::cout << "       
"; PreTraverseImpl(m_pRoot); } else { std::cout << "
"; NoRecPreTraverseImpl(m_pRoot); } } break; case INORDER: // { if (true == bRec) { std::cout << "
"; InTraverseImpl(m_pRoot); } else { std::cout << "
"; NoRecInTraverseImpl(m_pRoot); } } break; case POSTORDER: // { if (true == bRec) { std::cout << "
"; PostTraverseImpl(m_pRoot); } else { std::cout << "
"; NoRecPostTraverseImpl(m_pRoot); } } break; case LEVELORDER: // { std::cout << "
"; LevelTraverseImpl(m_pRoot); } } std::cout << std::endl; } // void BinaryTree::PreTraverseImpl(PTreeNode pTreenode) { if (NULL == pTreenode) return; std::cout << "Item = " << pTreenode->Node << std::endl; PreTraverseImpl(pTreenode->pLeft); PreTraverseImpl(pTreenode->pRight); } // void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode) { if (NULL == pTreenode) return; TreeNodeStack NodeStack; PTreeNode pNode; NodeStack.push(pTreenode); while (!NodeStack.empty()) { while (NULL != (pNode = NodeStack.top())) // { std::cout << "Item = " << pNode->Node << std::endl; // NodeStack.push(pNode->pLeft); // } NodeStack.pop(); // if (!NodeStack.empty()) { pNode = NodeStack.top(); NodeStack.pop(); // NodeStack.push(pNode->pRight); // } } } // // void BinaryTree::InTraverseImpl(PTreeNode pTreenode) { if (NULL == pTreenode) return; if (NULL != pTreenode->pLeft) { InTraverseImpl(pTreenode->pLeft); } std::cout << "Item = " << pTreenode->Node << std::endl; if (NULL != pTreenode->pRight) { InTraverseImpl(pTreenode->pRight); } } // void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode) { if (NULL == pTreenode) return; TreeNodeStack NodeStack; PTreeNode pNode; NodeStack.push(pTreenode); while (!NodeStack.empty()) { while (NULL != (pNode = NodeStack.top())) // { NodeStack.push(pNode->pLeft); } NodeStack.pop(); if (!NodeStack.empty() && NULL != (pNode = NodeStack.top())) { std::cout << "Item = " << pNode->Node << std::endl; NodeStack.pop(); NodeStack.push(pNode->pRight); } } } // void BinaryTree::PostTraverseImpl(PTreeNode pTreenode) { if (NULL == pTreenode) return; if (NULL != pTreenode->pLeft) { PostTraverseImpl(pTreenode->pLeft); } if (NULL != pTreenode->pRight) { PostTraverseImpl(pTreenode->pRight); } std::cout << "Item = " << pTreenode->Node << std::endl; } // void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode) { if (NULL == pTreenode) return; TreeNodeStack NodeStack; PTreeNode pNode1, pNode2; NodeStack.push(pTreenode); pNode1 = pTreenode->pLeft; bool bVisitRoot = false; // , while (!NodeStack.empty()) { while (NULL != pNode1) // { NodeStack.push(pNode1); pNode1 = pNode1->pLeft; } pNode1 = NodeStack.top(); NodeStack.pop(); if (NULL == pNode1->pRight) // { std::cout << "Item = " << pNode1->Node << std::endl; pNode2 = pNode1; pNode1 = NodeStack.top(); if (pNode2 == pNode1->pRight) // { std::cout << "Item = " << pNode1->Node << std::endl; NodeStack.pop(); pNode1 = NULL; } else // { pNode1 = pNode1->pRight; } } else // { if (pNode1 == pTreenode && true == bVisitRoot) // { std::cout << "Item = " << pNode1->Node << std::endl; return; } else { if (pNode1 == pTreenode) { bVisitRoot = true; } NodeStack.push(pNode1); pNode1 = pNode1->pRight; } } } } // void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode) { if (NULL == pTreenode) return; // std::queue<PTreeNode> NodeQueue; PTreeNode pNode; NodeQueue.push(pTreenode); while (!NodeQueue.empty()) { pNode = NodeQueue.front(); NodeQueue.pop(); std::cout << "Item = " << pNode->Node << std::endl; if (NULL != pNode->pLeft) { NodeQueue.push(pNode->pLeft); } if (NULL != pNode->pRight) { NodeQueue.push(pNode->pRight); } } } : #include "BinaryTree.h" #include <stdio.h> #include <stdlib.h> #include <time.h> #include <iostream> void DisplayArray(int array[], int length) { int i; for (i = 0; i < length; i++) { printf("array[%d] = %d
", i, array[i]); } } void CreateNewArray(int array[], int length) { for (int i = 0; i < length; i++) { array[i] = rand() % 256 + i; } } int main() { int array[10]; srand(time(NULL)); // CreateNewArray(array, 10); DisplayArray(array, 10); BinaryTree *pTree = new BinaryTree(array, 10); // pTree->Traverse(BinaryTree::PREORDER); std::cout << "root = " << pTree->GetRoot()->Node << std::endl; std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl; std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl; pTree->Traverse(BinaryTree::PREORDER, false); // pTree->Traverse(BinaryTree::INORDER); std::cout << "root = " << pTree->GetRoot()->Node << std::endl; std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl; std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl; pTree->Traverse(BinaryTree::INORDER, false); // pTree->Traverse(BinaryTree::POSTORDER); std::cout << "root = " << pTree->GetRoot()->Node << std::endl; std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl; std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl; pTree->Traverse(BinaryTree::POSTORDER, false); // pTree->Traverse(BinaryTree::LEVELORDER); system("pause"); delete pTree; return 0; }

좋은 웹페이지 즐겨찾기