BST

江南无所谓 聊赠一枝春

前言

• 二叉搜索树插入
• 二叉搜索树遍历
• 二叉搜索树高度
• 二叉搜索树最大值

什么是二叉搜索树

满足条件： 左节点值 < 根节点值 < 右节点值

定义树节点

    typedef struct TreeNode {        int data;        struct TreeNode *left;        struct TreeNode *right;    } TreeNode;

定义树

    typedef struct tree {        struct TreeNode *root;    } Tree;

二叉搜索树的插入

插入节点

    void insertNode (Tree *tree, int value) {        TreeNode *node1 = malloc(sizeof(TreeNode));        node1->data = value;        node1->left = NULL;        node1->right = NULL;                if(tree->root == NULL){            tree->root = node1;        } else {            TreeNode *temp = tree->root;            while (temp != NULL) {                if(value < temp->data){                    if(temp->left == NULL) {                        temp->left = node1;                        return ;                    } else {                       temp = temp->left;                    }                                    } else {                    if(temp->right == NULL) {                        temp->right = node1;                        return;                    } else {                       temp = temp->right;                    }                }            }        }    }

BST的前中后序遍历

    // 前序遍历 根->左->右    void preorderTraverse(TreeNode *tree) {        if(tree == NULL) {return;}        NSLog(@"%d ", tree->data);        preorderTraverse(tree->left);        preorderTraverse(tree->right);    }        //中序遍历 左->根->右    void midTraverse(TreeNode *tree) {        if(tree == NULL) {return;}        midTraverse(tree->left);        NSLog(@"%d ", tree->data);        midTraverse(tree->right);    }        //后序遍历 左->右->根    void postorderTraversal(TreeNode *tree) {        if(tree == NULL) {return;}        postorderTraversal(tree->left);        postorderTraversal(tree->right);        NSLog(@"%d ", tree->data);    }

二叉搜索树高度

    int getBSTHeight (TreeNode *node) {        if (node == NULL) {            return 0;        } else {            int leftH = getBSTHeight(node->left);            int rightH = getBSTHeight(node->right);            int max = leftH;            if (max < rightH) {                max = rightH;            }            return max+1;        }    }

二叉搜索树最大值

    int getMaxNum(TreeNode *node) {        if (node == NULL) {            return -1;        } else {            int leftMax = getMaxNum(node->left);            int rightMax = getMaxNum(node->right);            int current = node->data;            int max = leftMax;            if (rightMax > max) {                max = rightMax;            }            if (current>max) {                max = current;            }            return max;        }    }

测试功能

        int arr[] = {6,3,8,2,5,1,7};                // 创建树        Tree *tree = malloc(sizeof(Tree));        tree->root = NULL;        for(int i=0; i<7; i++) {            // 树中插入节点            insertNode(tree, arr[i]);        }            // 计算树的高度        int treeH = getBSTHeight(tree->root);        NSLog(@"%d\n", treeH);                 // 计算树的最大值        int maxNum = getMaxNum(tree->root);        NSLog(@"%d\n", maxNum);

测试结果

BST树中序遍历的得到的是一个有序的数列

源码地址

链接描述