tree.cpp

程序说明 创建二叉树

/*
程序说明
创建二叉树，并以前序、中序和后序进行遍历
随机产生15个0~100之间的整数，然后插入到二叉树中
2007.11.25
*/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

//自引用结构
struct treeNode{
 int data;     //节点值
 struct treeNode *leftPtr; //指向左子树的指针
 struct treeNode *rightPtr; //指向右子树的指针
}; /*结构定义结束*/

typedef struct treeNode TreeNode;
typedef TreeNode * TreeNodePtr;

/*函数原型*/
void insertNode(TreeNodePtr &treePtr,int value);  //插入节点
void inOrder(TreeNodePtr treePtr);     //中序遍历
void preOrder(TreeNodePtr treePtr);     //前序遍历
void postOrder(TreeNodePtr treePtr);    //后序遍历

/*主函数*/
void main(){
 int i;      //循环计数器
 int item;     //存储随机制的变量
 TreeNodePtr rootPtr=NULL; //树在开始的时候为空

 srand(time(NULL));
 printf("生成的随机数组成的树：\n");

 /*将1到100之间的随机数插入到树中去*/
 for(i=1;i<=15;i++){
  item=rand()%100;
  printf("%5d",item);
  insertNode(rootPtr,item);
 } /*结束for*/

 /*前序遍历*/
 printf("\n前序遍历:\n");
 preOrder(rootPtr);

 /*中序遍历*/
 printf("\n中序遍历:\n");
 inOrder(rootPtr);

 /*后序遍历*/
 printf("\n后序遍历:\n");
 postOrder(rootPtr);

 printf("\n");

} /*结束main函数*/

/*将节点插入到树中*/
void insertNode(TreeNodePtr &treePtr,int value){

 //生成新节点，找到一个要连的地方
 TreeNodePtr newNodePtr;
 if(newNodePtr=(TreeNodePtr)malloc(sizeof(TreeNode))){
  newNodePtr->data=value;
  newNodePtr->leftPtr=NULL;
  newNodePtr->rightPtr=NULL;
 } /*结束if*/
 else{
  printf("没有分配空间成功!\n");
 } /*结束else*/
 

 /*如果树为空*/
 if(treePtr==NULL){
  treePtr=newNodePtr;
 } /*结束if*/

 /*如果树不为空*/
 else{

  /*要插入的数值小于当前节点终的数值*/
  if(newNodePtr->data<treePtr->data){
   insertNode(treePtr->leftPtr,newNodePtr->data);
  } /*结束if*/

  /*要插入的数值大于当前节点中的数值*/
  else if(newNodePtr->data>treePtr->data){
   insertNode(treePtr->rightPtr,newNodePtr->data);
  } /*结束else if*/

  /*忽略重复的值*/
  else{
  } /*结束else*/

 } /*结束else*/
} /*结束insertNode()函数*/

/*对树进行中序遍历*/
void inOrder(TreeNodePtr treePtr){
 /*如果树不为空*/
 if(treePtr!=NULL){
  inOrder(treePtr->leftPtr);
  printf("%5d",treePtr->data);
  inOrder(treePtr->rightPtr);
 } /*结束if*/

} /*结束inOrder()函数*/

/*对树进行前序遍历*/
void preOrder(TreeNodePtr treePtr){
 /*如果树不为空*/
 if(treePtr!=NULL){  
  printf("%5d",treePtr->data);
  preOrder(treePtr->leftPtr);
  preOrder(treePtr->rightPtr);
 } /*结束if*/

} /*结束inOrder()函数*/

/*对树进行后序遍历*/
void postOrder(TreeNodePtr treePtr){
 /*如果树不为空*/
 if(treePtr!=NULL){
  postOrder(treePtr->leftPtr);  
  postOrder(treePtr->rightPtr);
  printf("%5d",treePtr->data);
 } /*结束if*/

} /*结束inOrder()函数*/