java三叉树中根遍历

在Java中，三叉树的根遍历可以通过递归或者使用栈来实现。下面是两种实现方法：

1. 递归实现根遍历：

class InThreadedBinaryTree {
    // 定义树的节点
    class Node {
        int data;
        Node left, middle, right;

        public Node(int item) {
            data = item;
            left = middle = right = null;
        }
    }

    Node root;

    // 根遍历
    public void rootTraversal(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            rootTraversal(node.left);
            rootTraversal(node.middle);
            rootTraversal(node.right);
        }
    }

    public static void main(String[] args) {
        InThreadedBinaryTree tree = new InThreadedBinaryTree();
        // 构建三叉树
        tree.root = tree.new Node(1);
        tree.root.left = tree.new Node(3);
        tree.root.middle = tree.new Node(2);
        tree.root.right = tree.new Node(4);
        tree.root.left.left = tree.new Node(6);
        tree.root.left.middle = tree.new Node(7);
        tree.root.left.right = tree.new Node(9);
        tree.root.middle.left = tree.new Node(1);
        tree.root.middle.middle = tree.new Node(2);
        tree.root.middle.right = tree.new Node(3);
        tree.root.right.left = tree.new Node(8);

        // 执行根遍历
        tree.rootTraversal(tree.root);
    }
}

2. 使用栈实现根遍历：

import java.util.Stack;

class InThreadedBinaryTree {
    // 定义树的节点
    class Node {
        int data;
        Node left, middle, right;

        public Node(int item) {
            data = item;
            left = middle = right = null;
        }
    }

    Node root;

    // 根遍历
    public void rootTraversal(Node node) {
        if (node == null)
            return;

        Stack<Node> stack = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()) {
            Node currNode = stack.pop();
            System.out.print(currNode.data + " ");

            if (currNode.right != null)
                stack.push(currNode.right);
            if (currNode.middle != null)
                stack.push(currNode.middle);
            if (currNode.left != null)
                stack.push(currNode.left);
        }
    }

    public static void main(String[] args) {
        InThreadedBinaryTree tree = new InThreadedBinaryTree();
        // 构建三叉树
        tree.root = tree.new Node(1);
        tree.root.left = tree.new Node(3);
        tree.root.middle = tree.new Node(2);
        tree.root.right = tree.new Node(4);
        tree.root.left.left = tree.new Node(6);
        tree.root.left.middle = tree.new Node(7);
        tree.root.left.right = tree.new Node(9);
        tree.root.middle.left = tree.new Node(1);
        tree.root.middle.middle = tree.new Node(2);
        tree.root.middle.right = tree.new Node(3);
        tree.root.right.left = tree.new Node(8);

        // 执行根遍历
        tree.rootTraversal(tree.root);
    }
}