层次遍历建立二叉树

zhunhuan38 · 2018-4-30 01:53:01

你可以参考严蔚敏的数据结构与算法c语言描述，其中对二叉树的描述很清楚，至于层次输入你可以参考后面有个堆的遍历，有个构造队列做暂存器的方法遍历，其中

072jncgnt · 2018-4-30 01:53:02

#include
#include
//二叉链表的结构类型定义
const int maxsize=1024;
typedef char datatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}bitree;

bitree*creattree();
void preorder(bitree*);

void main()
{
bitree*pb;
pb=creattree();
preorder(pb);
printf("\n");
}

//二叉树的建立
bitree*creattree()
{
char ch;
bitree*Q[maxsize];
int front,rear;
bitree*root,*s;
root=NULL;
front=1;rear=0;
printf("按层次输入二叉树，虚结点输入'@'，以'#'结束输入：\n");
while((ch=getchar())!='#')
{
  s=NULL;
  if(ch!='@')
  {
s=(bitree*)malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
  }
  rear++;
  Q[rear]=s;
  if(rear==1)root=s;
  else
  {
if(s&&Q[front])
if(rear%2==0)Q[front]->lchild=s;
else Q[front]->rchild=s;
if(rear%2==1)front++;
  }
}
return root;
}

//先序遍历按层次输出二叉树
void preorder(bitree*p)
{
if(p!=NULL)
{
  printf("%c",p->data);
  if(p->lchild!=NULL||p->rchild!=NULL)
  {
printf("(");
preorder(p->lchild);
if(p->rchild!=NULL)printf(",");
preorder(p->rchild);
printf(")");
  }
}
}

//这个是不论输入多少个结点的，我想你应该会改成10个的吧，我就不改了。
//你所说的是先序遍历，就是最后的这个子程序

qq1209 · 2018-4-30 01:53:03

我用java写的
结点类
package聽Tree;

public聽class聽BTNode聽{
private聽E聽data;
private聽BTNode聽left,聽right;

public聽BTNode(E聽initialData,BTNode聽initialLeft,BTNode聽initialRight){
  left=initialLeft;
  right=initialRight;
  data=initialData;
}

public聽E聽getData()
{
  return聽data;
}

public聽BTNode聽getLeft()
{
  return聽left;
}

public聽E聽getLeftmostData()
{
  if(left==null)
return聽data;
  else聽
return聽left.getLeftmostData();
}

public聽BTNode聽getRight()
{
  return聽right;
}

public聽E聽getRightmostData()
{
  if(right==null)
return聽data;
  else聽
return聽right.getRightmostData();
}

//中序序遍历
public聽void聽inorderPrint()
{
  if(left!=null)
left.inorderPrint();
  System.out.println(data);
  if(right!=null)
right.inorderPrint();
}

//中序聽遍历
public聽void聽postorderPrint()
{
  if(left!=null)
left.postorderPrint();
  if(right!=null)
right.postorderPrint();
  System.out.println(data);
}

//前序遍历
public聽void聽preorderPrint()
{
  System.out.println(data);
  if(left!=null)
left.preorderPrint();
  if(right!=null)
right.preorderPrint();
}

public聽boolean聽isLeaf()
{
  return(left==null)&&(right==null);
}

public聽void聽print(int聽depth)
{
  int聽i;
  for(i=1;i

湘_羊 · 2018-4-30 01:53:04

就是一层一层的来，从上到下，全部遍历完

guojianlin1985 · 2018-4-30 01:53:05

http://baike.baidu.com/view/549587.htm

层次遍历建立二叉树

5 个回复