二叉樹遍歷算法集合(前中后序遍歷的遞歸和非遞歸算法,層序遍歷算法)
費了兩天時間寫的,包括前中后序遍歷的遞歸和非遞歸算法,還有層序遍歷總共2*3 + 1 = 7中遍歷二叉樹的算法,感覺其中后序遍歷的非遞歸算法比較困難,想了很久最后的實現還是不夠優雅,請大家指正~~
總共三個文件,一個頭文件,一個對應的cpp文件,還有一個用于測試的文件.
頭文件:

/**//********************************************************************
????created:????2006/07/04
????filename:?????BinaryTree.h
????author:????????李創
????????????????http://www.shnenglu.com/converse/

????purpose:????演示二叉樹的算法
*********************************************************************/

#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
實現文件:

/**//********************************************************************
????created:????2006/07/04
????filename:?????BinaryTree.cpp
????author:????????李創
????????????????http://www.shnenglu.com/converse/

????purpose:????演示二叉樹的算法
*********************************************************************/

#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?<<?"遞歸前序遍歷樹\n";
????????????????PreTraverseImpl(m_pRoot);
????????????}
????????????else

????????????
{
????????????????std::cout?<<?"非遞歸前序遍歷樹\n";
????????????????NoRecPreTraverseImpl(m_pRoot);
????????????}
????????}
????????break;

????case?INORDER:????//?中序

????????
{????????????
????????????if?(true?==?bRec)

????????????
{
????????????????std::cout?<<?"遞歸中序遍歷樹\n";
????????????????InTraverseImpl(m_pRoot);
????????????}
????????????else

????????????
{
????????????????std::cout?<<?"非遞歸中序遍歷樹\n";
????????????????NoRecInTraverseImpl(m_pRoot);
????????????}
????????}
????????break;

????case?POSTORDER:????//?后序

????????
{????????????
????????????if?(true?==?bRec)

????????????
{
????????????????std::cout?<<?"遞歸后序遍歷樹\n";
????????????????PostTraverseImpl(m_pRoot);
????????????}
????????????else

????????????
{
????????????????std::cout?<<?"非遞歸后序遍歷樹\n";
????????????????NoRecPostTraverseImpl(m_pRoot);
????????????}
????????}
????????break;

????case?LEVELORDER:????//?層序

????????
{
????????????std::cout?<<?"層序遍歷樹\n";
????????????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);
????????}????
????}
}
測試文件:

/**//********************************************************************
????created:????2006/07/04
????filename:?????main.cpp
????author:????????李創
????????????????http://www.shnenglu.com/converse/

????purpose:????測試二叉樹的算法
*********************************************************************/

#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\n",?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;
}
總共三個文件,一個頭文件,一個對應的cpp文件,還有一個用于測試的文件.
頭文件:























































































實現文件:




























































































































































































































































































































































































































測試文件:





















































































posted on 2006-07-08 15:21 那誰 閱讀(20260) 評論(9) 編輯 收藏 引用 所屬分類: 算法與數據結構