xiansuoerchashu.cpp

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

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

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
typedef struct ttbnode
{ 
  int data;
  struct ttbnode* lchild;
  struct ttbnode* rchild;
  int ltag;
  int rtag;
}node,*link;
link createtree(int n)
{
  link root=NULL;
  for (int i=0;i<n;i++)
  {
	  link parentnode,currentnode;
	  link newnode=(link)malloc(sizeof(node));
	  printf("input no%d\n",i+1);
	  scanf("%d",&newnode->data);
	  newnode->lchild=NULL;
	  newnode->rchild=NULL;
	  currentnode=root;
	  if(currentnode==NULL)root=newnode;
	  else
	  {
        while (currentnode!=NULL)
        {
			parentnode=currentnode;
			if(newnode->data<currentnode->data)
				currentnode=currentnode->lchild;
			else
                currentnode=currentnode->rchild;
        }
		if(newnode->data<parentnode->data)
			parentnode->lchild=newnode;
		else
			parentnode->rchild=newnode;
	  }
  }
  return root;
}
link postnode(link p)
{
  link post;
  post=p->rchild;
  if(p->rtag!=1)
	  while(post->ltag==0)post=post->lchild;
	  return(post);
}
link prenode(link p)
{
	link pre;
	pre=p->lchild;
	if(p->ltag!=1)
		while(pre->rtag==0)pre=pre->rchild;
		 return(pre);
}
link search(link head,int x)
{
   link p,q;
   p=head->lchild;
   q=p;
   while(p->data!=x&&p!=head)p=postnode(p);
   if (p==head)
   {
    while(q->data!=x&&q!=head)q=postnode(q);
	if (q==head)
	{
		printf("not found the data\n");
		return(0);
	}
	else return(q);
   }
   else return(p);
}
link addthread(link bt,link pre);
link threadtree(link bt)
{
  link head,pre;
  head=(link)malloc(sizeof(node));
  head->ltag=0;
  head->rtag=1;
  head->rchild=head;
  head->lchild=bt;
  if (bt==NULL)
{
  head->lchild=head;
  head->ltag=1;
}
  else
  {
	  pre=head;
	  pre=addthread(head->lchild,pre);
	  pre->rchild=head;
	  pre->rtag=1;
	  head->rchild=pre;
	  head->rtag=1;
      
  }
  return(head);
}
link addthread(link bt,link pre)
{
  link stack[12],p;
  int top;
  p=bt;
  top=0;
  while (!(p==NULL&&top==0))
  {
	  while (p!=NULL)
	  {
		  if (top<11)
		  stack[top++]=p;                                                                                                                                                                                                                                                                                                                                 
		  else
		  {
			  printf("stack overflow!");
			  return(0);
		  }
		  p=p->lchild;
	  }
	  if(top==-1)return(pre);
	  else
	  {
		  top--;
		  p=stack[top];
		  if (p->lchild==NULL)
		  {
             p->ltag=1;
			 p->lchild=pre;
		  }
		  else
			  p->ltag=0;
		  if (pre->rchild==NULL)
		  {
			  pre->rtag=1;
			  pre->rchild=p;
		  }
		  else pre->rtag=0;
		  pre=p;
		  p=p->rchild;
	  }
}
  return(pre);
}
int main(int argc, char* argv[])
{
	link head,pst,result;
	int m,n;
	printf("input number of node:");
	scanf("%d",&n);
	head=createtree(n);
	head=threadtree(head);
	pst=postnode(head);
	printf("\n%d\n",pst->data);
	printf("input the data you want to search:");
	scanf("%d",&m);
	result=search(head,m);
	if(result!=NULL)printf("found\n");
	return 0;
}