codeblocksツリーの遍歴再帰と非再帰
5032 ワード
#ifndef RECORD_H
#define RECORD_H
#include <iostream>
using namespace std;
class Record
{
public:
Record();
Record(string name, int age);
virtual ~Record();
void Display();
protected:
private:
public:
string name;
int age;
};
#endif // RECORD_H
#ifndef TREE_H
#define TREE_H
#include "TreeNode.h"
class Tree
{
public:
Tree();
virtual ~Tree();
void visit(TreeNode* node);
void PreOrderVisit(TreeNode* node);
void InOrderTraverse(TreeNode* root);
protected:
private:
public:
TreeNode* headNode;
};
#endif // TREE_H
#ifndef TREENODE_H
#define TREENODE_H
#include "Record.h"
class TreeNode
{
public:
TreeNode();
TreeNode(Record record);
virtual ~TreeNode();
void Display();
protected:
private:
public:
Record treeRec;
TreeNode* leftNode;
TreeNode* rightNode;
};
#endif // TREENODE_H
#include "../include/Record.h"
Record::Record()
{
}
Record::Record(string name, int age)
{
this->name = name;
this->age = age;
}
Record::~Record()
{
//dtor
}
void Record::Display()
{
cout<<"ÐÕÃû£º"<<name<<" "<<"ÄêÁ䣺"<<age<<endl;
}
#include "../include/TreeNode.h"
TreeNode::TreeNode()
{
}
TreeNode::TreeNode(Record record)
{
treeRec = record;
leftNode = NULL;
rightNode = NULL;
}
TreeNode::~TreeNode()
{
//dtor
}
void TreeNode::Display()
{
cout<<"ÐÕÃû£º"<<treeRec.name<<" "<<"ÄêÁ䣺"<<treeRec.age<<endl;
}
#include "../include/Tree.h"
#include "../include/Record.h"
#include "../include/TreeNode.h"
#include<Stack>
using namespace std;
Tree::Tree()
{
Record rc0("jiji",0);
Record rc1("jiji",1);
Record rc2("jiji",2);
Record rc3("jiji",3);
Record rc4("jiji",4);
Record rc5("jiji",5);
TreeNode* treeNode0 = new TreeNode(rc0);
TreeNode* treeNode1 = new TreeNode(rc1);
TreeNode* treeNode2 = new TreeNode(rc2);
TreeNode* treeNode3 = new TreeNode(rc3);
TreeNode* treeNode4 = new TreeNode(rc4);
TreeNode* treeNode5 = new TreeNode(rc5);
headNode = treeNode0;
treeNode0->leftNode = treeNode1;
treeNode0->rightNode = treeNode2;
treeNode2->leftNode = treeNode3;
treeNode2->rightNode = treeNode4;
treeNode3->rightNode = treeNode5;
}
Tree::~Tree()
{
//dtor
}
void Tree::visit(TreeNode* node)
{
if(node != NULL) {
node->Display();
}
}
void Tree::PreOrderVisit(TreeNode* node) //
{
if(node != NULL) {
node->Display();
PreOrderVisit(node->leftNode);
PreOrderVisit(node->rightNode);
}
}
void Tree::InOrderTraverse(TreeNode* root) //
{
TreeNode* temp = root->leftNode;
stack<TreeNode*>* nstack = new stack<TreeNode*>(); // , 。
nstack->push(root);
while (nstack->size() > 0 || temp != NULL)
{
if (temp != NULL) {
nstack->push(temp);
temp = temp->leftNode;
}
else {
temp = nstack->top();
nstack->pop();
temp->Display();
temp = temp->rightNode;
}
}
}
#include <iostream>
#include "./include/Record.h"
#include "./include/TreeNode.h"
#include "./include/Tree.h"
using namespace std;
int main()
{
Tree tree;
tree.PreOrderVisit(tree.headNode);
cout<<endl;
tree.InOrderTraverse(tree.headNode);
return 0;
}