Status InOrderTraverse(BiTree T, Status(*Visit)(BiTree))
//T表示这个树的根节点的指针
//采用二叉链表储存结构,Visit是对结点操作的对应函数
//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit()失败,则操作失败
{
if (T){
BiTree lchild = T->lchild, rchild = T->rchild;
if (InOrderTraverse(lchild, Visit))
if (Visit(T))
if (InOrderTraverse(rchild, Visit))return OK;
return ERROR;
}
return OK;
}
Status InOrderTraverse_2(BiTree T, Status(*Visit)(BiTree))
//采用二叉链表储存结构,Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法,对每个数据元素调用函数Visit
{
stack<BiTree> sta;
sta.push(T);
BiTree p;
while (!sta.empty()){
while (p = sta.top())sta.push(p->lchild);
sta.pop();
if (!sta.empty()){
p = sta.top();
sta.pop();
if (!Visit(p))return ERROR;
sta.push(p->rchild);
}
}
return OK;
}
Status InOrderTraverse_3(BiTree T, Status(*Visit)(BiTree))
//采用二叉链表储存结构,Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法,对每个数据元素调用函数Visit
{
stack<BiTree> sta;
BiTree p = T;
while (p || !sta.empty()){
if (p){ sta.push(p); p = p->lchild; }
else{
p = sta.top();
sta.pop();
if (!Visit(p))return ERROR;
p = p->rchild;
}
}
return OK;
}
Status PostOrderTraverse(BiTree T, Status(*Visit)(BiTree))
//T表示这个树的根节点的指针
//采用二叉链表储存结构,Visit是对结点操作的对应函数
//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit()失败,则操作失败
{
if (T){
BiTree lchild = T->lchild, rchild = T->rchild;
if (PostOrderTraverse(lchild, Visit))
if (PostOrderTraverse(rchild, Visit))
if (Visit(T))return OK;
return ERROR;
}
return OK;
}
Status LevelOrderTraverse(BiTree T, Status(*Visit)(BiTree))
//T表示这个树的根节点的指针
//采用二叉链表储存结构,Visit是对结点操作的对应函数
//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
//一旦visit()失败,则操作失败
{
deque<BiTree> deq;
if (T){
deq.push_back(T);
while (!deq.empty()){
auto temp = deq.at(0);
Visit(temp);
if (temp->lchild)
deq.push_back(temp->lchild);
if (temp->rchild)
deq.push_back(temp->rchild);
deq.pop_front();
}
}
cout << endl;
return OK;
}
Status DestroyBiTree(BiTree &T)
//摧毁二叉树T
{
if (PreOrderTraverse(T, Destroy))return OK;
return FALSE;
}
主函数:
// 二叉链表.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"