erchashu.cpp

数据结构中的建立排序二叉树算法,很经典,非常容易看懂,适合初学者.

#include<iostream.h>

typedef struct NODE  // 结点结构
{
	int data;
	struct NODE  *Left_child, *right_child;    
} NODE, *node;

void Creatnode( node &root_node,int e ) //建树,root_node表示根结点
{
  
  if (!root_node)                                      // 新插入结点必为叶子结点
  {
	  NODE *s = new NODE;                         // 生成新的结点
	  s ->data = e;                            
	  s->Left_child = NULL;                          
	  s->right_child = NULL; 
	  root_node = s;
  }                          
  else 
  {
	  if ( e< root_node->data)
		  Creatnode(root_node->Left_child,e);    // 建在左子树中
	  else
		  Creatnode(root_node->right_child,e);    // 建在右子树中
  }
} 

void SearchBSroot_node (node root_node, int x)// 查找
{
	node f;
	node p;
	if (!root_node)
	{ p = f;cout<<"没找到";}   
	else  if ( x==root_node->data )
	{ p = root_node;cout<<"找到";}  
	else  
	{
		if ( x<root_node->data )
		SearchBSroot_node (root_node->Left_child, x);  
                         
		else
		SearchBSroot_node (root_node->right_child, x);
    }
} 




void Insert_BSroot_node( node &root_node,int e ,node f,node &p)// 插入记录e
{
  
  NODE *s = new NODE;                         // 生成新的结点
  s ->data = e;  s->Left_child = NULL;  s->right_child = NULL;    // 新插入结点必为叶子结点
  if (!root_node)  root_node = s;                           // 插入的结点为根结点
  else {
         p = root_node;
         while ( p)                           // 查找插入位置
		 {
			 if ( e< p->data)
			 { f = p;  p = p->Left_child; }     // 应插入在左子树中
			 else
             { f = p;  p = p->right_child; } // 应插入在右子树中
		 }
         if ( e < f->data)  f->Left_child = s;     // 插入为f 所指结点的左子树根
         else  f->right_child = s;               // 插入为f所指结点的右子树根
       } 
}
void PrintElement(int  e)  
 {   cout<<e<<" "; }                          
             

void PreOrder(node root_node, void(*visit)(int  e)) //先序
{
  if (root_node)
  {
          visit(root_node->data);
		  PreOrder (root_node->Left_child, visit);
		  PreOrder (root_node->right_child, visit); 
  }
}
                            
void inorder(node root_node, void(*visit)(int e)) //中序
{
  if (root_node)  
  {
	  inorder (root_node->Left_child, visit);
      visit(root_node->data);
	  inorder (root_node->right_child, visit); 
  }
}
void postorder(node root_node, void(*visit)(int e)) //后序
{
  if (root_node) 
  { 
	  postorder (root_node->Left_child, visit);
      postorder (root_node->right_child, visit);
	  visit(root_node->data);
  }
}
void main()
{
    node root_node=NULL;
	int zhou[10];
	cout<<"input element!:"<<'\n';
    for(int i=0;i<10;i++)  //输入数组
	{
		cin>>zhou[i];
	}
	
	for(i=0;i<10;i++)  //建立排序二叉树
	{
		Creatnode(root_node,zhou[i]);
	}
    PreOrder(root_node,PrintElement);//先序
	cout<<'\n';
	inorder(root_node,PrintElement);//中序
	cout<<'\n';
	postorder(root_node,PrintElement);//后序
    cout<<'\n';
	int x;
	cout<<"查找";
	cin>>x;
    SearchBSroot_node (root_node, x);
}