二叉排序树的建立和遍历(java)

也是个经典的面试题,要求建立二叉排序树同时实现树的遍历,其实不难,直接上代码吧

树节点定义:

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(){

    }

    TreeNode(int value){
        this.val = value;
        this.left = null;
        this.right = null;
    }

    TreeNode(int value, TreeNode left, TreeNode right){
        this.val = value;
        this.left = left;
        this.right = right;
    }
}

建立二叉排序树

public static TreeNode buildBST(int[] data){
        //建立二叉排序树
        //假设data中的数字是互不相同的
        TreeNode root = new TreeNode(data[0]);
        for(int i = 1; i < data.length; i++){
            insert(root, data[i]);
        }

        return root;
    }

    private static TreeNode insert(TreeNode root, int value) {
        //二叉排序树插入节点
        if(root == null){
            root = new TreeNode(value);
        }else{
            if(value <= root.val){
                //插入到左子树
                root.left = insert(root.left, value);
            }else{
                //插入到右子树
                root.right = insert(root.right, value);
            }
        }

        return root;
    }

遍历验证下: 更多的树的遍历方法,参考二叉树的多种遍历方法

public static void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        if(root.left != null){
            preOrder(root.left);
        }
        if(root.right != null){
            preOrder(root.right);
        }
    }

main函数:

public static void main(String[] args) {
        int[] data = {3,1,2,5,0,7,9,8};
        TreeNode root = Main.buildBST(data);
        Main.preOrder(root);
    }

当然这样生成的二叉树不是高度最小的二叉树,不过对于面试到这基本也就可以了

这篇博客说了如何建立高度最小的二叉排序树,大家参考下

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 将二叉树拆成链表题目分析代码

将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说,用二叉树的 right 指针,来表示链表中的 next 指针。

7630
来自专栏和蔼的张星的图像处理专栏

85. 在二叉查找树中插入节点常规操作

You can assume there is no duplicate values in this tree + node.

25420
来自专栏书山有路勤为径

二叉查找树编码与解码

LeetCode 449 给定一个二叉查找树,实现对该二叉查找树编码与解码功能。编码即将二叉查找树转为字符串,解码即将字符串转为二叉查找树。不限制使用何种编码...

6510
来自专栏desperate633

LintCode 最近公共祖先题目代码

8820
来自专栏计算机视觉与深度学习基础

Leetcode 103 Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' valu...

218100
来自专栏计算机视觉与深度学习基础

Leetcode 105 Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree. Not...

20260
来自专栏计算机视觉与深度学习基础

Leetcode 101 Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric arou...

185100
来自专栏赵俊的Java专栏

镜像二叉树

18130
来自专栏desperate633

LintCode 中序遍历和后序遍历树构造二叉树题目代码

8510
来自专栏计算机视觉与深度学习基础

Leetcode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is de...

22290

扫码关注云+社区

领取腾讯云代金券