#include "stdio.h"
#include "malloc.h"
#define MAXLENGTH 128
struct Node
{
int value;
struct Node* firstChild;
struct Node* nextBrother;
};
struct Node* createNode(int value)
{
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->value = value;
node->firstChild = NULL;
node->nextBrother = NULL;
return node;
}
struct Stack
{
struct Node* a[MAXLENGTH];
int top;
};
struct Queue
{
struct Node* a[MAXLENGTH];
int first;
int end;
int num;
};
void addChild(struct Node* node, struct Node* childNode)
{
if(node->firstChild != NULL)
{
struct Node* temp = node->firstChild;
while(temp ->nextBrother != NULL)
temp = temp->nextBrother;
temp->nextBrother = childNode;
}
else
{
node->firstChild = childNode;
}
}
void firstRoot(struct Node* root) //递归先根遍历
{
printf("%d\n",root->value);
struct Node* temp = root->firstChild;
while(temp !=NULL)
{
firstRoot(temp);
temp = temp->nextBrother;
}
}
struct Node* pop(struct Stack* stack)
{
struct Node* node = stack->a[stack->top];
stack->top--;
return node;
}
void pull(struct Stack* stack, struct Node* node)
{
stack->a[++stack->top] = node;
}
void firstRoot_Stack(struct Node* root) //用栈来实现
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
struct Stack* child_stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = -1;
child_stack->top = -1;
pull(stack, root);
while(stack->top != -1 )
{
struct Node* node = pop(stack);
printf("%d\n", node->value);
struct Node* child = node->firstChild;
while(child != NULL)
{
pull(child_stack, child);
child = child->nextBrother;
}
while(child_stack->top != -1)
{
pull(stack, pop(child_stack));
}
}
}
struct Node* out(struct Queue* queue)
{
struct Node* node = queue->a[queue->first];
queue->num--;
queue->first = (queue->first + 1) % MAXLENGTH;
return node;
}
void in(struct Queue* queue, struct Node* node)
{
queue->end = (queue->end + 1) % MAXLENGTH;
queue->num++;
queue->a[queue->end] = node;
}
void layer_Root(struct Node* root) //递归层次遍历只能用队列实现
{
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->first = 0;
queue->end = -1;
queue->num = 0;
in(queue, root);
while(queue->num > 0)
{
struct Node* node = out(queue);
printf("%d\n", node->value);
struct Node* child = node->firstChild;
while(child != NULL)
{
in(queue, child);
child = child->nextBrother;
}
}
}
/*
树的结构为
1
-----
2 3 4
- -
5 6
*/
int main()
{
struct Node* first = createNode(1);
addChild(first, createNode(2));
addChild(first, createNode(3));
addChild(first, createNode(4));
addChild(first->firstChild, createNode(5));
addChild(first->firstChild->nextBrother, createNode(6));
firstRoot(first);
firstRoot_Stack(first);
layer_Root(first);
getchar();
return 0;
}