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;
}