定义一个结构体来表达一個二叉树的节点的结构：

struct Node {

int self; // 数据

Node *left; // 左孩子

Node *right; // 右孩子

};

那么我们在搜索一个树的时候，从一个节点开始，能首先获取的是它的两个子节点。例如：

“

A

B C

D E F G

”

A是第一个访问的，然后顺序是B和D、然后是E。然后再是C、F、G。那么我们怎么来保证这个顺序呢？

这里就应该用堆栈的结构，因为堆栈是一个后进先出(LIFO)的顺序。通过使用C++的STL，下面的程序能帮助理解：

const int TREE_SIZE = 9;

std::stack unvisited;

Node nodes[TREE_SIZE];

Node *current;

//初始化树

for (int i = 0; i < TREE_SIZE; i++) {

nodes[i].self = i;

int child = i * 2 + 1;

if (child < TREE_SIZE) // Left child

nodes[i].left = &nodes[child];

else

nodes[i].left = NULL;

child++;

if (child < TREE_SIZE) // Right child

nodes[i].right = &nodes[child];

else

nodes[i].right = NULL;

}

unvisited.push(&nodes[0]); //先把0放入UNVISITED stack

// 树的深度优先搜索在二叉树的特例下，就是二叉树的先序遍历操作（这里是使用循环实现）

// 只有UNVISITED不空

while (!unvisited.empty()) {

current = (unvisited.top()); //当前访问的

unvisited.pop();

if (current->right != NULL)

unvisited.push(current->right );

if (current->left != NULL)

unvisited.push(current->left);

cout << current->self << endl;

}