文章目录
层次遍历
要求：
按照二叉树分层输出
思路：
用一个队列保存下一行的节点
当队列不为空的时候，出队列输出节点值，并把该节点的左右节点入队列
代码：
//层次遍历
static void levelShow(TreeNode node){
//模拟队列
LinkedList queue = new LinkedList();
//把头节点加入队列
queue.addLast(node);
//当前节点指针
TreeNode p;
while(queue.size()>0){
//出队列
p = queue.removeFirst();
System.out.print(p.value+" ");
//左节点进队列
if (p.left!=null) queue.addLast(p.left);
//右节点进队列
if (p.right!=null) queue.addLast(p.right);
}
}
分层输出的层次遍历
要求：
层次遍历二叉树，并分层输出
思路：
在层次遍历的基础上
另外用两个变量分别保存当前行的最后一个节点二叉树遍历算法 java二叉树遍历算法 java 经典二叉树算法题（Java实现），和下一行的最后一个节点
每次节点入队列，当做它是该行的最后一个节点，把它赋给
判断当前出队列的节点是否为，如果是，输出换行，把赋给，开始下一行判断
否则继续出队列
代码：
//层次遍历分层输出
static void levelShow1(TreeNode node){
//模拟队列
LinkedList queue = new LinkedList();
//把头节点加入队列
queue.addLast(node);
//当前节点指针
TreeNode p;
//记录的当前行最后一个节点
TreeNode currentlastNode = node;
//记录下一行的最后一个节点
TreeNode nextlastNode = null;
while(queue.size()>0){
p = queue.removeFirst();
System.out.print(p.value+" ");
//左节点进队列
if (p.left!=null){
queue.addLast(p.left);
nextlastNode = p.left;
}
//右节点进队列
if (p.right!=null) {
queue.addLast(p.right);
nextlastNode = p.right;
}
//如当前遍历的节点是记录行的最后一个节点，证明当前行已经遍历结束了，输出换行符
//把下一行的最后一个节点赋给当前行最后一个节点
if (currentlastNode==p) {
System.out.println();
currentlastNode = nextlastNode;
}
}
<p>![二叉树遍历算法 java_easyui java遍历树_用文字描述先(根)序的遍历二叉树算法算法,中(根)序的遍历二][1]
}</p>
数组求哈夫曼树
要求：
用数组构建一棵哈夫曼树
思路：
1把数组的所有数字保存为节点存到list里面
2对list排序，每次移除list里面最小的两个节点，新建一个节点，把这两个节点作为它的左右节点，把这个新的节点放到list里面
3重复步骤2知道list里面只剩一个节点，这个节点就是哈夫曼树的根节点
代码：
//数组构建哈夫曼树
static TreeNode haff(int[] arr) {
List list = new ArrayList();
for (int i = 0; i 1) {
Collections.sort(list, (o1, o2) -> o1.value - o2.value);
TreeNode n1 = list.get(0);
TreeNode n2 = list.get(1);
TreeNode parent = new TreeNode(n1.value + n2.value);
parent.left = n1;
parent.right = n2;
list.remove(n1);
list.remove(n2);
list.add(parent);
}
TreeNode node = list.get(0);
return node;
}
通过前序中序遍历求二叉树
要求：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
（剑指offer原题–重建二叉树）
思路：
1通过前序遍历可以找到根节点，创建根节点
2通过根节点可以在后序遍历找到，左子树的前序遍历和右子树的前序遍历的长度
3通过左右子树前序遍历的长度可以在前序遍历中找到，左右子树的前序遍历
4然后通过递归可求根节点的左节点和右节点，返回根节点
例如：
前序遍历1,2,4,7,3,5,6,8找到1是根节点，通过1在后续遍历4,7,2,1,5,3,8,6可以确定：
左子树的后续遍历为4,7,2，右子树为5,3,8,6，
回到前序遍历二叉树遍历算法 java，确定左子树的前序遍历就是2,4,7,右子树的前序遍历为3,5,6,8
代码：
<p><pre> public TreeNode reConstructBinaryTree(int [] pre,int [] last) {
//数组为空，直接返回null；
if (pre.length