数据结构学习（C++）之二叉树

　　递归遍历与非递归遍历

　　在没有树的慨念，对递归的理解总是很困难，因为不能提出有说服力的例子，只是阐述了“递归是一种思想”。但只要能能让你建立“递归是一种思想”这个观念，我的努力就没有白费。现在，讲完了二叉搜索树，终于有了能说明问题的例子了。按照前面提供的代码，应该能调试通过下面的程序。

#include <iostream> using namespace std; #include <stdlib.h> #include <time.h> #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<int> 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; }

　　以下是timer.h的内容

#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

　　上面的程序中，层次遍历用到的是队列，这应该可以代表用栈消解递归的情况，在我的机器C500上运行的结果是：

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

　　以上是VC6的release版的结果，时间单位是ms，不说明会有人认为是死机了，^_^。可以看出，递归遍历实际上并不慢，相反，更快一些，而debug版的结果是这样的：

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