#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct BstNode
{
   int data;
   struct BstNode *left;
   struct BstNode *right;
};

struct BstNode *GetNewNode(int data)
{
   struct BstNode *temp = (struct BstNode *)malloc(sizeof(struct BstNode));
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}

// 在二叉搜索树中插入一个节点
struct BstNode *Insert(struct BstNode *root, int data)
{
   if (root == NULL)
   {
      root = GetNewNode(data);
   }
   else if (data <= root->data)
   {
      root->left = Insert(root->left, data);
   }
   else
   {
      root->right = Insert(root->right, data);
   }
   return root;
}

// 在二叉搜索树中搜索一个节点
bool Search(struct BstNode *root, int data)
{
   if (root == NULL)
      return false;
   else if (root->data == data)
      return true;
   else if (data <= root->data)
      return Search(root->left, data);
   else
      return Search(root->right, data);
}

// 二叉搜索树的最小值
int FindMin(struct BstNode *root)
{
   struct BstNode *temp = root;
   if (temp == NULL)
   {
      printf("root is empty\n");
      return -1;
   }
   else
   {
      while (temp->left != NULL)
      {
         temp = temp->left;
      }
      return temp->data;
   }
}

// 二叉搜索树的最大值
int FindMax(struct BstNode *root)
{
   struct BstNode *temp = root;
   if (temp == NULL)
   {
      printf("root is empty\n");
      return -1;
   }
   else
   {
      while (temp->right != NULL)
      {
         temp = temp->right;
      }
      return temp->data;
   }
}
// 二叉搜索树的前序遍历
void Preorder(struct BstNode *root)
{
   if (root == NULL)
      return;
   printf("%d,", root->data);
   Preorder(root->left);
   Preorder(root->right);
}
// 二叉搜索树的中序遍历
void Inorder(struct BstNode *root)
{
   if (root == NULL)
      return;
   Inorder(root->left);
   printf("%d,", root->data);
   Inorder(root->right);
}
// 二叉搜索树的后序遍历
void Poseorder(struct BstNode *root)
{
   if (root == NULL)
      return;
   Poseorder(root->left);
   Poseorder(root->right);
   printf("%d,", root->data);
}

// 判断是否是二叉搜索树
bool IsSubtreeLesser(struct BstNode *root, int data)
{
   if (root == NULL)
      return true;
   if (root->data <= data && IsSubtreeLesser(root->left, data) && IsSubtreeLesser(root->right, data))
      return true;
   else
      return false;
}
bool IsSubtreeGreater(struct BstNode *root, int data)
{
   if (root == NULL)
      return true;
   if (root->data >= data && IsSubtreeGreater(root->left, data) && IsSubtreeGreater(root->right, data))
      return true;
   else
      return false;
}
bool IsBinarySearchTree(struct BstNode *root)
{
   if (root == NULL)
      return true;
   if (IsSubtreeLesser(root->left, root->data) && IsSubtreeGreater(root->right, root->data) && IsBinarySearchTree(root->left) && IsBinarySearchTree(root->right))
      return true;
   else
      return false;
}
// 二叉搜索树的高度
int FindHeight(struct BstNode *root)
{
   int LeftHeight = 0;
   int RightHeight = 0;
   if (root == NULL)
   {
      return -1;
   }
   LeftHeight = FindHeight(root->left);
   RightHeight = FindHeight(root->right);
   if (LeftHeight >= RightHeight)
      return LeftHeight + 1;
   else
      return RightHeight + 1;
}

int main()
{
   struct BstNode *root = NULL;
   printf("input start!\n");
   root = Insert(root, 10);
   root = Insert(root, 8);
   root = Insert(root, 7);
   root = Insert(root, 10);
   root = Insert(root, 35);
   root = Insert(root, 50);
   printf("input yes!\n");
   printf("%d", FindHeight(root));
   // Inorder(root);

   // if(IsBinarySearchTree(root) == true)printf("This is IsBinarySearchTree");
   // else printf("This is not IsBinarySearchTree");
   // if(Search(root,30) == true)printf("Found!\n");
   // else printf("Not Found!\n");

   // printf("%d\n",FindMax(root));
   // printf("%d",FindMin(root));
}