이 진 트 리 옮 겨 다 니 기 알고리즘 집합 (앞 뒤 순서 옮 겨 다 니 는 재 귀 와 비 재 귀 알고리즘, 층 차 옮 겨 다 니 기 알고리즘)
:
#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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.