遍历Java中二叉树的所有节点 [英] Traversing through all nodes of a binary tree in Java

问题描述

假设我有一个简单的二叉树节点类，如下所示：

Let's say I have a simple binary tree node class, like so:

public class BinaryTreeNode {
    public String identifier = "";
    public BinaryTreeNode parent = null;
    public BinaryTreeNode left = null;
    public BinaryTreeNode right = null;

    public BinaryTreeNode(BinaryTreeNode parent, String identifier)
    {
        this.parent = parent; //passing null makes this the root node
        this.identifier = identifier;
    }

    public boolean IsRoot() {
        return parent == null;
    }
}

我如何添加一个能够递归的方法遍历任何大小的树，从左到右访问每个现有节点，没有重新访问已经遍历过的节点？


这会有效吗？ ：

How would I add a method which is able to recursively traverse through any size tree, visiting each and every existing node from left to right, without revisiting a node that has already been traversed?

Would this work?:

public void traverseFrom(BinaryTreeNode rootNode)
{
    /* insert code dealing with this node here */

    if(rootNode.left != null)
        rootNode.left.traverseFrom(rootNode.left);

    if(rootNode.right != null)
        rootNode.traverseFrom(rootNode.right);
}

推荐答案

二元有三种类型你可以实现的树遍历：

There are 3 types of Binary tree traversal that you can achieve :

示例：

考虑以下二叉树：

Pre-order traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)
In-order traversal sequence: A, B, C, D, E, F, G, H ,I (left, root, right)
Post-order traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)

代码示例：

从二进制树的左到右遍历，不按顺序遍历二叉树：

left to right traversal of the Binary tree, nay In order Traversal of binary tree :

public void traverse (Node root){ // Each child of a tree is a root of its subtree.
    if (root.left != null){
        traverse (root.left);
    }
    System.out.println(root.data);
    if (root.right != null){
        traverse (root.right);
    }
}

这篇关于遍历Java中二叉树的所有节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！