时间:2021-05-19
本文实例讲述了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-leafpaths, 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 containingthe 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程序设计有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
二叉树中和为某一值的路径:输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点
题目描述输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。思路:首先要
给定一个二叉树,找出所有路径中各节点相加总和等于给定目标值的路径。一个有效的路径,指的是从根节点到叶节点的路径。样例给定一个二叉树,和目标值=5:1/\24/\
什么是二叉树,这里不再介绍,可以自行百度:二叉树。在这里利用java实现“表达式二叉树”。表达式二叉树的定义第一步先要搞懂表达式二叉树是个什么东东?举个栗子,表
Java二叉树排序算法排序二叉树的描述也是一个递归的描述,所以排序二叉树的构造自然也用递归的:排序二叉树的3个特征:1:当前node的所有左孩子的值都小于当前n