二叉树排序程序.cpp

在数据计算和存储过程中

                     // 二叉树排序程序 //
                     //                   //
#include <iostream.h>

 //定义结构//
struct node                   
{     
   int data;
   node *xch,*jch;
};
 
int array[8]={10,18,3,8,12,2,7,3};    //定义数组,数组中数是需排序的数
void insert(node *head,node *s);             //插入函数声明
void display(node *head);                  //输出函数声明
node *head;                           //首节点
 //*********************************************************************//
 
 void main()
 { 
  node *s;
  head=new node;
  head->data=array[0];
  head->xch=head->jch=NULL;//建立头节点
  for(int i=1;i<=7;i++)
  {
   s=new node;
   s->data=array[i];
   s->xch=s->jch=NULL;
   insert(head,s);               //把S节点插入head指向的二叉树
  }
  s=head;
  display(s);                    //输出排序结果
  cout<<endl;
  } 
                                 //输出函数//
 void display(node *s)
 {
  if(s->xch!=NULL) display(s->xch);
  cout<<s->data<<" ";
  if(s->jch!=NULL) display(s->jch);
 }
   
 void insert(node *head,node *s)
                                 //*把S接点插入以head为头的二叉树中p是遍历指针用于查找插入点,//
                                 // q是p的前驱节点,新节点插入q的左右子域中*//
 {
  node *p,*q;
  q=p=head;
  if(s->data>=p->data) 
	  p=p->xch;
  else
	  p=p->jch;
  while(p!=NULL)                 //p节点不等于NULL说明还没找到叶子节点,继续查找//
  {
   q=p;
   if(s->data>=p->data)
	   p=p->xch;
   else 
	   p=p->jch;
  }
  if(s->data>=q->data)
	  q->xch=s;
  else 
	  q->jch=s;
 }