bianli2.cpp

二叉树遍历的递归算法,帮助理解程序设计过程中的递归思想,以及二叉树遍历的基本思想

#include <stdio.h>
// #include <stdlib.h>//等效于malloc.h
#include"malloc.h"
#include"iostream.h"
typedef struct btree
{
 int data;
 struct btree *left;
 struct btree *right; 
}BTR;

void creat_btree(BTR** p,int num)//建立树（对分查找树）
{
   if(*p==NULL)
   {
	   *p=(BTR*)malloc(sizeof(BTR));
	   if(*p==NULL)
	   {
		   cout<<"error"<<endl;
	   }
	   else
	   {
		   (*p)->data=num;
		   (*p)->left=NULL;
		   (*p)->right=NULL;
	   }
   }
   else
   {
	   if(num>(*p)->data)
          creat_btree(&((*p)->right),num);
	   else if(num<(*p)->data)
          creat_btree(&((*p)->left),num);
	   else
		   cout<<"dulpicate data"<<endl;
   }
}

void preorder(BTR* p)//先序
{
  if(p!=NULL)
  {
  printf("%4d",p->data);
  preorder(p->left);
  preorder(p->right);      
  }    
}


void midorder(BTR* p)//中序
{
  if(p!=NULL)
  {
  midorder(p->left);
  printf("%4d",p->data);
  midorder(p->right);      
  }    
}


void postorder(BTR* p)//后序
{
  if(p!=NULL)
  {
  postorder(p->left);
  postorder(p->right); 
  printf("%4d",p->data);     
  }    
}


int btreedepth(BTR* p)//求数的深度
{int h,hl,hr;
 if(p==NULL)
 {
 h=0;
 }
 else
 {
  hl=btreedepth(p->left);
  hr=btreedepth(p->right);
   if(hl>hr)
   {
    h=hl+1;
   }
  else
  {
    h=hr+1;
  }
 }
  return h; 
}

const int N=12;
int main()
{  
	int i;
	BTR* root=NULL;//指向树根节点的指针
    int a[N]={1,45,89,13,24,56,39,78,79,69,20,44};
	for(i=0;i<N;i++)//整个for语句用于构建二叉树
    {
      creat_btree(&root,a[i]);
    }
    preorder(root);
	cout<<endl;
    midorder(root);
	cout<<endl;
    postorder(root);
	cout<<endl;
    printf("%4d\n",btreedepth(root)); 
    return 0;
}