二叉树的遍历
基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？到了后面才明白，这是不同的应用需要的。例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。
实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性，这些遍历方法能很清晰的表达。
1. 前序遍历
public:
void PreOrder(void (*visit)(T &data) = print) { PreOrder(root, visit); }
private:
void PreOrder(BTNode<T>* p, void (*visit)(T &data))
{
if (p){ visit(p->data); PreOrder(p->left, visit); PreOrder(p->right, visit); }
} |
2. 中序遍历
public:
void InOrder(void (*visit)(T &data) = print) { InOrder(root, visit); }
private:
void InOrder(BTNode<T>* p, void (*visit)(T &data))
{
if (p){ InOrder(p->left, visit); visit(p->data); InOrder(p->right, visit); }
}
|
3. 后序遍历
public:
void PostOrder(void (*visit)(T &data) = print) { PostOrder(root, visit); }
private:
void PostOrder(BTNode<T>* p, void (*visit)(T &data))
{
if (p){ PostOrder(p->left, visit); PostOrder(p->right, visit); visit(p->data); }
}
|
4. 层次遍历
void LevelOrder(void (*visit)(T &data) = print)
{
queue< BTNode<T>* > a; BTNode<T>* p = root;//记得#include<queue>
while (p)
{
visit(p->data);
if (p->left) a.push(p->left); if (p->right) a.push(p->right);
if (a.empty()) break; p = a.front(); a.pop();
}
}
附注：缺省的visit函数print如下
private:
static void print(T &data) { cout << data << ' ';｝ |
5. 不用栈的非递归中序遍历
当有parent指针时，可以不用栈实现非递归的中序遍历，书上提到了有这种方法，但没给出例程。
public:
BTNode<T>* next()
{
if(!current) return NULL;
if (current->right) { current = current->right; while (current->left) current = current->left; }
else
{
BTNode<T>* y = current->parent;
while (y && current == y->right) {current = y; y = y->parent; }
current = y;
}
return current;
}
private:
BTNode<T>* current; |
上面的函数能使current指针向前移动一个位置，如果要遍历整棵二叉树，需要使current指向中序序列的第一个节点，例如下面的成员函数：
public:
void first() { current = root; while (current->left) current = current->left; } |
2/2 首页 上一页 1 2 |
