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 树中序遍历的得到的是一个有序的数列

源码地址

链接描述