求一个二叉树层次遍历的程序~~~
建立二叉树，层序遍历（ 用递归或非递归的方法都可以）。
任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数。
[解决办法]
typedef struct qnode
{
stree *data;
struct qnode *next;
} qtree; //链队节点类型<用于层次遍历>
typedef struct
{
qtree *front;
qtree *rear;
} lqueue; //<用于层次遍历>
static int enqueue(lqueue *,stree *);//入队 <用于层次遍历>
static stree *dequeue(lqueue *); //出队<用于层次遍历>
int levorder(stree *t,void (*callback)(eletype)) //层次遍历
{
lqueue q= {NULL,NULL};
stree *temp;
if(t==NULL) return 0;
if(enqueue(&q,t)==-1) return -1;
while(q.front!=NULL)
{
temp=dequeue(&q);
callback(temp->element);
if(temp->left!=NULL)
if(enqueue(&q,temp->left)==-1) return -1;
if(temp->right!=NULL)
if(enqueue(&q,temp->right)==-1) return -1;
}
return 1;
}
static int enqueue(lqueue *q,stree *e)//入队 <用于层次遍历>
{
qtree *p;
if((p=(qtree *)malloc(sizeof(qtree)))==NULL)
{
fprintf(stderr,"%s\n","内存分配失败...");
return -1;
}
p->data=e;
p->next=NULL;
if(q->front==NULL)
q->front=q->rear=p;
else
{
q->rear->next=p;
q->rear=p;
}
return 1;
}
static stree *dequeue(lqueue *q) //出队<用于层次遍历>
{
qtree *p;
stree *e;
if(q->front==NULL)
{
fprintf(stderr,"%s\n","空队,无法删除...");
return NULL;
}
e=q->front->data;
p=q->front;
q->front=q->front->next;
free(p);
if(q->front==NULL)
q->rear=NULL;
return e;
}
[解决办法]
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.Serialization;
namespace Binary_Tree
{
/// <summary>
/// /中序遍历
/// </summary>
class Program
{
static void Main(string[] args)
{
BinaryTree<int>integers=new BinaryTree<int> ();
integers.AddRange(8,5 ,6, 7, 3, 4, 13, 21, 1, 17);
integers.Print();
Console.ReadLine();
Console.Clear();
foreach (var item in integers.Inorder)
Console.WriteLine (item);
}
}
public class Node<T>where T:IComparable <T>
{
public T date;
private Node <T> leftNode;
public Node<T> LeftNode
{
get{return leftNode ;}
set{leftNode =value ;}
}
private Node <T> rightNode;
public Node<T> RightNode
{
get{return rightNode ;}
set{rightNode =value ;}
}
public Node(T date)
{
this.date =date ;
}
public override string ToString()
{
return date.ToString();
}
}
public class BinaryTree<T> where T:IComparable <T>
{
private Node<T> root;
public Node<T> Root
{
get { return root; }
set { root = value; }
}
public void Add(T item)
{
if (root == null)
{
root = new Node<T>(item );
return;
}
Add (item ,root);
}
private void Add(T item, Node<T> node)
{
if (item.CompareTo (node.date )<0)
{
if (node.LeftNode == null)
node.LeftNode = new Node<T>(item);
else
Add(item, node.LeftNode);
}
else if (item.CompareTo(node.date) > 0)
{
if (node.RightNode == null)
node.RightNode = new Node<T>(item);
else
Add(item,node.RightNode );
}
}
public void AddRange(params T[] items)
{
foreach (var item in items)
Add(item);
}
/// <summary>
/// error in displaying tree -7 is overwritten 17;
/// </summary>
public void Print()
{
Print(root, 0, 50 / 2);
}
private void Print(string s, int depth, int offset)
{
Console.CursorLeft = offset;
Console.CursorTop = depth;
Console.Write(s);
}
private void Print(Node<T> item,int depth,int offset)
{
if (item == null) return;
Console.CursorLeft = offset;
Console.CursorTop = depth;
Console.Write(item.date);
if (item.LeftNode != null)
Print("/", depth + 1, offset - 1);
Print(item.LeftNode ,depth +2,offset -3);
if (item.RightNode != null)
Print("\\",depth +1,offset +1);
Print(item.RightNode ,depth +2,offset +3);
}
IEnumerable<T> GetInorder(Node<T> node)
{
if (node.LeftNode != null)
{
foreach (T item in GetInorder (node.LeftNode ))
{
yield return item;
}
}
yield return node.date;
if (node.RightNode != null)
{
foreach (T item in GetInorder(node.RightNode ))
{
yield return item;
}
}
}
public IEnumerable<T> Inorder
{
get { return GetInorder(this.root); }
}
}
}
[解决办法]
Status HierarchyBiTree(BiTree T, Status (*Visit)(TElemType e)) { LinkQueue *Q; // 保存当前节点的左右孩子的队列 InitQueue(Q); // 初始化队列 if (T == NULL) return ERROR; //树为空则返回 p = T; // 临时保存树根T到指针p中 Visit(p->data); // 访问根节点 if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列 if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列 while (!QueueEmpty(Q)) { // 若队列不空，则层序遍历 DeQueue(Q, p); // 出队列 Visit(p->data); // 访问当前节点 if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子，左孩子进队列 if (p->rchild) EnQueue(Q, p->rchild); // 若存在右孩子，右孩子进队列 } DestroyQueue(Q); // 释放队列空间 return OK;}
[解决办法]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAXLEN 100
#define MAXNUM 10
typedef int Tree[MAXLEN];
Tree bt;
typedef struct queue
{
int begin,end;
int space[MAXLEN];
}Queue;
int main()
{
int i=0;
memset(bt,-1,sizeof(bt));
for(i=1;i <=MAXNUM;i++)
bt[i]=i;
Queue qe;
qe.begin=0;qe.end =0;
qe.space[qe.end++]=bt[1];
while(qe.begin!=qe.end)
{
if(bt[2*qe.space[qe.begin]]!=-1)//lchild
{
qe.space[qe.end++]=bt[2*qe.space[qe.begin]];
}
if(bt[2*qe.space[qe.begin]+1]!=-1)//rchild
{
qe.space[qe.end++]=bt[2*qe.space[qe.begin]+1];
}
qe.begin++;
}
printf("--------------------\n");
for(i=0;i <qe.end;i++)
printf("%d ",qe.space[i]);
return 0;
}