数据结构笔记总结(5.6)二分搜索树的前序遍历

二分搜索树的前序遍历

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

数据结构笔记总结(5.6)二分搜索树的前序遍历

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

二分搜索树的递归操作

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

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

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

数据结构笔记总结(5.6)二分搜索树的前序遍历

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

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

代码演示

在我们之前实现的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);
    }
}

运行程序,观察结果

数据结构笔记总结(5.6)二分搜索树的前序遍历

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

源码下载

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

导航目录

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

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(5.6)二分搜索树的前序遍历
分享到:
赞(0)

评论抢沙发

评论前必须登录!