自学内容网 自学内容网

Java-数据结构-二叉树-习题(三)  ̄へ ̄

文本目录:

❄️一、习题一(前序遍历非递归):

        ▶ 思路: 

        ▶ 代码: 

 ❄️二、习题二(中序遍历非递归):

         ▶ 思路: 

        ▶ 代码: 

 ❄️三、习题三(后序遍历非递归):

         ▶ 思路: 

        ▶ 代码: 

 ❄️四、习题四(选择题):

     ➷ 选则题一:

      ➷ 选则题二:

       ➷ 选则题三:

        ➷ 选则题四:

        ➷ 选则题五:

❄️五、总结:


❄️一、习题一(前序遍历非递归):

          ☞  题的链接:

                       前序遍历非递归


        ▶ 思路: 

      对于这道题呢,我们不使用递归实现,我们呢需要使用到一种结构——栈。来实现这个前序遍历的操作,因为返回的 List<Integer>  我们呢要把每次的节点的 val 值存放到 List 里面。

     我们先把根节点放入到栈中,之后遍历左子树把其都放到栈中,当 cur 为空的时候,出栈顶节点给到 top 这个临时变量中,把 top.right 给到 cur 节点,并且我们每次入栈的节点的值都要放到List 当中最后返回的是 List 这个数据结构

     我们来看看图是如何进行的:

OK,这个呢就是我们这个题的操作流程了,我们来看看代码是如何编写的: 

        ▶ 代码 

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }

        Stack<TreeNode> stack = new Stack<>();
        //先把根节点入进来
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {

            while (cur != null) {
                //入List
                ret.add(cur.val);
                //入栈
                stack.push(cur);
                //往左子树遍历
                cur = cur.left;
            }
            //存储栈顶节点
            TreeNode top = stack.pop();
            //把栈顶的节点的右子树给到cur
            cur = top.right;
        }

        return ret;
    }

我们的前序遍历的非递归就到这结束了,当然有前序就得有 中序和后序,我们来看看。


 ❄️二、习题二(中序遍历非递归):

          ☞  题的链接:

                      中序遍历的非递归实现


         ▶ 思路: 

    对于我们这个题呢,当我们了解了上面的代码之后呢,就是非常好写了,我们对于前序遍历是:

根   左   右。我们的中序遍历呢是: 左  根  右。所以呢这个题其实就很简单了,我们只需要把我们存储到 List 的代码,改变到我们出栈顶数据之后再存储到 List 当中,并且我们要注意我们存储到List 的 val 值应该是我们出的栈顶的数据 top 的 val 值。

     我们的代码流程和上面的题是差不多的,我们只需要改变 List 的存储顺序就可以了。

     我们来看看代码如何编写:

        ▶ 代码 

public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {

            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.pop();
            //我们在这里进行存储到 List 中
            ret.add(top.val); 
            cur = top.right;
        }
        return ret;
    }

 ❄️三、习题三(后序遍历非递归):

          ☞  题的链接:

                     后序遍历的非递归实现


         ▶ 思路: 

     后序遍历是:左  右  根。我们这个题的代码呢和前面两个遍历是不一样的,这个呢我们需要判断左子树和右子树都为空的情况下,才能把这个节点的值存到 List 当中所以我们不是先出栈,我们需要先 peek 一下栈顶的数据,看是否栈顶数据的右子树是否为空,为空则打印,不为空就把其右子树的节点放到 cur 中 。但是如果这样写呢,会有一些问题,我们一会在看,我们下把我们描述的代码写下:

public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> ret = new LinkedList<>();

        if (root == null) {
            return ret;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while(cur != null || !stack.isEmpty()) {

            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.peek();
            
            if (top.right == null) {
                ret.add(top.val);
                stack.pop();
            }else {
                cur = top.right;
            }
        }
        return ret;
    }

我们来看看这个代码哪里存在问题呢? 

       所以我们需要一个临时变量,用来存储我们要出栈的节点,当我们再次循环的时候,如果 top.right == prev 这个节点,就不会进入出栈的方法中。

那么我们来看看最终的代码是什么样的:

        ▶ 代码 

public List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> ret = new LinkedList<>();
        if (root == null) {
            return ret;
        }

        Stack<TreeNode> stack = new Stack<>();

        TreeNode cur = root;
        TreeNode prev = null;

        while (cur != null || !stack.isEmpty()) {

            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode top = stack.peek();

            if (top.right == null || top.right == prev) {
                ret.add(top.val);
                stack.pop();
                prev = top;
            } else {
                cur = top.right;
            }
        }
        return ret;
    }

      到这里呢,我们关于我们前中后序的非递归遍历,就到这里就结束了,我们呢之后来看看几道选择题,这几次做代码题是不是都做腻了,我们来看看新口味:选择题。 也是关于二叉树的。


 ❄️四、习题四(选择题):

     ➷ 选则题一:

