二叉链表表示的二叉树和一些基本操作(2)

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"

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/5ba31942bdb83b2a59d3dbb310ba7ad5.html