Java实现打印二叉树所有路径的方法

Java实现打印二叉树所有路径的方法

本文实例讲述了java实现打印二叉树所有路径的方法。分享给大家供大家参考，具体如下：

问题：

给一个二叉树，把所有的路径都打印出来。

比如，对于下面这个二叉树，它所有的路径为：

8 -> 3 -> 1

8 -> 2 -> 6 -> 4

8 -> 3 -> 6 -> 7

8 -> 10 -> 14 -> 13

思路：

从根节点开始，把自己的值放在一个数组里，然后把这个数组传给它的子节点，子节点同样把自己的值放在这个数组里，又传给自己的子节点，直到这个节点是叶节点，然后把这个数组打印出来。所以，我们这里要用到递归。

代码：

/**

Given a binary tree, prints out all of its root-to-leaf

paths, one per line. Uses a recursive helper to do the work.

*/

public void printPaths(Node root, int n) {

String[] path = new String[n];

printPaths(root, path, 0);

}

/**

Recursive printPaths helper -- given a node, and an array containing

the path from the root node up to but not including this node,

prints out all the root-leaf paths.

*/

private void printPaths(Node node, String[] path, int pathLen) {

if (node == null) return;

// append this node to the path array

path[pathLen++] = node.value;

// it's a leaf, so print the path that led to here

if (node.leftChild == null && node.rightChild == null) {

printArray(path, pathLen);

}

else {

// otherwise try both subtrees

printPaths(node.leftChild, path, pathLen);

printPaths(node.rightChild, path, pathLen);

}

}

/**

Utility that prints strings from an array on one line.

*/

private void printArray(String[] ints, int len) {

for (int i = 0; i < len; i++) {

System.out.print(ints[i] + " ");

}

System.out.println();

}

备注：这里只能用一个数组+一个数值才能打印出所需要的路径，如果用linkedlist之类的链表结构是不行的。值得分析一下原因，很有意思。

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。