C++二叉树的建立与遍历

/************************************************************************/
/* coder:huifeng00
/* 时间：2010-5-16 下午5点
/* 功能：实现空格为虚节点的二叉树的建立，并且格式化打印二叉树
/************************************************************************/

#include
#include

typedef struct node
{
char data;
struct node *left,*right;
}Node,*PNode;
PNode createBtree(PNode root)//创建二叉树，控制台下输入，基于先序遍历输入
{
char data;
scanf("%c",&data);
if (data==' ')
{
root=NULL;
return root;
}
root = (PNode)malloc(sizeof(Node));
root->data = data;
root->left = createBtree(root->left);
root->right = createBtree(root->right);

return root;
}

void printFormat(PNode root)//格式化打印二叉树
{
static i = 0;//这是控制格式化。
int j;
if (root==NULL)
{
return;
}
for (j=0;j {
printf(" ");
}
printf("%c\n",root->data);
i++;
printFormat(root->left);
printFormat(root->right);
i--;
}
int main()
{
PNode root=NULL;
root = createBtree(root);
printFormat(root);
return 0;
}
程序如上。
虚节点用空格输入的。例如你输入
先序遍历
234空格空格5空格6空格空格7空格空格回车就可以看到结果。
另外你说的输出二叉树图形。
我是这样输出的。第1列是最高节点，就是根。
第2列是第2层节点。
格式话是通过缩进完成的。
这个图形可以参考下面的地址。
http://hi.baidu.com/huifeng00/blog/item/c1e37a4d59310b3caec3ab32.html
我空间曾经写过大量的关于二叉树和多叉树的程序，可以参考下，在数据结构类别下。
这个程序是可以运行的，运行工具是vc6.0.
如还有疑问，可以空间留言，或hi我。

以下是我以前做的一个二叉树的图形化输出函数楼主可做参考：
template
void BinTree::displayTree(BinTreeNode* t,int datawidth, int screenwidth)
{
if(t==NULL)
cout<<"error:Atemping to diaplay a tree not existed!"< Queue *> q;
Queue QI;
BinTreeNode * currNode;
Info currInfo;
int units(screenwidth/datawidth);
int offset=units/2;
//当前结点的列坐标
int currlevel=-1;
//当前结点的同层的前一结点的行坐标
int prex;

//如果树空，退出
if(t==NULL) return;

//在队列q中插入结点来初始化队列
q.QInsert(t);
//在队列QI中插入结点来初始化队列
QI.QInsert(Info(offset,0));

//继续迭代过程，直到队列为空
while(!q.QEmpty())
{
//从队列中删除前端结点，并访问节点
currNode=q.QFront();
q.QDelete();
currInfo=QI.QFront();
QI.QDelete();
if(currInfo.yLevel!=currlevel)
{
//换两行
cout<<"\n\n";
//新行，起始位置为0
prex=0;
//子女结点的偏移量为上层节点的1/2
offset/=2;
//更新当前节点坐标层次
currlevel=currInfo.yLevel;
}

//在相应位置输出接点队列头部元素的值，类型为T
//假定类型T定义了合适的<<操作符
cout<data;
if(currNode->left!=NULL)
{
//左子结点入队
q.QInsert(currNode->left);
//左子结点位置信息入队
QI.QInsert(Info(currInfo.xIndent-offset,currInfo.yLevel+1));
}
if(currNode->right!=NULL)
{
//右子结点入队
q.QInsert(currNode->right);
//右子结点位置信息入队
QI.QInsert(Info(currInfo.xIndent+offset,currInfo.yLevel+1));
}
prex=currInfo.xIndent;
}
cout<}