数据结构二叉链表

鱼小伟

就是用以下的头文件怎么使用主函数实现已知中序和先序实现后序和层次的输出


#ifndef BITREE1_H_INCLUDED
#define BITREE1_H_INCLUDED
#include <iostream>
typedef char TElemType;//给char类型起别名

struct BiTNode //定义二叉树结构类型
{
    TElemType data;//字符元素
    BiTNode *lchild,*rchild;//定义左右孩子
};

typedef BiTNode *Bitree;//定义二叉树的结构指针；

void InitBitree(Bitree &T);//初始化二叉树
void CreatBitree(Bitree &T);//创建二叉树
void PreOrderTraverse(Bitree T,void(*visit)(TElemType));//递归前序遍历
void PreOrderTraversel(Bitree T,void(*visit)(TElemType));//??非递归前序遍历
void InOrderTraverse(Bitree T,void(*visit)(TElemType));//递归中序遍历
void PostOrderTraverse(Bitree T,void(*visit)(TElemType));//递归后序遍历
void LevelOrderTraverse(Bitree T,void(*visit)(TElemType));//层次遍历


//将T初始化为空的二叉树
void InitBitree(Bitree &T)
{
    T=NULL;
}

//先序遍历递归T,对每个结点调用函数visit一次且一次
void PreOrderTraverse(Bitree T,void(*visit)(TElemType))
{
    if(T);//不为空
    {
        visit(T->data);//先访问根结点 ??为什么T中元素的两种访问运算符均成立
        PreOrderTraverse(T->lchild,visit);//再先序遍历左子树
        PreOrderTraverse(T->rchild,visit);//然后先序遍历右子树
    }
}

//先序遍历二叉树的非递归算法（利用栈），对每个数据元素调用函数visit
void PreOrderTraversel(Bitree T,void(*visit)(TElemType))
{
    Bitree s[100];
    int top=0;//top为栈顶指针
    while((T!=NULL)||(top>0))//大树不为空且栈顶指针存在
    {
        while(T!=NULL)//递归子树
        {
            visit(T->data);
            s[top++]=T;
            T=T->lchild;
        }
        T=s[--top];//？？
        T=T->rchild;
    }
}

//中序递归遍历T,对每个结点调用函数Visit一次且仅一次
void InOrderTraverse(BiTree T, void(*visit)(TElemType))
{
    if(T)
    {
        InOrderTraverse(T->lchild, visit); // 先中序遍历左子树
        visit(T->data); // 再访问根结点
        InOrderTraverse(T->rchild, visit); // 最后中序遍历右子树
    }
}

//后序递归遍历T,对每个结点调用函数Visit一次且仅一次
void PostOrderTraverse(BiTree T, void (*visit)(TElemType))
{
    if(T)
    {
        PostOrderTraverse(T->lchild, visit); // 后序遍历左子树
        PostOrderTraverse(T->rchild, visit); // 再后序遍历右子树
        visit(T->data); // 最后访问根结点
    }
}

//层次遍历T(利用队列）,对每个结点调用函数visit一次且仅一次
void LevelOrderTraverse(Bitree T,void(*visit)(TElemType))
{
    Bitree q[100],p;
    int f,r;//分别为头尾指针
    q[0]=T;//??
    f=0;
    r=1;
    while(f<r)
    {
        p=q[f++];//出队
        visit(p->data);
        if(p->lchild!=NULL)
            q[r++]=p->lchild;//入队
        if(p->rchild!=NULL)
            q[r++]=p->rchild;//入队
    }
}

//按先序次序输入二叉树中结点的值（#表示空格），构造二叉链表表示的二叉树T
void CreatBitree(Bitree &T)
{
    TElemType ch;
    cin >> ch;
    if(ch=='#')//空
    T=NULL;
     else
     {
         T=new Bitree;
         if(!T)
            exit(1);
        T->data=ch;//生成根结点
        CreatBitree(T->lchild);//构造左子树
        CreatBitree(T->rchild);//构造右子树
     }
}

#endif // BITREE1_H_INCLUDED

常德水鱼村

支持楼主！