二叉树算法

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define ElementType int

//node structure constructor
typedef struct bt {
   ElementType data;
   struct bt *lchild, *rchild;
} BinaryTreeNode,*BTRoot;

//function declear
InOrder(BTRoot root);
PreOrder(BTRoot root);
PostOrder(BTRoot root);

//the main function to excute
main()
{
  BTRoot r=malloc(sizeof(BinaryTreeNode));
  CreateTree(r,1);
  printf("\nPreorder :");
  PreOrder(r);
  printf("\nInorder :");
  InOrder(r);
  printf("\nPostorder:");
  PostOrder(r);
  while(1) ;
  return 0;
}

//inorder function
InOrder(BTRoot root)
{
  if(!root) return 0;
  InOrder(root->lchild);
  printf("%4d",root->data);
  InOrder(root->rchild);
}

//preorder function
PreOrder(BTRoot root)
{
  if(!root) return 0;
  printf("%4d",root->data);
  PreOrder(root->lchild);
  PreOrder(root->rchild);
}

//postorder function
PostOrder(BTRoot root)
{
  if(!root) return 0;
  PostOrder(root->lchild);
  PostOrder(root->rchild);
  printf("%4d",root->data);
}
 /*receive the input data and create a node each time!*/
CreateTree(BTRoot root,int NodeNum) /* Preorder */
{
  ElementType x;
  int i,layer;

  layer=log(NodeNum)/log(2)+1;
  printf("\nInput data for Node %d in layer %d :",NodeNum,layer);
  scanf("%d",&x);
  root->data=x;

  printf("create lchild for Node %d in layer %d (0 for No)?",NodeNum,layer);
  scanf("%d",&i);
  if(i==0) root->lchild=NULL;
   else
    {root->lchild=(BTRoot)malloc(sizeof(BinaryTreeNode));
     CreateTree(root->lchild,2*NodeNum);
    }

  printf("create rchild for Node %d in layer %d (0 for No)?",NodeNum,layer);
  scanf("%d",&i);
  if(i==0) root->rchild=NULL;
   else
    {root->rchild=(BTRoot)malloc(sizeof(BinaryTreeNode));
     CreateTree(root->rchild,2*NodeNum+1);
    }
  return 0;
}

本文地址：http://com.8s8s.com/it/it25411.htm