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程序设计有所帮助。

您可能感兴趣的文章:

  • Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】
  • java编程求二叉树最大路径问题代码分析
  • 图解二叉树的三种遍历方式及java实现代码
  • java实现二叉树的创建及5种遍历方法(总结)
  • java 完全二叉树的构建与四种遍历方法示例
  • 图解红黑树及Java进行红黑二叉树遍历的方法
  • Java中二叉树数据结构的实现示例
  • Java实现求二叉树的深度和宽度
  • JAVA 实现二叉树（链式存储结构）
赞 (0)

相关推荐

  • 图解二叉树的三种遍历方式及java实现代码

    图解二叉树的三种遍历方式及java实现代码

    二叉树(binary tree)是一颗树,其中每个节点都不能有多于两个的儿子. 1.二叉树节点 作为图的特殊形式,二叉树的基本组成单元是节点与边:作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用. 如下,给出了二叉树节点的数据结构图示和相关代码: // 定义节点类: private static class BinNode { private Object element; private BinNode lChild;// 定义指向

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

  • java实现二叉树的创建及5种遍历方法(总结)

    用java实现的数组创建二叉树以及递归先序遍历,递归中序遍历,递归后序遍历,非递归前序遍历,非递归中序遍历,非递归后序遍历,深度优先遍历,广度优先遍历8种遍历方式: package myTest; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Stack; public class myClass { public static void main(

  • java 完全二叉树的构建与四种遍历方法示例

    java 完全二叉树的构建与四种遍历方法示例

    本来就是基础知识,不能丢的太干净,今天竟然花了那么长的时间才写出来,记一下. 有如下的一颗完全二叉树: 先序遍历结果应该为:1  2  4  5  3  6  7 中序遍历结果应该为:4  2  5  1  6  3  7 后序遍历结果应该为:4  5  2  6  7  3  1 层序遍历结果应该为:1  2  3  4  5  6  7 二叉树的先序遍历.中序遍历.后序遍历其实都是一样的,都是执行递归操作. 我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素检查是其是

  • JAVA 实现二叉树（链式存储结构）

    JAVA 实现二叉树（链式存储结构）

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • java编程求二叉树最大路径问题代码分析

    题目: Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example: Given the below binary tree, 1 / \ 2 3 Return 6. 节点可能为负数,寻找一条最路径使得所经过节点和最大.路径可以开始和结束于任何节点但是不能走回头路. 这道题虽然

  • Java实现求二叉树的深度和宽度

    这个是常见的对二叉树的操作.总结一下: 设节点的数据结构,如下: 复制代码 代码如下: class TreeNode {     char val;     TreeNode left = null;     TreeNode right = null; TreeNode(char _val) {         this.val = _val;     } } 1.二叉树深度 这个可以使用递归,分别求出左子树的深度.右子树的深度,两个深度的较大值+1即可. 复制代码 代码如下: // 获取最大

  • Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

    Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】

    本文实例讲述了Java实现的二叉树常用操作.分享给大家供大家参考,具体如下: import java.util.ArrayDeque; import java.util.Queue; import java.util.Stack; //二叉树的建树,前中后 递归非递归遍历 层序遍历 //Node节点 class Node { int element; Node left; Node right; public Node() { } public Node(int element) { this.

  • Java中二叉树数据结构的实现示例

    来看一个具体的习题实践: 题目 根据二叉树前序遍历序列例如:7,-7,8,#,#,-3,6,#,9,#,#,#,-5,#,#,构建二叉树,并且用前序.中序.后序进行遍历 代码 import java.util.Scanner; public class BinaryTree { public static String[] str; public static int count; /** * 静态内部类,定义二叉树节点 */ static class TreeNode { public Str

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

    本文实例讲述了Java实现打印二叉树所有路径的方法.分享给大家供大家参考,具体如下: 问题: 给一个二叉树,把所有的路径都打印出来. 比如,对于下面这个二叉树,它所有的路径为: 8 -> 3 -> 1 8 -> 2 -> 6 -> 4 8 -> 3 -> 6 -> 7 8 -> 10 -> 14 -> 13 思路: 从根节点开始,把自己的值放在一个数组里,然后把这个数组传给它的子节点,子节点同样把自己的值放在这个数组里,又传给自己的子节点,

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • Java获取此次请求URL以及服务器根路径的方法

    本文介绍了Java获取此次请求URL以及获取服务器根路径的方法,并且进行举例说明,感兴趣的朋友可以学习借鉴下文的内容. 一. 获取此次请求的URL String requestUrl = request.getScheme() //当前链接使用的协议 +"://" + request.getServerName()//服务器地址 + ":" + request.getServerPort() //端口号 + request.getContextPath() //应用

  • Java程序打印奥林匹克标志方法详解

    奥林匹克五环标志,它由5个奥林匹克环套接组成,由蓝.黑.红.黄.绿5种颜色.环从左到右互相套接,上面是蓝.黑.红环,下面是是黄.绿环.整个造形为一个底部小的规则梯形.根据奥林匹克宪章,五环的含义是象征五大洲的团结以及全世界的运动员以公正.坦率的比赛和友好的精神在奥林匹克运动会上相见.奥林匹克五环标志由皮埃尔·德·顾拜旦先生于1913年构思设计的,是由<奥林匹克宪章>确定的,也被称为奥运五环标志,它是世界范围内最为人们广泛认知的奥林匹克运动会标志.简单了解下五环标志的起源,接下来,咱们就看看怎么

  • java区分绝对路径和相对路径的方法

    本文实例讲述了java区分绝对路径和相对路径的方法.分享给大家供大家参考.具体分析如下: 这里要区分的是目录路径 如: /opt/deve/tomcat/bin c:\deve\tomcat\bin 都是绝对目录路径 bin bin/data bin\data 都是相对目录路径 通过观察,发现规律 以/开始 或者 包含\或//的都是绝对路径 或者 以/开始 或者 包含:的都是绝对路径 反之就是相对路径 介绍几个方法: startsWith public class Stringutil { pu

  • JAVA获取文件绝对路径的方法

    本文实例讲述了JAVA获取文件绝对路径的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: /** * 获取一个类的class文件所在的绝对路径. 这个类可以是JDK自身的类,也可以是用户自定义的类,或者是第三方开发包里的类. * 只要是在本程序中可以被加载的类,都可以定位到它的class文件的绝对路径. * * @param cls *            一个对象的Class属性 * @return 这个类的class文件位置的绝对路径. 如果没有这个类的定义,则返回nu

  • 基于获取JAVA路径,包括CLASSPATH外的路径的方法详解

    归纳一些网上取JAVA路径的方法: 注明:如果从ANT启动程序,this.getClass().getResource("")取出来的比较怪,直接用JAVA命令行调试就可成功.得到classpath和当前类的绝对路径的一些方法获得CLASSPATH之外路径的方法:URL base = this.getClass().getResource(""): //先获得本类的所在位置,如/home/popeye/testjava/build/classes/net/ Stri

  • C语言实现找出二叉树中某个值的所有路径的方法

    本文实例讲述了C语言实现找出二叉树中某个值的所有路径的方法,是非常常用的一个实用算法技巧.分享给大家供大家参考. 具体实现方法如下: #include <iostream> #include <vector> #include <iterator> #include <algorithm> using namespace std; vector<int> result; struct Node { Node(int i = 0, Node *pl

随机推荐