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

typedef int ElemType;

/**
* 定義節(jié)點
*/
typedef struct BSTNode{
 ElemType data;//數(shù)據(jù)域
 struct BSTNode *lchild,//左孩子
  *rchild;//右孩子
}BSTNode;

/**
* 插入節(jié)點
*/
int BST_InsertNode(BSTNode** bstNode,ElemType e);

/**
* 創(chuàng)建BST樹
*/
void BST_Create(BSTNode** bstTree,ElemType* dataSet,int n);

/**
 * 查找BST樹節(jié)點
 */
BSTNode* BST_SearchNode(BSTNode** bstNode,ElemType e);

/**
 * 遍歷BST樹節(jié)點
 */
void BST_PrintNodes(BSTNode* bstNode);

#include "BSTree.h"

/**
* 插入節(jié)點
*/
int BST_InsertNode(BSTNode** bstNode,ElemType e){
 //如果BST樹為空，直接創(chuàng)建根節(jié)點
 if (*bstNode==NULL)
 {
  *bstNode=(BSTNode*)malloc(sizeof(BSTNode));
  (*bstNode)->data=e;
  (*bstNode)->lchild=NULL;
  (*bstNode)->rchild=NULL;
  return 1;
 }
 //如果BST樹不為空,則比較插入值與根節(jié)點值的大小關系
 if ((*bstNode)->data==e)
  return 0;//關鍵值相同，則插入失敗
 else if ((*bstNode)->data>e)
  return BST_InsertNode(&(*bstNode)->lchild,e);//大于插入值，將其作為左子樹節(jié)點
 else if ((*bstNode)->data<e)
  return BST_InsertNode(&(*bstNode)->rchild,e);//小于插入值，將其作為右子樹節(jié)點
}

/**
* 創(chuàng)建BST樹
*/
void BST_Create(BSTNode** bstTree,ElemType* dataSet,int n){
 int i=0;
 *bstTree=NULL;//BST樹初始化為空
 while (i<n)
 {
  printf("%d\t",dataSet[i]);
  BST_InsertNode(bstTree,dataSet[i++]);
 }
 printf("\n");
}

/**
 * 查找BST樹節(jié)點
 */
BSTNode* BST_SearchNode(BSTNode** bstNode,ElemType e){
 if (*bstNode==NULL)//判空
  return *bstNode;
 //查找結點
 if ((*bstNode)->data==e)//驗證是否為根節(jié)點
  return *bstNode;
 else if ((*bstNode)->data>e)
 {
  return BST_SearchNode(&(*bstNode)->lchild,e);//如果小于根節(jié)點的值，查找左子樹
 }else
 {
  return BST_SearchNode(&(*bstNode)->rchild,e);//如果大于根節(jié)點的值，查找右子樹
 }
}

/**
 * 遍歷BST樹節(jié)點
 */
void BST_PrintNodes(BSTNode* bstNode){
 if (bstNode==NULL)//根節(jié)點判空
 {
  return;
 }
 //打印根節(jié)點的值
 printf("%d\t",(bstNode)->data);
 //從根節(jié)點開始遍歷
 if (bstNode->lchild!=NULL)
  BST_PrintNodes((bstNode)->lchild);//遍歷左子樹
 if (bstNode->rchild!=NULL)
  BST_PrintNodes(bstNode->rchild);//遍歷右子樹
}

#include "BSTree.h"


int main(int argc,char** argv){
 int i;
 ElemType arr[]={45,24,53,45,12,24,68,25,36,96,100,25,64,78};//只有4個元素，因為關鍵字重復的元素不能被插入
 BSTNode* bstNode=NULL;
 BSTNode* bstTemp=NULL;
 //創(chuàng)建BST樹
 BST_Create(&bstNode,arr,sizeof(arr)/sizeof(ElemType));
 printf("%d\t%d\n",bstNode,bstNode->data);
 printf("%d\t%d\n",bstNode,bstNode->lchild->data);

 //查找結點
 bstTemp=BST_SearchNode(&bstNode,53);
 printf("the aimed node is %d,\n",bstNode->data);
 
 //遍歷BST樹的所有節(jié)點
 BST_PrintNodes(bstNode);
 printf("\n");
}