按先序序列输入字符序列(其中逗号表示空节点),输出该二叉树的层次遍历序列。
#include <iostream>
#define END ','//表示空节点
using namespace std;
typedef char Elem_Type;
typedef struct BiTree
{
Elem_Type data;
struct BiTree *Lchild;
struct BiTree *Rchild;
}BiTree;
BiTree *CreateBiTree(void)
{
Elem_Type value;cin>>value;
if(value == END)
return NULL;
BiTree *root = new BiTree;
root->data = value;
root->Lchild = CreateBiTree();
root->Rchild = CreateBiTree();
return root;
}
int BiTreeDepth(BiTree *root)
{
if( !root )
return 0;
return max( BiTreeDepth(root->Lchild),BiTreeDepth(root->Rchild) ) + 1;
}
void PrintBiTree(BiTree *root,int level)
{
if( !root )//不写这个会有段错误发生
return;
if(level == 1 )
cout<<root->data;
else
{
PrintBiTree(root->Lchild,level - 1);
PrintBiTree(root->Rchild,level - 1);
}
}
void LeveOrderTraverse(BiTree *root)
{
int depth = BiTreeDepth(root);
for(int i=1; i <= depth; i++)
{
PrintBiTree(root,i);
cout<<endl;
}
}
int main(void)
{
BiTree *root = CreateBiTree();
LeveOrderTraverse(root);
return 0;
}
二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm