二叉搜索树 - 前序遍历

2020/01/06

Pre-order traversal using stack and loop

使用循环实现前序遍历时,需要注意:先插入当前节点的右子树,然后才是左子树喔~

@Setter
@Getter
public class TreeNode {
    public int val;
    private TreeNode leftNode;
    private TreeNode rightNode;
    private TreeNode parentNode;

    public TreeNode(int val){
        this.val  = val;
        leftNode  = null;
        rightNode = null;
    }
}

/**
 * Pre-order traversal using stack and while loop.
 */
public static void preOrderTraversalUsingStackAndLoop(TreeNode node){
    if (node == null) return;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(node);
    System.out.println("PreOrder traversal using stack and loop: ");

    while (!stack.isEmpty()){

        TreeNode curNode = stack.pop();
        System.out.print(curNode.getVal() + " ");
        if (curNode.getRightNode() != null){
            stack.push(curNode.getRightNode());
        }
        if (curNode.getLeftNode() != null){
            stack.push(curNode.getLeftNode());
        }
    }
}

@Test
public void preOrderTraversalUsingStackAndLoopTest(){
    TreeUtils tu = new TreeUtils();
    tu.addTreeNode(4);
    tu.addTreeNode(2);
    tu.addTreeNode(6);
    tu.addTreeNode(1);
    tu.addTreeNode(3);
    tu.addTreeNode(5);
    tu.addTreeNode(7);
    BinaryTreePrinter.printNode(tu.root);

    TreeUtils.preOrderTraversalUsingStackAndLoop(tu.root);
}

结果如下:


Pre-order traversal using recursion

使用递归方式实现前序遍历时,需要注意:当前节点为null时,应直接跳过。

 /**
 * Pre-order traversal using recursion.
 */
public static void preOrderTraversalUsingRecursion(TreeNode node){
    if (node == null) return;

    System.out.print(node.getVal() + " ");
    preOrderTraversalUsingRecursion(node.getLeftNode());
    preOrderTraversalUsingRecursion(node.getRightNode());
}

@Test
public void preOrderTraversalUsingRecursionTest(){
    TreeUtils tu = new TreeUtils();
    tu.addTreeNode(4);
    tu.addTreeNode(2);
    tu.addTreeNode(6);
    tu.addTreeNode(1);
    tu.addTreeNode(3);
    tu.addTreeNode(5);
    tu.addTreeNode(7);
    BinaryTreePrinter.printNode(tu.root);

    System.out.println("PreOrder traversal using recursion: ");
    TreeUtils.preOrderTraversalUsingRecursion(tu.root);
}

详细执行流程与结果如下所示:



一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory