树的递归和非追溯遍历 [英] recursive and non resursive traversal of tree

问题描述

通过执行二进制搜索树上的递归和非递归预序遍历，我不会获得相同的结果

I am not getting the same result by executing the recursive and non recursive preorder traversal on a binary search Tree

递归方法

public static void preorder(TreeNode root) {
    if (root == null)
        return;
    else {
        System.out.print(root);
        inorder(root.getLeftPtr());
        inorder(root.getRightPtr());
    }
}

非递归方法 / p>

non recursive method

public static void preorder2(TreeNode root){
    if(root==null)return;
    Stack<TreeNode> stack=new Stack<TreeNode>();

    while(true){
        while(root!=null){
            //process current Node
            System.out.print(root);
            stack.push(root);
            root=root.getLeftPtr();
        }
        if(stack.isEmpty())break;
        root=stack.pop();
        root=root.getRightPtr();
    }

}

结果

      recursive method-> 10-> 5-> 6-> 8-> 12-> 15-> 20
  non recursive method-> 10-> 6-> 5-> 8-> 15-> 12-> 20

推荐答案

我认为你的递归方法应该是这样的，

I think your recursive method should be like this,

public static void preorder(TreeNode root) {
    if (root == null)
        return;
    else {
        System.out.print(root);
        preorder(root.getLeftPtr());
        preorder(root.getRightPtr());
    }
}

这篇关于树的递归和非追溯遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！