求用C语言实现二叉树层次遍历的递归算法，谢谢！！！

Question

如题所述

Answer 1

算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}

Tree *t = DeleteQueue();
TransLevele(t);
}
//测试程序，创建树输入例如ABD##E##C##,根左右创建的方式。
如下代码是测试通过的。
#include "stdlib.h"

#define MAX 100

typedef int Element;

typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;

typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;

Queue Qu;

void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();

void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);

int main()
{
Tree *r=NULL;
CreateTree(&r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}

void Init()
{
int i=0;
for (i=0; i<MAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}

void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)->ch = ch;
CreateTree(&((*r)->left));
CreateTree(&((*r)->right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
PrintTree(r->left);
PrintTree(r->right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}

Tree *t = DeleteQueue();
TransLevele(t);
}

Answer 2

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* self-referential structure */
struct treeNode {
struct treeNode *leftPtr; /* treeNode pointer */
int data; /* define data as an int */
struct treeNode *rightPtr; /* treeNode pointer */
}; /* end structure treeNode */
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr;
/* prototypes */
void insertNode( TreeNodePtr *treePtr, int value );
void inOrder( TreeNodePtr treePtr );
void preOrder( TreeNodePtr treePtr );
void postOrder( TreeNodePtr treePtr );
/* function main begins program execution */
int main() {
int i; /* counter */
int item; /* variable to hold random values */
TreeNodePtr rootPtr = NULL; /* initialize rootPtr */
srand( time( NULL ) );
printf( "The numbers being placed in the tree are:\n" );
/* insert random values between 1 and 15 in the tree */
for ( i = 1; i <= 10; i++ ) {
item = rand() % 15;
printf( "%3d", item );
insertNode( &rootPtr, item );
} /* end for */
/* traverse the tree preOrder */
printf( "\n\nThe preOrder traversal is:\n" );
preOrder( rootPtr );
/* traverse the tree inOrder */
printf( "\n\nThe inOrder traversal is:\n" );
inOrder( rootPtr );
/* traverse the tree postOrder */
printf( "\n\nThe postOrder traversal is:\n" );
postOrder( rootPtr );
return 0; /* indicates successful termination */
} /* end main */
/* insert node into tree */
void insertNode( TreeNodePtr *treePtr, int value ) {

/* if tree is empty */
if ( *treePtr == NULL ) {
*treePtr = malloc( sizeof( TreeNode ) );
/* if memory was allocated then assign data */
if ( *treePtr != NULL ) {
( *treePtr )->data = value;
( *treePtr )->leftPtr = NULL;
( *treePtr )->rightPtr = NULL;
} /* end if */
else {
printf( "%d not inserted. No memory available.\n", value );
} /* end else */
} /* end if */
else { /* tree is not empty */
/* data to insert is less than data in current node */
if ( value < ( *treePtr )->data ) {
insertNode( &( ( *treePtr )->leftPtr ), value );
} /* end if */
/* data to insert is greater than data in current node */
else if ( value > ( *treePtr )->data ) {
insertNode( &( ( *treePtr )->rightPtr ), value );
} /* end else if */
else { /* duplicate data value ignored */
printf( "dup" );
} /* end else */
} /* end else */
} /* end function insertNode */
/* begin inorder traversal of tree */
void inOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */
if ( treePtr != NULL ) {
inOrder( treePtr->leftPtr );
printf( "%3d", treePtr->data );
inOrder( treePtr->rightPtr );
} /* end if */
} /* end function inOrder */
/* begin preorder traversal of tree */
void preOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */
if ( treePtr != NULL ) {
printf( "%3d", treePtr->data );
preOrder( treePtr->leftPtr );
preOrder( treePtr->rightPtr );
} /* end if */
} /* end function preOrder */
/* begin postorder traversal of tree */
void postOrder( TreeNodePtr treePtr ) {
/* if tree is not empty then traverse */
if ( treePtr != NULL ) {
postOrder( treePtr->leftPtr );
postOrder( treePtr->rightPtr );
printf( "%3d", treePtr->data );
} /* end if */
} /* end function postOrder */本回答被网友采纳

Answer 3

void BrinaryTree(Tree *p){
if(p){
do(p);
BrinaryTree(p->left);
BrinaryTree(p->right);
}
}

Answer 4

软件工程 书里面好像有吧！自己找找！