erchashu.cpp

关于数据结构的各章节的c原代码实现

// erchashu.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#define  MAX 12
struct treenode
{
	int data;
	struct treenode *llink;
	struct treenode *rlink;

};
typedef struct treenode node;
typedef node* link;
link creattree(int n)
{
	link root=NULL;
	

	for (int i=0;i<n;i++)
	{   
		link parentnode,currentnode;
	    
		link newnode=(link)malloc(sizeof(node));

		printf("\ninput data:");
		scanf("%d",&newnode->data);

		newnode->llink=NULL;
		newnode->rlink=NULL;
		currentnode=root;
		if(currentnode==NULL)
			root=newnode;
		else
		{
			while (currentnode!=NULL)
			{
				parentnode=currentnode;
				if(newnode->data>currentnode->data)
					currentnode=currentnode->rlink;
				else
					currentnode=currentnode->llink;
			}
			if(newnode->data>parentnode->data)
				parentnode->rlink=newnode;
			else
				parentnode->llink=newnode;
		}
	
	}
	return root;
}
void inorder(link ptr)
{
	if (ptr!=NULL)
	{
		inorder(ptr->llink);
		printf("%d\n",ptr->data);
		inorder(ptr->rlink);
	}
}
void preorder(link bt)
{
	link stack[MAX],p;
	int top;
	if(bt==NULL)return;
	top=0;
	p=bt;
	while (!(p==NULL&&top==0))
	{
		while (p!=NULL)
		{
			printf("\n%d",p->data);
			if (top<MAX-1)
			   stack[top++]=p;
			else
			{
				printf("stack overflow!");
				return;
			}
		    p=p->llink;
		}
		if(top<0)return;
		else
	      p=stack[--top]->rlink;	 
	}
}
void postorder(link bt)
{
	link stack[MAX],p;
	int top=0;
	p=bt;
	do
	{
		while(p!=NULL)
		{
		  stack[++top]=p;
		  p=p->llink;
		}
		while (top>0&&stack[top]->rlink==p)
		{
             p=stack[top--];
			 printf("%d\n",p->data);
		}
		if (top>0)
		{
			p=stack[top]->rlink;
		}

	}while (top>0);
}
int main(int argc, char* argv[])
{    
	link head;
     int n;
	 printf("input the number of tree: ");
	 scanf("%d",&n);
     head=creattree(n);
	 printf("前序遍历：\n");
     preorder(head);
	 printf("\n中序遍历：\n");
     inorder(head);
     printf("\n后序遍历：\n");
	 postorder(head);
	return 0;
}