二叉链表按先序建树再输出
就是按先序建立一个二叉链表，到叶子结点的下一个设置为‘#’，但是在按先序创建表的时候，又是遇到‘#’树T为空，结果输出树的时候，一到某一叶子结点就不能继续输出了，这个该怎么解决？代码如下
#ifndef BITREE1_H_INCLUDED
#define BITREE1_H_INCLUDED
//visit是输出函数
#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;
int top=0;//top为栈顶指针
while((T!=NULL)||(top>0))//大树不为空且栈顶指针存在
{
while(T!=NULL)//递归子树
{
visit(T->data);
s=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,p;
int f,r;//分别为头尾指针
q=T;//??
f=0;
r=1;
while(f<r)
{
p=q;//出队
visit(p->data);
if(p->lchild!=NULL)
q=p->lchild;//入队
if(p->rchild!=NULL)
q=p->rchild;//入队
}
}
#include <iostream>
#include <string>
#include "bitree1.h"
#include <cstdlib>//包含exit函数
using namespace std;
//按先序次序输入二叉树中结点的值（#表示空格），构造二叉链表表示的二叉树T
void CreatBitree(Bitree &T)//&为引用符号，
{
TElemType ch;
cin >> ch;
if(ch=='#')//空
T=NULL;
else
{
T=new BiTNode;//T=new Bitree;这个语句是错误的
if(!T)
exit(1);
T->data =ch;//生成根结点
cout<<"输入"<<T->data<<"左子树：";
CreatBitree(T->lchild);//构造左子树
cout<<"输入"<<T->data<<"右子树：";
CreatBitree(T->rchild);//构造右子树
cout<<"输入"<<T->data<<"完毕：";
}
}
void visit(TElemType a)//这个a为形参没有分配空间
{
if(a!='#')
cout << a;
}
int main()
{
Bitree T;
CreatBitree(T);//CreatBitree(&T);T本身就是一个地址
PreOrderTraverse(T,visit);
InOrderTraverse(T,visit);
LevelOrderTraverse(T,visit);
return 0;
}
页:
[1]