最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 二分搜索树的前序遍历

    之前我们学习了二分搜索树的添加和查询操作,这一小节开始我们研究二分搜索树的遍历。

    • 遍历操作就是把所有节点都访问一遍
    • 访问原因和业务相关,比如:现在数据结构中存储的都是学生的分数,但是可能有道题判错了,学生都应该加两分,那么就应该把所有节点都访问一遍,给每个学生加两分
    • 在线性结构下,遍历是极其容易的,无论是数组还是链表,从头到尾循环就好了

    二分搜索树的递归操作

    之前讨论的添加或查询都是这样一个模式,从根节点开始,根节点这个元素是不是我们要查找或添加的元素。

    如果是的话我们直接操作就好了,如果不是的话我们就要看看我们查找或添加的元素是不是小于根节点,小于根节点我们就要在左子树中继续这个操作,如果大于根节点就在右子树中继续进行这个操作。

    也就是说在递归过程中,我们每一次只选择一个子树继续下去,直到达到递归的中止条件,但是对于遍历操作是不一样的。

    由于我们要访问二叉树中所有的节点,所以对于遍历操作,两颗子树都要顾及。

    访问完根节点之后,既要访问根节点中所有的左子树节点,又要访问右子树中所有的节点,这种遍历通常称为二叉树的前序遍历。(先访问左右子树的前面)

    代码演示

    在我们之前实现的BST这个类中添加新的方法。

    // 二分搜索树的前序遍历
    public void preOrder(){
        preOrder(root);
    }
    
    // 前序遍历以node为根的二分搜索树, 递归算法
    private void preOrder(Node node){
        if(node == null)
            return;
    
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }
    

    重写toString方法

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }
    
    // 生成以node为根节点,深度为depth的描述二叉树的字符串
    private void generateBSTString(Node node, int depth, StringBuilder res){
    
        if(node == null){
            res.append(generateDepthString(depth) + "null\n");
            return;
        }
    
        res.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.right, depth + 1, res);
    }
    
    private String generateDepthString(int depth){
        StringBuilder res = new StringBuilder();
        for(int i = 0 ; i < depth ; i ++)
            res.append("--");
        return res.toString();
    }
    

    下面我们做一个简单的测试用例

    public class Main {
    
        public static void main(String[] args) {
    
            BST bst = new BST<>();
            int[] nums = {5, 3, 6, 8, 4, 2};
            for(int num: nums)
                bst.add(num);
    
            /////////////////
            //      5      //
            //    /   \    //
            //   3    6    //
            //  / \    \   //
            // 2  4     8  //
            ////////////////
            bst.preOrder();
            System.out.println();
    
            System.out.println(bst);
        }
    }
    

    运行程序,观察结果

    第一个是前面我们输出的结果,第二个为我们编写的输出方法打印的结果,可以观察到二叉树深结构和度。

    源码下载

    [dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

    导航目录

    [dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(5.6)二分搜索树的前序遍历

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 102会员总数(位)
    • 3674资源总数(个)
    • 2本周发布(个)
    • 0 今日发布(个)
    • 136稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级