a2-4.c

数据结构的一些比较经典的程序,适合刚学的人,里面的一些程序都是比较常用的

#define NULL 0
#include "stdlib.h"
#include "stdio.h"
 struct tree
 {
	int data;
	int DescNum;
	struct tree * left;
	struct tree * right;
 };
 typedef struct tree treenode;
 typedef treenode * btree;
 btree insertnode (btree root,int value)
 {
	 btree newnode;
	 btree current;
	 btree back;
	 newnode = (btree)malloc(sizeof(treenode));
	 newnode->data=value;
	 newnode->left=NULL;
	 newnode->right=NULL;
	 if (root==NULL)
	 {
		 return newnode;
	 }
	 else 
	 {
		 current=root;
		 while (current!=NULL)
		 {
			 back=current;
			 if (current->data>value)
				 current=current->left;
			 else 
				 current=current->right;
		 }
		 if (back->data>value)
			 back->left=newnode;
		 else back->right=newnode;
	 }
	 return root;
 }
 btree creatbtree(int * data,int len)
 {
	 btree root=NULL;
	 int i;
	 for (i=0;i<len;i++)
		 root=insertnode (root,data[i]);
	 return root;
 }
 int DescNum(btree T)
 {
	 int d;
	 if (!T) return -1;
	 else d=(DescNum(T->left)+DescNum(T->right)+2);
	 T->DescNum=d;
	 return d;
 }
 void preorder(btree ptr)
 {
	 if (ptr!=NULL)
	 {
		 printf(" %2d ",ptr->data);
		 preorder(ptr->left);
		 preorder(ptr->right);
	 }
 }
 void inorder(btree ptr)
 {
	 if (ptr!=NULL)
	 {
		 inorder(ptr->left);
		 printf(" %2d ",ptr->data);
		 inorder(ptr->right);
	 }
 }
 void postorder(btree ptr)
 {
	 if (ptr!=NULL)
	 {
		 postorder(ptr->left);
		 postorder(ptr->right);
		 printf(" %2d ",ptr->data);
	 }
 }
 btree btreesearch(btree ptr,int value)
 {
	 btree ptr1,ptr2;
	 if (ptr!=NULL)
	 {
		 if (ptr->data==value)
			 return ptr;
		 else
			 ptr1=btreesearch(ptr->left,value);
			 ptr2=btreesearch(ptr->left,value);
			 if (ptr1!=NULL)
				 return ptr1;
			 else if (ptr2!=NULL)
				 return ptr2;
			 else return NULL;
	 }
	 else return NULL;
 }
		 
 void main()
 {
	 int k,value,flag;
	 btree root=NULL;
	 btree find;
	 int data[9];
	 printf("输入9个树中元素:\n");
	 for(k=0;k<=8;k++)
	 {
		 printf("输入第%d个数据:",k+1);
		 scanf("%d",&data[k]);
	 }
	 root=creatbtree(data,9);
	 printf("按哪种方式编历这个树:(1.前序 2.中序 3.后序):");
	 scanf("%d",&flag);
	 switch(flag)
	 {
	 case 1:
		 preorder(root);printf("\n");break;
	 case 2:
		 inorder(root);printf("\n");break;
	 case 3:
		 postorder(root);printf("\n");break;
	 };
	 printf("输入要查找子孙数目结点的值:");
	 scanf("%d",&value);
	 find=btreesearch(root,value);
	 k=DescNum(find);
	 printf("\n要查找的结点%d的子孙数目是 %d\n",value,k);
 }