江南无所谓 聊赠一枝春 前言 二叉搜索树插入 二叉搜索树遍历 二叉搜索树高度 二叉搜索树最大值 什么是二叉搜索树 满足条件: 左节点值 根节点值 右节点值 定义树节点 typede" />
  • 35648

    文章

  • 23

    评论

  • 20

    友链

  • 最近新加了很多技术文章,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

BST

欢迎来到阿八个人博客网站。本 阿八个人博客 网站提供最新的站长新闻,各种互联网资讯。 喜欢本站的朋友可以收藏本站,或者加QQ:我们大家一起来交流技术! URL链接:https://www.abboke.com/jsh/2019/0702/4635.html 1190000019634761">

图片描述

江南无所谓 聊赠一枝春

前言

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

什么是二叉搜索树

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

定义树节点

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

源码地址

链接描述

相关文章

暂住......别动,不想说点什么吗?
  • 全部评论(0
    还没有评论,快来抢沙发吧!