在二进制树中递归递归 [英] In order recursion in binary trees

问题描述

有人可以向我解释在顺序遍历中递归如何工作。这里是我的inOrder（）方法。

  public void inOrder（BinaryNode p）{
 if（p.left！= null）{
 inOrder（p.left）; 
} 
 
访问（p）; 
 
 if（p.right！= null）{
 inOrder（p.right）; 
} 
 
 
} 
 public void visit（BinaryNode p）{
 System.out.println（p.element）; 
} 
 
 BinaryTree t = new BinaryTree（）; 
 t.insert（5）; 
 t.insert（t.root，4）; 
 t.insert（t.root，6）; 
 t.insert（t.root，60）; 
 t.insert（t.root，25）; 
 t.insert（t.root，10）; 
 t.inOrder（t.root）; 
  

Order（）中的方法正确打印元素，但我不明白它是如何工作的。 br>
当我调用 t.inOrder（t.root）; ，因为root具有值5，它将类似于 inOrder（5 ）;
，并且有一个左节点，所以 if（p.left！= null）{
inOrder（p.left）;
}

将被执行。递归调用将在 inOrder（4）;

由于4的左点指向null，则访问（4）是执行打印值4的行。

但是之后，5如何打印。虽然起初当方法被调用 t.inOrder（t.root）; 时，局部变量p是分配值为5的BinaryNode，现在p为4.然后在打印出4之后，可以执行的下一行是

if（p .right！= null）{
inOrder（p.right）;
}

但是由于p.right现在是指在BinaryNode中的元素4和4的右边是null，这也不会被执行。

那么递归如何维护？

如何打印出5和其余的节点？

解决方案

我已经解释了没有图像的最好的。
打印（i）意味着打印i
，并按顺序（i）意味着排序（i）被扩展为排序（我的左边）> print（i）> inorder（i） p>

inorder（5）called

todo：inorder（4）> print 5> inorder（6）

do order（4）

todo：inorder（left of 4）= nothing> print（4）> inorder 4）= nothing> print（5）

in 6 6

do print 4

do print 5

todo：inorder（6）左边=无> print 6> inorder（60）

do print 6

在60之前执行

todo：inorder（25）> print 60> inorder（right of 60）= nothing

在25号

todo：inorder（10）> print 25> inorder（25） >打印60

做10

todo：inorder（10的左边）= nothing> print 10>无序（10的权利）=无> print 25> p rint 60

do print 10

do print 25

do print 60

所以如果你看到打印的顺序4 5 6 10 25 60

Can someone please explain to me how recursion works in in Order traversal. here's my inOrder() method.

public void inOrder(BinaryNode p){
        if(p.left!=null){
            inOrder(p.left);
        }

        visit(p);

        if(p.right!=null){
            inOrder(p.right);
        }


    }
    public void visit(BinaryNode p){
        System.out.println(p.element);
    }

BinaryTree t=new BinaryTree();
        t.insert(5);
        t.insert(t.root,4);
        t.insert(t.root,6);
        t.insert(t.root,60);
        t.insert(t.root,25);
        t.insert(t.root,10);
        t.inOrder(t.root);  

The method inOrder() prints the elements correctly,but I don't understand how it works.
When I call t.inOrder(t.root); since root has value 5 it would be similar to inOrder(5); and that has a left node so if(p.left!=null){ inOrder(p.left); }

would get executed.There the recursion call would be inOrder(4);
Since 4's left points to null, then visit(4) is the line that executed printing the value 4.
But then after that how does 5 get printed.Although at first when the method was called by t.inOrder(t.root); the local variable p was assigned with BinaryNode of value 5, now p is 4. Then after printing out 4, the next line that can get executed is

if(p.right!=null){ inOrder(p.right); }
But since p.right now refers to right in BinaryNode with element 4 and 4's right is null, this also won't get executed.
Then how does the recursion is maintained?
How does it print out 5 and the rest of the nodes?

解决方案

I've explained the best i could without images. do print(i) means printing i and do inorder(i) means inorder(i) is expanded to inorder(left of i) > print (i) > inorder(right of i)

inorder(5) called

todo: inorder(4) > print 5 > inorder(6)

do inorder(4)

todo: inorder(left of 4)=nothing > print(4) > inorder(right of 4)=nothing > print(5)

inorder 6

do print 4

do print 5

do inorder 6

todo: inorder(left of 6)=nothing > print 6 > inorder(60)

do print 6

do inorder 60

todo: inorder(25) > print 60 > inorder(right of 60)=nothing

do inorder 25

todo: inorder(10) > print 25 > inorder(right of 25)=nothing > print 60

do inorder 10

todo: inorder(left of 10)=nothing > print 10 >inorder(right of 10)=nothing >print 25>print 60

do print 10

do print 25

do print 60

So if you see the order of printing its 4 5 6 10 25 60

这篇关于在二进制树中递归递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！