// 二叉搜索树
// 根 > 左结点
// 根 < 右结点
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

typedef struct {
    Node* root;
} Tree;

// 二叉搜索树的插入
void insert(Tree* tree, int value)
{
    Node* node = malloc(sizeof(Node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    
    if (tree->root == NULL) {  // 树是空的
        tree->root = node;
    } else {
        Node* temp = tree->root;
        while (temp != NULL) {
            if (value < temp->data) {  // 小于根结点，左
                if (temp->left == NULL) {
                    temp->left = node;
                    return ;
                } else {
                    temp = temp->left;
                }
            } else {  // 大于根结点，右
                if (temp->right == NULL) {
                    temp->right = node;
                    return ;
                } else {
                    temp = temp->right;
                }
            }
        }
    }
    
}


void preorder(Node* node) {
    if (node != NULL) {
        printf("%d\n", node->data);
        preorder(node->left);
        preorder(node->right);
    }
}


void inorder(Node* node) {
    if (node != NULL) {
        inorder(node->left);
        printf("%d\n", node->data);
        inorder(node->right);
    }
}


void postorder(Node* node) {
    if (node != NULL) {
        postorder(node->left);
        postorder(node->right);
        printf("%d\n", node->data);
    }
}

// 获取树的高度
int get_height(Node* node)
{
    if (node == NULL) {
        return 0;
    } else {
        int left_h = get_height(node->left);
        int right_h = get_height(node->right);
        int max_h = (left_h > right_h) ? left_h : right_h;
        return max_h + 1;
    }
}

// 二叉搜索树最右结点就是最大值
// 获取二叉树最大值，假设所有结点值为正整数
int get_maximum(Node* node)
{
    if (node == NULL) {
        return -1;
    } else {
        int m1 = get_maximum(node->left);
        int m2 = get_maximum(node->right);
        int m3 = node->data;
        int max = m1;
        if (m2 > max) {max = m2;}
        if (m3 > max) {max = m3;}
        return max;
    }
}

int main(void)
{
    int arr[7] = {6, 3, 8, 2, 5, 1, 7};
    Tree tree;
    tree.root = NULL;
    int i;
    for (i=0; i<7; i++) {
        insert(&tree, arr[i]);
    }
    
//  preorder(tree.root);
//  putchar('\n');
//  inorder(tree.root);  // 中序遍历的结果是升序排列

    int h = get_height(tree.root);
    printf("h = %d\n", h);
    
    int m = get_maximum(tree.root);
    printf("max = %d", m);

}

binary_search_tree.jpg