用C语言实现递归法先序创建二叉树，用非递归法进行先序和层次遍历输出节点。希望各位IT精英可以加以详细注释
#include // malloc()等
#include // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include // atoi()，exit()
#include // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
网上很多的
#include
#include
#include
struct Node
{
void *data;
struct Node *next;
};
typedef struct Node Queue;
Queue* Enqueue(Queue **rear, void data, int *count)
{
Queue *node = (Queue)malloc(sizeof(Queue));
node->data = data;
node->next = NULL;
if (*rear != NULL)
{
(*rear)->next = node;
}
*rear = node;
(*count)++;
return node;
}
void Dequeue(Queue **head, int *count)
{
Queue *node = (*head);
(*head) = node->next;
free(node);
(*count)--;
}
typedef struct Node Stack;
void Push(Stack **top, void data, int *count)
{
Stack *node = (Stack)malloc(sizeof(Stack));
node->data = data;
node->next = NULL;
node->next = *top;
*top = node;
(*count)++;
}
void Pop(Stack **top, int *count)
{
Stack *node = (*top);
(*top) = node->next;
free(node);
(*count)--;
}
struct TreeNode
{
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* CreateNode(int data)
{
struct TreeNode node = (struct TreeNode)malloc(sizeof(struct TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void CreateTree(struct TreeNode** root)
{
int data;
scanf("%d", &data);
if (data == 0)
return;
struct TreeNode* node = CreateNode(data);
printf("添加数据 %d\n", data);
(*root) = node;
printf("添加左节点:");
CreateTree(&((*root)->left));
printf("添加右节点:");
CreateTree(&((*root)->right));
}
void FirstOrderPrintTree(struct TreeNode* root)
{
Stack *top = NULL;
int count = 0;
Push(&top, root, &count);
while (top)
{
struct TreeNode* node = (struct TreeNode*)top->data;
printf("%d\n", node->data);
Pop(&top, &count);
if (node->right)
Push(&top, node->right, &count);
if (node->left)
Push(&top, node->left, &count);
}
}
void LevelPrintTree(struct TreeNode* root)
{
Queue *head = NULL, *rear = NULL;
int count = 0;
Enqueue(&rear, root, &count);
head = rear;
while (count != 0)
{
struct TreeNode* node = (struct TreeNode*)head->data;
printf("%d \n", node->data);
if (node->left)
Enqueue(&rear, node->left, &count);
if (node->right)
Enqueue(&rear, node->right, &count);
Dequeue(&head, &count);
}
}
void main()
{
struct TreeNode* root = NULL;
CreateTree(&root);
FirstOrderPrintTree(root);
LevelPrintTree(root);
system("pause");
}
哪里需要注释再说
非递归需要借助一个堆栈，这里有个例子代码，包括了堆栈的实现和使用它非递归遍历树
#include
#include
#define MAXSIZE 255
typedef struct BiNode
{
char data;
struct BiNode *lchild;
struct BiNode *rchild;
}BiTree;
BiTree *CreateBitreepre(char *str)
{
BiTree *bt,*stack[MAXSIZE],*p=NULL;
int top=-1,k,j=0;
char ch;
bt=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(':
top++;
stack[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':
k=2;
break;
default:
{
p=(BiTree *)malloc(sizeof(BiTree));
p->data=ch;
p->lchild=p->rchild=NULL;
if(bt==NULL)
bt=p;
else
{
switch(k)
{
case 1:
stack[top]->lchild=p;
break;
case 2:
stack[top]->rchild=p;
break;
}
}
}
}
j++;
ch=str[j];
}
return bt;
}
void OutBiTree(BiTree *bt)
{
BiTree *stack[MAXSIZE],*p;
int level[MAXSIZE][2],top,n,i,width=4;
char type;
if(bt!=NULL)
{
top=1;
stack[top]=bt;
level[top][0]=width;
level[top][1]=2;
while(top>0)
{
p=stack[top];
n=level[top][0];
switch(level[top][1])
{
case 0:
type='0';
break;
case 1:
type='1';
break;
case 2:
type='2';
break;
}
for(i=1;i<=n;i++)
printf(" ");
printf("%c(%c)\n",p->data,type);
for(i=n+1;i<=1;i+=2)
printf("——");
top--;
if(p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
level[top][0]=n+width;
level[top][1]=1;
}
if(p->rchild!=NULL)
{
top++;
stack[top]=p->lchild;
level[top][0]=n+width;
level[top][1]=0;
}
}
}
}
void main()
{
BiTree * bt;
char *gyb,str[MAXSIZE];
int j=1;
printf("\n--------------------------------------");
printf("\n 1将按照输入的二叉树广义表表示字符串 ");
printf("\n 生成对应的二叉树链式结构 ");
printf("\n 2输出二叉树的凹入法表示形式 ");
printf("\n r——跟 0——左孩子 1——右孩子 ");
printf("\n--------------------------------------");
printf("\n请输入二叉树的广义表形式：\n");
gyb=str;
scanf("%s",&str);
bt=CreateBitreepre(gyb);
printf("此二叉树建立成功！\n");
printf("次二叉树凹入法表示为：\n");
OutBiTree(bt);
}
/*
二叉树的操作（ 用递归和非递归的方法都要）
任务：
要求能够输入树的各个结点，创建二叉树，并能够输出用不同方法遍历的遍历序列；
分别建立建立二叉树存储结构的的输入函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；
*/
#include
using namespace std;
typedef char datatype;
typedef struct node
{
datatype data;
struct node *lchild, *rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;
typedef struct stack
{
bintree data[100];
int tag[100];
int top;
}seqstack;
//入栈
void push(seqstack *s, bintree t)
{
s->data[s->top] = t;
s->top++;
}
//出栈
bintree pop(seqstack *s)
{
if (s->top != 0)
{
s->top--;
return (s->data[s->top]);
}
else
return NULL;
}
//create bintree 按照前序遍历创建二叉树
bintree createbintree()
{
char ch;
bintree t;
if ((ch = getchar()) == '#')
t = NULL;
else
{
t = (bintnode*)malloc(sizeof(bintnode)); //t=new bintnode;
t->data = ch;
t->lchild = createbintree();
t->rchild = createbintree();
}
return t;
}
//前序遍历 递归
void preorder(bintree t)
{
if (t)
{
cout << t->data;
preorder(t->lchild);
preorder(t->rchild);
}
}
//中序遍历 递归
void inorder(bintree t)
{
if (t)
{
inorder(t->lchild);
cout << t->data;
inorder(t->rchild);
}
}
//后序遍历 递归
void postorder(bintree t)
{
if (t)
{
postorder(t->lchild);
postorder(t->rchild);
cout << t->data;
}
}
//非递归先序遍历
void preorder1(bintree t)
{
seqstack s;
s.top = 0;
while ((t) || (s.top != 0)) //当前处理子树不为空或栈不为空则循环
{
if (t)
{
cout << t->data;
push(&s, t);
t = t->lchild;
}
else
{
t = pop(&s);
t = t->rchild;
}
}
}
//非递归中序遍历
void inorder1(bintree t)
{
seqstack s;
s.top = 0;
while ((t) || (s.top != 0))
{
if (t)
{
push(&s, t); //如果子树存在时，将左子树进栈
t = t->lchild;
}
else
{
t = pop(&s); //左子树为空时，出栈
cout << t->data;
t = t->rchild; //访问右子树
}
}
}
//非递归后序遍历
void postorder1(bintree t)
{
seqstack s;
s.top = 0;
while ((t) || (s.top != 0))
{
if (t)
{
s.data[s.top] = t; //首先进入左子树访问，根节点和右子树尚未访问，将T保存起来放入栈中
s.tag[s.top] = 0; //每个元素刚进栈时，将tag值设为0
s.top++;
t = t->lchild;
}
else
if (s.tag[s.top - 1] == 1)
{
s.top--;
t = s.data[s.top];
cout << t->data;
t = NULL;
}
else
{
t = s.data[s.top - 1];
s.tag[s.top - 1] = 1;
t = t->rchild;
}
}
}
int main()
{
cout<<"请以前序遍历的方法创建二叉树，以#结束（如A##）"<<endl;
root = createbintree();
cout << "前序遍历（递归）：";
preorder(root);
cout << endl;
cout << "前序遍历（非递归）：";
preorder1(root);
cout << endl;
cout << "中序遍历（递归）：";
inorder(root);
cout << endl;
cout << "中序遍历（非递归）：";
inorder1(root);
cout << endl;
cout << "后序遍历（递归）：";
postorder(root);
cout << endl;
cout << "前序遍历（非递归）：";
postorder1(root);
cout << endl;
return 0;
}