欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-28 14:20:57
本文实例讲述了java实现打印二叉树所有路径的方法。分享给大家供大家参考,具体如下: 问题: 给一个二叉树,把所有的路径都打印出来。 比如,对于下面这个二叉树,它所有...

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

问题:

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

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

8 -> 3 -> 1
8 -> 2 -> 6 -> 4
8 -> 3 -> 6 -> 7
8 -> 10 -> 14 -> 13

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

思路:

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

代码:

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