二叉树的深度遍历分为前中后遍历,关于前中后遍历的概念,别的博客有讲,我们主要研究一下二叉树的创建原理和遍历的代码
首先我们创建树的节点:
private static class TreeNode {
int data;
TreeNode leftChild;
TreeNode rightChild;
TreeNode(int data) {
this.data = data;
}
}
里面有左右节点和本身的数据
由于深度遍历是以链表为基础的,所以我们创建一个链表数组
LinkedListinputList = new LinkedList (Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4,}));
接下来我们用递归的方法将数据创建一个数,这个代码最主要是画图,或者自己debug一下,我用注释讲一下
public static TreeNode createBinaryTree(LinkedListinputList){ TreeNode node = null;//创建一个空节点 if(inputList==null || inputList.isEmpty()){ return null; }//如果传入的链表数组为空,那么就创建完成了 Integer data = inputList.removeFirst();//这个函数的是取出链表第一个数据并将其删除,这样链表的长度会一点点减少,直到为empyt; if(data != null){ //这里的判空很关键。如果元素是空,说明该节点不存在,跳出这一层递归;如果元素非空,继续递归构建该节点的左右孩子。 node = new TreeNode(data);//将数据传入节点 node.leftChild = createBinaryTree(inputList);//开始左递归;递归到最后一个数据后,开始右递归 node.rightChild = createBinaryTree(inputList);//开始右递归;递归到最后一个数据后,返回上一个节点 } return node;递归到null后,如果是左节点,开始递归右节点,如果是右节点,则返回上一个节点 }
这个树是这样的:
接下来是三种遍历,其实三种遍历的思想是一样的,就是先递归哪个代码的问题;
前序遍历:
public static void preOrderTraversal(TreeNode node){
if(node == null){
return;
}
System.out.println(node.data);
preOrderTraversal(node.leftChild);
preOrderTraversal(node.rightChild);
}
前序遍历是先输出节点的数据,然后一直递归左子树,左子树递归后,递归右子树
所以结果是这样的:3 2 9 10 8 4
中序遍历:
public static void inOrderTraversal(TreeNode node){
if(node == null){
return;
}
inOrderTraversal(node.leftChild);
System.out.println(node.data);
inOrderTraversal(node.rightChild);
}
中序遍历是先递归左子树,然后输出,再递归右子树
所以结果是:9 2 10 3 8 4
后序遍历:
public static void postOrderTraversal(TreeNode node){
if(node == null){
return;
}
postOrderTraversal(node.leftChild);
postOrderTraversal(node.rightChild);
System.out.println(node.data);
}
后序遍历是先一直左递归,然后右递归,最后输出数据
所以结果是:9 10 2 4 8 3
总代码:
package tree;
import java.util.Arrays;
import java.util.LinkedList;
public class BinaryTreeTraversal {
public static TreeNode createBinaryTree(LinkedList inputList){
TreeNode node = null;
if(inputList==null || inputList.isEmpty()){
return null;
}
Integer data = inputList.removeFirst();
//这里的判空很关键。如果元素是空,说明该节点不存在,跳出这一层递归;如果元素非空,继续递归构建该节点的左右孩子。
if(data != null){
node = new TreeNode(data);
node.leftChild = createBinaryTree(inputList);
node.rightChild = createBinaryTree(inputList);
}
return node;
}
public static void preOrderTraversal(TreeNode node){
if(node == null){
return;
}
System.out.println(node.data);
preOrderTraversal(node.leftChild);
preOrderTraversal(node.rightChild);
}
public static void inOrderTraversal(TreeNode node){
if(node == null){
return;
}
inOrderTraversal(node.leftChild);
System.out.println(node.data);
inOrderTraversal(node.rightChild);
}
public static void postOrderTraversal(TreeNode node){
if(node == null){
return;
}
postOrderTraversal(node.leftChild);
postOrderTraversal(node.rightChild);
System.out.println(node.data);
}
private static class TreeNode {
int data;
TreeNode leftChild;
TreeNode rightChild;
TreeNode(int data) {
this.data = data;
}
}
public static void main(String[] args) {
LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4,}));
TreeNode treeNode = createBinaryTree(inputList);
System.out.println("前序遍历:");
preOrderTraversal(treeNode);
System.out.println("中序遍历:");
inOrderTraversal(treeNode);
System.out.println("后序遍历:");
postOrderTraversal(treeNode);
}
}



