java - 将(BST 的)迭代层序遍历转换为递归实现

Question

我有一个工作程序，使用迭代函数的“首选”方法(参见下面的代码)打印(完整)二叉树的每个级别，但我想看看如何实现相同的程序，但使用递归方法。

虽然我同意通常有人给我写代码并不利于良好的学习；如果没有事先看到有效的实现，我在学习如何做某事时会遇到更多困难(因为没有先例)。

到目前为止我所拥有的(迭代程序):

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Collections;

public class BinaryTreeLevelWise<T extends Comparable<T>> {

    /*
     * This class represents the individual nodes of the binary tree
     * Each node has a left, right pointer of type Node
     * and Value to hold the value
     */
    class Node<T> {
        Node left;

        Node right;

        T value;

        public Node(T value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node value=" + value + "";
        }

    }

    public static void main(String[] args) {
        new BinaryTreeLevelWise().run();
    }

    /*
     * This function inserts an element into the binary tree
     */
    public <T> void insert(Node node, T value) {
        if (((Comparable<T>) value).compareTo((T) node.value) < 0) {
            if (node.left != null) {
                insert(node.left, value);
            } else {
                System.out.println("  Inserted " + value + " to left of "
                        + node.value);
                node.left = new Node(value);
            }
        } else if (((Comparable<T>) value).compareTo((T) node.value) > 0) {
            if (node.right != null) {
                insert(node.right, value);
            } else {
                System.out.println("  Inserted " + value + " to right of "
                        + node.value);
                node.right = new Node(value);
            }
        }
    }

    public void run() {

        Node root = new Node(5);
        System.out.println("Building tree with root value " + root.value);
        insert(root, 1);
        insert(root, 8);
        insert(root,-2);
        insert(root, 6);
        insert(root, 3);
        insert(root, 9);
        insert(root,-3);
        insert(root,-1);
        insert(root,-4);

        System.out.println("*************\nPrinting the tree level by level");

        printLevelWise(root);
    }

    /*
     * This functions uses a list of nodes and prints them level by level, 
     * assuming a complete binary tree.
     */
    public void printLevelWise(Node root) {
        List<List<Node>> levels = traverseLevels(root);

        int i = 0;
        for (List<Node> level : levels) {
            System.out.print("Level " + i + ": ");
            for (Node node : level) {
                System.out.print("node " + node.value + " -> ");
            }
            System.out.println();
            i++;
        }
    }

    /*
     * This function traverses the tree and puts all the nodes into a list, level by level
     */
    private List<List<Node>> traverseLevels(Node root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<List<Node>> levels = new LinkedList<>();

        Queue<Node> nodes = new LinkedList<>();
        nodes.add(root);

        while (!nodes.isEmpty()) {
            List<Node> level = new ArrayList<>(nodes.size());
            levels.add(level);

            for (Node node : new ArrayList<>(nodes)) {
                level.add(node);
                if (node.left != null) {
                    nodes.add(node.left);
                }
                if (node.right != null) {
                    nodes.add(node.right);
                }
                nodes.poll();
            }
        }
        return levels;
    }
}

此代码输出以下内容(我认为这是正确的输出):

Level 0: node 5 -> 
Level 1: node 1 -> node 8 -> 
Level 2: node -2 -> node 3 -> node 6 -> node 9 -> 
Level 3: node -3 -> node -1 -> 
Level 4: node -4 -> 

关于如何使该程序使用递归方法而不是迭代方法有什么想法吗？

Answer 1

您可以尝试以下递归方式的代码，但如果您比较复杂性，那么队列方式比递归方法遍历级别顺序更好

public void printLevelOrder(Node<T> root)
    {
        int h = height(root);//Calculate height of the tree
        int i;
        for (i=1; i<=h; i++)
        {
            printGivenLevel(root, i);
            System.out.println();
        }
    }
    private void printGivenLevel(Node<T> root, int height) {
         if (root == null)
                return;
            if (height == 1)
                System.out.print(root.value);
            else if (height > 1)
            {
                printGivenLevel(root.left, height-1);
                printGivenLevel(root.right, height-1);
            }

    }