/* Binary tree demo program
Exercise: 課堂公布
*/
#include <stdio.h>
#include <malloc.h>
typedef struct treeNode {
char data;
treeNode *leftChild, *rightChild;
};
#define MAX_STACK_SIZE 100
#define MAX_QUEUE_SIZE 100
treeNode* stack[MAX_STACK_SIZE];
int top;
treeNode* queue[MAX_QUEUE_SIZE];
int front, rear;
treeNode* createTree();
void inorder(treeNode *ptr);
void preorder(treeNode *ptr);
void postorder(treeNode *ptr);
void iterInorder(treeNode *node);
void levelOrder(treeNode *ptr);
treeNode* copy(treeNode *original);
int equal(treeNode *first, treeNode *second);
void push(treeNode* item);
treeNode* pop();
void addq(treeNode* item);
treeNode* deleteq();
int main()
{
treeNode *tree1;
tree1=createTree();
printf("Inorder = ");
inorder(tree1);
printf("\n");
printf("Preorder = ");
preorder(tree1);
printf("\n");
printf("Postorder = ");
postorder(tree1);
printf("\n");
printf("Level order = ");
levelOrder(tree1);
printf("\n");
treeNode *tree2=copy(tree1);
if (equal(tree1,tree2))
{
printf("Inorder by interation of the copying tree = ");
iterInorder(tree2);
printf("\n");
}
getchar();
return 0;
}
treeNode* createTree()
{
treeNode *left, *right, *parent;
left=(treeNode *) malloc(sizeof(treeNode));
left->data='A';
left->leftChild=NULL;
left->rightChild=NULL;
right=(treeNode *) malloc(sizeof(treeNode));
right->data='B';
right->leftChild=NULL;
right->rightChild=NULL;
parent=(treeNode *) malloc(sizeof(treeNode));
parent->data='/';
parent->leftChild=left;
parent->rightChild=right;
left=parent;
right=(treeNode *) malloc(sizeof(treeNode));
right->data='C';
right->leftChild=NULL;
right->rightChild=NULL;
parent=(treeNode *) malloc(sizeof(treeNode));
parent->data='*';
parent->leftChild=left;
parent->rightChild=right;
left=parent;
right=(treeNode *) malloc(sizeof(treeNode));
right->data='D';
right->leftChild=NULL;
right->rightChild=NULL;
parent=(treeNode *) malloc(sizeof(treeNode));
parent->data='*';
parent->leftChild=left;
parent->rightChild=right;
left=parent;
right=(treeNode *) malloc(sizeof(treeNode));
right->data='E';
right->leftChild=NULL;
right->rightChild=NULL;
parent=(treeNode *) malloc(sizeof(treeNode));
parent->data='+';
parent->leftChild=left;
parent->rightChild=right;
return parent;
}
void inorder(treeNode *ptr)
{
if (ptr)
{
inorder(ptr->leftChild);
printf("%c",ptr->data);
inorder(ptr->rightChild);
}
}
void preorder(treeNode *ptr)
{
if (ptr)
{
printf("%c",ptr->data);
preorder(ptr->leftChild);
preorder(ptr->rightChild);
}
}
void postorder(treeNode *ptr)
{
if (ptr)
{
postorder(ptr->leftChild);
postorder(ptr->rightChild);
printf("%c",ptr->data);
}
}
void iterInorder(treeNode *node)
{
top= -1; /* initialize stack */
for (;;)
{
for (; node; node=node->leftChild)
push(node); /* add to stack */
node= pop(); /* delete from stack */
if (!node)
break; /* all nodes are traversed */
printf("%c",node->data);
node = node->rightChild;
}
}
void levelOrder(treeNode *ptr)
{
front = rear = 0;
if (!ptr) return; /* empty tree */
addq(ptr);
for (;;)
{
ptr = deleteq();
if (ptr)
{
printf("%c",ptr->data);
if (ptr->leftChild)
addq(ptr->leftChild);
if (ptr->rightChild)
addq(ptr->rightChild);
}
else break;
}
}
treeNode* copy(treeNode *original)
{
treeNode *temp;
if (original) {
temp=(treeNode *) malloc(sizeof(treeNode));
temp->leftChild=copy(original->leftChild);
temp->rightChild=copy(original->rightChild);
temp->data=original->data;
return temp;
}
return NULL;
}
int equal(treeNode *first, treeNode *second)
{
return ((!first & !second) ||
( first & second &
(first->data == second->data) &
equal(first->leftChild, second->leftChild) &
equal(first->rightChild, second->rightChild)));
}
void push(treeNode* item)
{
if (top==MAX_STACK_SIZE-1)
{
printf("\n");
printf("Stack is full, cannot add element\n");
return;
}
stack[++top] = item;
}
treeNode* pop()
{
if (top<0)
{
return NULL; /* return an error key */
}
return stack[top--];
}
void addq(treeNode* item)
{
if (rear == MAX_QUEUE_SIZE-1)
{
printf("\n");
printf("Queue is full, cannot add element\n");
return;
}
queue [++rear] = item;
}
treeNode* deleteq()
{
if (front==rear)
{
return NULL; /* return an error key */
}
return queue [++front];
}