某二叉树共有 399 个节点,其中 199 个度为 2 的节点,则该二叉树中叶子节点数为 ( )

A、不存在这样的二叉树

B、200

C、198

D、199

 这个选择题呢,我们使用到的公式是 : n0(度为0的节点个数) = n2(度为2的节点的个数) + 1

这样之后我们这个题就好做了,我们的 叶子节点就是度为0 的节点,所以这个题中的叶子节点数为:n0 = 199 + 1 = 200 个,所以这题我们选择 B。 


      ➷ 选则题二:

在具有 2n 个节点的完全二叉树中,叶子结点的个数为 ( )

A、n

B、n + 1

C、n - 2

D、n / 2

     这道题呢,我们呢要考虑这个总结点个数呢是奇数还是偶数的情况下,是不一样的结果的。我们的总结点是:n0 + n1 + n2 这些节点的总数。

     当我们的总结点个数为偶数的时候呢,我们的 n1 为 1 ,

     当我们的总结点的个数为奇数的时候呢,我们的 n1 是 0。

注意:这道题我们还是需要借助 n0 = n2 + 1 这个公式

我们再来看看总结点数为奇数的情况是什么样的:   

     我们再回到这道题中,我们的总结点数为 2n 是偶数,所以这里我们使用偶数的情况进行计算,

就可以得出我们的 叶子结点(n0) 是 n 个。


       ➷ 选则题三:

我们来举一个总结点数为奇数的情况是什么样的:

                                                   一个总结点为 767 个节点的完全二叉树,其 叶子节点 个数为 ( )

A、383

B、384

C、385

D、386

   我们来看看这道题是怎样做的,我们的这个题的节点数为 767 是奇数个,所以我们使用 奇数的节点个数来计算 叶子节点。

767 = n0 + n2

767 = n0 + n0 - 1

766 = 2n0

n0 = 383

 由此可知,我们这个题的 叶子节点 的个数就是 383 个。所以我们选择 A。


        ➷ 选则题四:

  接下来我们来看看对于遍历的题:

设一颗二叉树的中序遍历为:badce,后序遍历为:bdeca,则二叉树的前序遍历是什么 ( )

A、adbce

B、decab

C、debca

D、abcde

    这种题呢,我们需要记住 前中后序  遍历的顺序,用给的两个遍历呢去还原二叉树,之后再遍历我们需要的那个二叉树就可以了。 我们来看看这道题,

    我们的 后序遍历是:左  右  根所以我们的后序遍历的最后一个值就是根节点之后到中序遍历:左   根   右去寻找根节点,把左子树和右子树分割出来,再去后序遍历中寻找 右子树的根节点,再到中序中寻找,循环执行这个操作,直至后序没有节点,这个呢就是我们的上个博客中的编码题,变成了我们的选择题。

     

     这个就是这个题的二叉树了,之后我们再对其进行前序遍历就可以了,最后我们的到 前序遍历为:abcde。所以这道题就选择 D。


        ➷ 选则题五:

某二叉树的后序遍历和中序遍历的序列是相同的,均为ABCDEF,则按照 层序遍历是 ( )

A、FEDCBA

B、CBAFED

C、DEFCBA

D、ABCDEF

   这道题呢,我们要知道我们的 后序遍历是: 左  右  根。中序遍历是:左  根  右。

   他们的遍历顺序是不同的,所以要是想要它们的遍历循序是一样的话,我们的右子树是没有节点的,这样呢结果就可以是一样的了,当我们的右子树为空后序遍历就是:先左再根。中序遍历就是:先左再根。就是一样的了。比如这道题的二叉树就可以得到这样的:

所以我们可以得知,我们的层序遍历在这里就是:FEDCBA 。所以这道题我们选择 A。


❄️五、总结:

          OK,我们的这个关于我们的二叉树的习题三但这里就结束了,同时到这里呢,我们的

数据结构 ——二叉树 也就结束了,之后呢我们进入到新的章节了,欲知后事如何,且听下回分说

拜拜啦~~~我们下篇博客再见。


原文地址:https://blog.csdn.net/2303_80388948/article/details/142302949

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!