/*       twoTree.cpp

在 c++环境编译 ！

 创建二叉树  ----> 装入数据，

---->遍历---> 显示 --->销毁*

都换用递归实现了 非递归实现还不怎么熟悉所以就

*/

#include <iostream.h>

#ifndef DEBUG

#define DEBUG

typedef int DataType;

typedef struct Node

{

       DataType        data;

       struct Node  *LChild;

       struct Node  *RChild;

}Node;

/*树的数据结构*/

/////////////////////////////////////////////////////////////

Node * Initiate()

/*初始化为空树*/

{

       Node   *root = 0;

       return   root ;

}

////////////////////////////////////////////////////////////////

Node * Creat(  DataType data  )

 /*建节点*/

{

       Node   * Temp   = new Node ;

       Temp -> data     = data ;

       Temp -> LChild = 0 ;

       Temp -> RChild = 0;

       return Temp ;

}

 

/************************************************/

void  Insert( Node *&root , DataType data )

//在c下不能这样 Node *&root

/* 降顺序二叉数装入数据，左子树<右子树*/

{

       Node *p = Creat( data );

       if( !root  )

       {

              root = p;

            

       }

          else if( p->data < root->data )

          {

                 Insert ( root->LChild , p->data );

          }

          else

          {

                 Insert ( root->RChild , p->data );

          } /*相等的 将装数据到右孩子 */

        

}

/****************************************************/

 void PrintTree(Node * root)

 /*递归中序遍历 ---> 显示从小到大*/

{

       if( !root )  return ;

       PrintTree(root->LChild);

      

      cout<< root->data <<"  :";

      PrintTree( root->RChild );

      return ;

}

/*********************************************************/

void  FreeTree(Node * root)

{

       if( !root ) return;

       FreeTree(root -> LChild);

       FreeTree(root -> RChild);

       delete root;//跟节点要最后删！

}

#endif DEBUG

///测试代码////////////

void main()

{ 

       int a;

       Node *Root = Initiate() ;

       cout<<" -1 to exit: "<<endl;

       cin>>a;            

       while( (a != -1)&&cin.good() )

                 //遇到非法输入同样退出循环

       {     

              Insert( Root ,  a );

                       cin>>a ;                        

       }

         if(!cin.good())

                     //输出错误信息

         {

                     cout<<" the type is error ! "<<endl;

         }

          PrintTree(Root);

          cout<<" ok ? "<<endl;

           FreeTree(Root);//销毁树 防止内存泄漏

          return;

}