アルゴリズム論10.4-3 O(n)二叉樹は再帰的ではない.
一、テーマ
O(n)時間の不再帰過程を書き出してください.与えられたn接合点二叉樹の各結点のキーワードを出力します.補助データ構造としてスタックを利用することができます.
二、疑似コード
三、コード
1.main.cpp
O(n)時間の不再帰過程を書き出してください.与えられたn接合点二叉樹の各結点のキーワードを出力します.補助データ構造としてスタックを利用することができます.
二、疑似コード
01.TREE-PRINT(T, S)
02. 1 print key[T]
03. 2 PUSH(S, T)
04. 3 while true
05. 4 if left[T] != NIL
06. 5 then T <- left[T]
07. 6 else
08. 7 do
09. 8 T = POP(S)
10. 9 if T = NIL
11.10 then return
12.11 while left[T] = NIL
13.12 T <- right[T]
三、コード
1.main.cpp
#include "caselib.h"
int main()
{
CTestFrame test;
//test.inputNullWillShowErrorHint();
test.oneNoteWillSecuss();
test.rootWithLeftChildWillSecuss();
test.rootWithRightChildWillSecuss();
test.treeWithGraph10_4_1WillSecuss();
test.onlyLeftChildWillSecuss();
getchar();
return 0;
}
2.caselib.h#include <vector>
#include <string>
using namespace std;
class CTestFrame
{
typedef bool (CTestFrame::*pFunc)();
vector<int> outputDataVec;
vector<int> inputDataVec;
vector<int> expectOutputDataVec;
void prepare(int* inputData, int *expectOutputData, int inLen, int outLen);
bool testStep();
void backup();
void assertTrue(CTestFrame::pFunc testedFunc, string errorPrint);
public:
void inputNullWillShowErrorHint();
void oneNoteWillSecuss();
void rootWithLeftChildWillSecuss();
void rootWithRightChildWillSecuss();
void treeWithGraph10_4_1WillSecuss();
void onlyLeftChildWillSecuss();
};
3.caselib.cpp#include "funclib.h"
#include "caselib.h"
void CTestFrame::prepare(int* inputData, int *expectOutputData, int inLen, int outLen)
{
int dataNum = 0;
for(int i = 0; i < inLen; i++)
{
inputDataVec.push_back(inputData[i]);
if(inputData[i] != NONODE)
dataNum++;
}
//assert(dataNum == outLen)
for(int i = 0; i < outLen; i++)
expectOutputDataVec.push_back(expectOutputData[i]);
}
bool CTestFrame::testStep()
{
bool ret = false;
biTree *pBiTree = new biTree(inputDataVec);
outputDataVec = pBiTree->nonRecursiveTraversal();
delete pBiTree;
if(outputDataVec.size() != expectOutputDataVec.size())
ret = false;
else
{
ret = true;
for(int i =0; i < outputDataVec.size(); i++)
{
if(outputDataVec[i] != expectOutputDataVec[i])
{
ret = false;
break;
}
}
}
return ret;
}
void CTestFrame::backup()
{
inputDataVec.clear();
outputDataVec.clear();
expectOutputDataVec.clear();
}
void CTestFrame::assertTrue(CTestFrame::pFunc testedFunc, string errorPrint)
{
if((this->*testedFunc)() != true)
{
cout<<"failed: "<<errorPrint<<endl;
}
}
void CTestFrame::oneNoteWillSecuss()
{
int inputData[1] = {5};
int expectOutputData[1] = {5};
prepare(inputData, expectOutputData, 1, 1);
assertTrue(&CTestFrame::testStep, "The result is not correct when the bi-tree contains only one note");
backup();
}
void CTestFrame::rootWithLeftChildWillSecuss()
{
int inputData[2] = {5,
10};
int expectOutputData[2] = {5, 10};
prepare(inputData, expectOutputData, 2, 2);
assertTrue(&CTestFrame::testStep, "A root with a left node will not secuss");
backup();
}
void CTestFrame::rootWithRightChildWillSecuss()
{
int inputData[3] = {5,
NONODE, 10};
int expectOutputData[2] = {5, 10};
prepare(inputData, expectOutputData, 3, 2);
assertTrue(&CTestFrame::testStep, "A root with a right node will not secuss");
backup();
}
void CTestFrame::treeWithGraph10_4_1WillSecuss()
{
int inputData[10] = {18,
12, 10,
7, 4, 2, 21,
NONODE, NONODE, 5};
int expectOutputData[8] = {18, 12, 7, 4, 5, 10, 2, 21};
prepare(inputData, expectOutputData, 10, 8);
assertTrue(&CTestFrame::testStep, "test case with graph in Exercise 10.4_1 will fail");
backup();
}
void CTestFrame::onlyLeftChildWillSecuss()
{
int inputData[8] = {1,
2, NONODE,
3, NONODE, NONODE, NONODE,
4};
int expectOutputData[4] = {1, 2, 3, 4};
prepare(inputData, expectOutputData, 8, 4);
assertTrue(&CTestFrame::testStep, "only left child will false");
backup();
}
4.funclib.h#include <iostream>
#include <vector>
using namespace std;
#define NONODE -0x7FFFFFF
struct biTreeNode
{
int key;
biTreeNode *pLeftChild;
biTreeNode *pRightChild;
biTreeNode *pParent;
biTreeNode(){}
~biTreeNode();
biTreeNode(int x):key(x),pLeftChild(NULL),pRightChild(NULL){}
void visit(vector<int> *pDataVec);
bool isChildExist(bool leftOrRight);
};
//
class biTree
{
biTreeNode *pRootNode;
public:
biTree(const vector<int> nodeKeyVec);
~biTree();
vector<int> nonRecursiveTraversal();
};
5 funclib.cpp#include "funclib.h"
#include <queue>
#include<stack>
#define LEFT 0
#define RIGHT 1
void addNodeToChild(biTreeNode* pCurrentNode, biTreeNode* pChild, bool leftOrRight);
biTreeNode::~biTreeNode()
{
if(pLeftChild != NULL)
delete pLeftChild;
if(pRightChild != NULL)
delete pRightChild;
}
void biTreeNode::visit(vector<int> *pDataVec)
{
pDataVec->push_back(key);
}
bool biTreeNode::isChildExist(bool leftOrRight)
{
bool ret = false;
if(leftOrRight == LEFT && pLeftChild != NULL)
ret = true;
if(leftOrRight == RIGHT && pRightChild != NULL)
ret = true;
return ret;
}
biTree::~biTree()
{
if(pRootNode != NULL)
delete pRootNode;
}
biTree::biTree(const vector<int> nodeKeyVec)
{
pRootNode = new biTreeNode(nodeKeyVec[0]);
queue<biTreeNode*> nodeQueue;
nodeQueue.push(pRootNode);
for(int i = 1; i < nodeKeyVec.size(); i = i+2)
{
biTreeNode *pCurrentNode = nodeQueue.front();
nodeQueue.pop();
if(pCurrentNode != NULL && i < nodeKeyVec.size() && nodeKeyVec[i] != NONODE)
{
biTreeNode* pLeftChild = new biTreeNode(nodeKeyVec[i]);
addNodeToChild(pCurrentNode, pLeftChild, LEFT);
nodeQueue.push(pLeftChild);
}
else
nodeQueue.push(NULL);
if(pCurrentNode != NULL && i+1 < nodeKeyVec.size() && nodeKeyVec[i+1] != NONODE)
{
biTreeNode* pRightChild = new biTreeNode(nodeKeyVec[i+1]);
addNodeToChild(pCurrentNode, pRightChild, RIGHT);
nodeQueue.push(pRightChild);
}
else
nodeQueue.push(NULL);
}
}
vector<int> biTree::nonRecursiveTraversal()
{
vector<int> retDataVec;
stack<biTreeNode *> nodeStack;
biTreeNode *pCurrentNode = pRootNode;
while(true)
{
pCurrentNode->visit(&retDataVec);
nodeStack.push(pCurrentNode);
if(pCurrentNode->isChildExist(LEFT))
pCurrentNode = pCurrentNode->pLeftChild;
else
{
do{
if(nodeStack.empty() == true)
return retDataVec;
pCurrentNode = nodeStack.top();
nodeStack.pop();
}
while(pCurrentNode->isChildExist(RIGHT));
pCurrentNode = pCurrentNode->pRightChild;
}
}
}
void addNodeToChild(biTreeNode* pCurrentNode, biTreeNode* pChild, bool leftOrRight)
{
if(leftOrRight == LEFT)
pCurrentNode->pLeftChild = pChild;
else
pCurrentNode->pRightChild = pChild;
pChild->pParent = pCurrentNode;
}