主题:[讨论]二叉树的遍历
请高手帮忙,我只做出了二叉树的遍历算法,谁能帮我给出非递归的程序,还有层次遍历的程序...对于这几个我老是出错,调试了N久。。
/*======================================================================================================================*/
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
#define INFEASIBLE -1
struct tree
{struct tree *left;
int data;
struct tree *right;
};
typedef struct tree treenode;
typedef treenode *b_tree;
/*---------------------------------------------------------------------------------------------------------------------*/
/* 插入二叉树的节点 */
/*---------------------------------------------------------------------------------------------------------------------*/
b_tree insert_node(b_tree root,int node)
{
b_tree newnode;
b_tree currentnode;
b_tree parentnode;
/*建立新节点的内存空间*/
newnode=(b_tree) malloc (sizeof(treenode));
newnode->data=node;
newnode->right=NULL;
newnode->left=NULL;
if(root==NULL)
return newnode;
else
{
currentnode=root;
while(currentnode!=NULL)
{parentnode=currentnode;
if (currentnode->data>node)
currentnode=currentnode->left;
else
currentnode=currentnode->right;
}
if(parentnode->data>node)
parentnode->left=newnode;
else
parentnode->right=newnode;
}
return root;
}
/*----------------------------------------------------------------------------------------------------------------------*/
/* 建立二叉树 */
/*----------------------------------------------------------------------------------------------------------------------*/
b_tree create_btree(int *data,int len)
{
b_tree root=NULL;
int i;
for(i=0;i<len;i++)
root=insert_node(root,data[i]);
return root;
}
/*---------------------------------------------------------------------------------------------------------------------*/
/* 二叉树前序的递归遍历 */
/*---------------------------------------------------------------------------------------------------------------------*/
void preorder(b_tree point)
{
if(point!=NULL)
{
printf("%d",point->data);
preorder(point->left);
preorder(point->right);
}
}
/*-----------------------------------------中序递归遍历---------------------------------------------------------------*/
void inorder(b_tree point)
{
if(point!=NULL)
{
inorder(point->left);
printf("%d",point->data);
inorder(point->right);
}
}
/*-----------------------------------------后序递归遍历---------------------------------------------------------------*/
void postorder(b_tree point)
{
if(point!=NULL)
{
postorder(point->left);
postorder(point->right);
printf("%d",point->data);
}
}
/*=====================================================================================================================*/
/* 主程序 */
/*=====================================================================================================================*/
void main ()
{
b_tree root=NULL;
int i,index;
int value;
int nodelist[20];
printf("\n Please input the elements of the bibary tree(Exit for 0):\n");
index=0;
/*---------------读取数值存到数组中--------------*/
scanf("%d",&value);
while(value!=0)
{ nodelist[index]=value;
index=index+1;
scanf("%d",&value);
}
/*---------------建立二叉树-------------------------------------------------------------*/
root=create_btree(nodelist,index);
system("cls");
int choice;
for(;;)
{
printf("二叉树的遍历!");
printf("请你选择遍历的方式 :");
printf(" * 1 二叉树前序的递归遍");
printf("* 2 中序递归遍历");
printf(" * 3 后序递归遍历");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
/*--------------递归前序遍历二叉树-------------------------------------------*/
printf("\n the preorder traversal result is[ ");
preorder(root);
printf("]\n");
break;
};
case 2:
{ /*--------------递归中序遍历二叉树-------------------------------------------*/
printf("\n the preorder traversal result is[ ");
inorder(root);
printf("]\n");
break;
}
case 3:
{ /*--------------递归后序遍历二叉树-------------------------------------------*/
printf("\n the preorder traversal result is[ ");
postorder(root);
printf("]\n");
break;
}
case 4:
{
break;
}
case 5:
break;
}
case 6:
{
break;
}
case 0:
{exit(0)
break;
}
}
}
}