你的位置:首页 > 软件开发 > Java > 二叉树遍历等基本操作(Java实现)

二叉树遍历等基本操作(Java实现)

发布时间:2017-12-05 02:00:16
前中后序遍历递归实现+层序遍历:树的结点类代码: public class TreeNode<Value extends Comparable<? super Value>> { private Value value; private TreeNod ...

二叉树遍历等基本操作(Java实现)

前中后序遍历递归实现+层序遍历:

树的结点类代码: 

public class TreeNode<Value extends Comparable<? super Value>> { private Value value; private TreeNode left; private TreeNode right; public Value getValue() {  return value; } public void setValue(Value value) {  this.value = value; } public TreeNode getLeft() {  return left; } public void setLeft(TreeNode left) {  this.left = left; } public TreeNode getRight() {  return right; } public void setRight(TreeNode right) {  this.right = right; } public TreeNode(Value value){  this.value = value; }}  

接下来对这颗树进行遍历:

 二叉树遍历等基本操作(Java实现)

遍历类代码:

public class Treetraversal { /**  * 前序遍历,先根遍历  *  * @param node 树的根  */ public static void preOrder(TreeNode node) {  if (node == null) return;  System.out.print(node.getValue() + "\t");  preOrder(node.getLeft());  preOrder(node.getRight()); } /**  * 中序遍历,中根遍历  *  * @param node 树的根  */ public static void inOrder(TreeNode node) {  if (node == null) return;  inOrder(node.getLeft());  System.out.print(node.getValue() + "\t");  inOrder(node.getRight()); } /**  * 后序遍历,后根遍历  *  * @param node 树的根  */ public static void postOrder(TreeNode node) {  if (node == null) return;  postOrder(node.getLeft());  postOrder(node.getRight());  System.out.print(node.getValue() + "\t"); } /**  * 层序遍历,层次遍历  *  * @param node 树的根  */ public static void levelOrder(TreeNode node) {  java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<>();  queue.add(node);  while (!queue.isEmpty()) {   TreeNode cur = queue.pop();   System.out.print(cur.getValue() + "\t");   if (cur.getLeft() != null) queue.add(cur.getLeft());   if (cur.getRight() != null) queue.add(cur.getRight());  } } public static void main(String[] args) {  //创建一颗树,一个样例  TreeNode<Character> root = new TreeNode<>('A');  root.setLeft(new TreeNode<>('B'));  root.getLeft().setLeft(new TreeNode<>('D'));  root.getLeft().setRight(new TreeNode<>('E'));  root.getLeft().getRight().setLeft(new TreeNode<>('G'));  root.setRight(new TreeNode<>('C'));  root.getRight().setRight(new TreeNode<>('F'));  preOrder(root);//A B D E G C F   System.out.println();  inOrder(root);//D B G E A C F   System.out.println();  postOrder(root);//D G E B F C A  System.out.println();  levelOrder(root);//A B C D E F G }} 

求树的深度

树结点类的代码和上面一样。测试用的树也和上面一样。

求二叉树深度的代码(递归):

 

public class TreeDepth { public static int treeDepth(TreeNode node) {  if (node == null) return 0;  return Math.max(treeDepth(node.getLeft()), treeDepth(node.getRight())) + 1; } public static void main(String[] args) {  //创建一颗树,一个样例  TreeNode<Character> root = new TreeNode<>('A');  root.setLeft(new TreeNode<>('B'));  root.getLeft().setLeft(new TreeNode<>('D'));  root.getLeft().setRight(new TreeNode<>('E'));  root.getLeft().getRight().setLeft(new TreeNode<>('G'));  root.setRight(new TreeNode<>('C'));  root.getRight().setRight(new TreeNode<>('F'));  int depth = treeDepth(root);  System.out.println(depth);//4 }}  

求二叉树叶子节点个数:

树结点类的代码和上面一样。测试用的树也和上面一样。

求二叉树叶子结点的代码(递归):

public class LeafCounter { public static int leafCount(TreeNode node) {  if (node == null) return 0;  if (node.getLeft() == null && node.getRight() == null) return 1;  return leafCount(node.getLeft()) + leafCount(node.getRight()); } public static void main(String[] args) {  //创建一颗树,一个样例  TreeNode<Character> root = new TreeNode<>('A');  root.setLeft(new TreeNode<>('B'));  root.getLeft().setLeft(new TreeNode<>('D'));  root.getLeft().setRight(new TreeNode<>('E'));  root.getLeft().getRight().setLeft(new TreeNode<>('G'));  root.setRight(new TreeNode<>('C'));  root.getRight().setRight(new TreeNode<>('F'));  int count = leafCount(root);  System.out.println(count);//3 }}

  

 

原标题:二叉树遍历等基本操作(Java实现)

关键词:JAVA

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。