数据结构学习（C++）——二叉树【3】 (转)

递归遍历与非递归遍历

#include

using namespace std;

#include

#include

#include "BSTree.h"

#include "Timer.h"

#define random(num)  (rand() % (num))

#define randomize()  srand((unsigned)time(NULL))

#define NODENUM 200000//node number

int data[NODENUM];

void zero(int &t) { t = 0; }

int main()

{

BSTree a; Timer t; randomize(); int i;

for (i = 0; i < NODENUM; i++) data[i] = i;

for (i = 0; i < NODENUM; i++) swap(data[i], data[random(NODENUM)]);//random swap

t.start(); for (i = 0; i < NODENUM; i++) a.insert(data[i]);

cout << "Insert time: " << t.GetTime() << "tNode number: " << NODENUM << endl;

t.start(); for (a.first(); a.get() != NULL; a.next()) a.get()->data = 0;

cout << "Non-Stack time: " << t.GetTime() << endl;

t.start(); a.LevelOrder(zero); cout << "LevlOrder time: " << t.GetTime() << endl;

t.start(); a.PreOrder(zero); cout << " PreOrder time: " << t.GetTime() << endl;

t.start(); a.InOrder(zero); cout << "  InOrder time: " << t.GetTime() << endl;

t.start(); a.PostOrder(zero); cout << "PostOrder time: " << t.GetTime() << endl;

return 0;

}

#ifndef Timer_H

#define Timer_H

#include <windows.h>

class Timer

{

public:

Timer() { QueryPerformanceFrequency(&Frequency); }

inline void start() { QueryPerformanceCounter(&timerB); }

inline double GetTime()

{

QueryPerformanceCounter(&timerE);

return (double)(timerE.QuadPart - timerB.QuadPart) / (double)Frequency.QuadPart * 1000.0;

}

private:

LARGE_INTEGER timerB, timerE, Frequency;

};

#endif

Insert time: 868.818  Node number: 200000

Non-Stack time: 130.811

LevlOrder time: 148.438

PreOrder time: 125.47

InOrder time: 129.125

PostOrder time: 130.914

Insert time: 1355.69  Node number: 200000

Non-Stack time: 207.086

LevlOrder time: 766.023

PreOrder time: 183.287

InOrder time: 179.835

PostOrder time: 190.674

栈模拟递归的好处是节省了堆栈

Insert time: 27555.5  Node number: 15000

Non-Stack time: 16.858

LevlOrder time: 251.036

• 博文量
3984
• 访问量
7339251