Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

打印二叉树所有的路径

来源: beiyeqingteng 分享至:

问题:

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

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

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之类的链表结构是不行的。值得分析一下原因,很有意思。


Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史