二叉树的层序遍历算法 + 打印二叉树所有最左边的元素（算法）

层序遍历

/**
* 树结构定义
*/
private static class BinaryNode {BinaryNode(T theElement) {this(theElement, null, null);}BinaryNode(T theElement, BinaryNode lt, BinaryNode rt) {element = theElement;left = lt;right = rt;}T element;BinaryNode left;BinaryNode right;
}//层序遍历方法
public static void levelRead(BinaryNode node) {if (node == null) {return;}//计算深度int depth = calcDepth(node);for (int i = 0; i < depth; i++) {//打印每个深度上的所有节点readLevel(node,i);}}private static void readLevel(BinaryNode node, int i) {if (node == null||i<1) {return;}//递归打印，如果层级为1，则打印当前节点，如果不为1，则说明还在比较高的等级，需要递归从头往下继续找当前层。if (i == 1) {System.out.print(node.element+"  ");}readLevel(node.left, i-1);readLevel(node.right, i-1);}private static int calcDepth(BinaryNode node) {if (node ==null) {return 0;}int ld = calcDepth(node.left);int rd = calcDepth(node.right);if (ld>rd) {return ld+1;}else{return rd+1;}
}

打印二叉树所有最左边的元素

在层序遍历的基础上，我们可以借此实现打印二叉树上所有最左边的元素，代码如下：

public static void levelReadLeft(BinaryNode node) {if (node == null) {return;}int depth = calcDepth(node);for (int i = 1; i <= depth; i++) {String string = readLevelLeft(node,i);System.out.println(string);}
}private static String readLevelLeft(BinaryNode node, int i) {String reString = "";if (node == null||i<1) {return reString;}if (i == 1) {return reString + (node.element+"  ");}reString += readLevelLeft(node.left, i-1);if (reString.equals ("")) {reString += readLevelLeft(node.right, i-1);}return reString;
}private static int calcDepth(BinaryNode node) {if (node ==null) {return 0;}int ld = calcDepth(node.left);int rd = calcDepth(node.right);if (ld>rd) {return ld+1;}else{return rd+1;}
}

从顶层遍历最右边节点

代码如下：

 public static void levelReadRight(BinaryNode node) {if (node == null) {return;}int depth = calcDepth(node);for (int i = 1; i <= depth; i++) {String string = readLevelRight(node,i);System.out.println(string);}
}private static String readLevelRight(BinaryNode node, int i) {String reString = "";if (node == null||i<1) {return reString;}if (i == 1) {return reString + (node.element+"  ");}reString += readLevelRight(node.right, i-1);if (reString.equals ("")) {reString += readLevelRight(node.left, i-1);}return reString;
}private static int calcDepth(BinaryNode node) {if (node ==null) {return 0;}int ld = calcDepth(node.left);int rd = calcDepth(node.right);if (ld>rd) {return ld+1;}else{return rd+1;}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！