先序遍历:8 6 5 7 10 9 11 后序遍历:5 7 6 9 11 10 8 中序遍历:5 6 7 8 9 10 11 按层遍历:8 6 10 5 7 9 11 之字遍历:8 10 6 5 7 9 11
public static void printBTPerRecursion(TreeNode root){
if (root!=null){
System.out.print(root.value+" ");
printBTPerRecursion(root.left);
printBTPerRecursion(root.right);
}
}
public static void printBTPerUnrecursion(TreeNode node){
while (node!=null||!stack.isEmpty()){
if (node!=null){
System.out.print(node.value+" ");
stack.push(node);
node = node.left;
}
else {
node = stack.pop();
node = node.right;
}
}
}
public static void printBTMidRecursion(TreeNode root){
if (root!=null){
printBTMidRecursion(root.left);
System.out.print(root.value+" ");
printBTMidRecursion(root.right);
}
}
public static void printBTMidUnrecursion(TreeNode node){
while (node!=null||!stack.isEmpty()){
if (node!=null){
stack.push(node);
node = node.left;
}else {
TreeNode node1 = stack.pop();
System.out.print(node1.value+" ");
node = node1.right;
}
}
}
public static void printBTBackRecursion(TreeNode root){
if (root!=null){
printBTBackRecursion(root.left);
printBTBackRecursion(root.right);
System.out.print(root.value+" ");
}
}
//非递归后序遍历 参考自https://blog.csdn.net/zhuqiuhui/article/details/51319165
public static void printBTBackUnrecursion(TreeNode node){
if (node==null)return;
TreeNode curNode;
TreeNode lastVisitNode;
curNode = node;
lastVisitNode = null;
//先找到最左节点
while (curNode!=null){
stack.push(curNode);
curNode = curNode.left;
}
while (!stack.empty()){
curNode = stack.pop();
//如果此结点右节点不为空且没有被访问过,那么将它再次入栈,并顺着它的右节点再次入栈左节点
if (curNode.right!=null&&curNode.right!=lastVisitNode){
stack.push(curNode);
curNode = curNode.right;
while (curNode!=null){
stack.push(curNode);
curNode = curNode.left;
}
}else {
System.out.print(curNode.value+" ");
lastVisitNode = curNode;
}
}
}
public static void printLayerRecursion(TreeNode root) throws InterruptedException {
System.out.print(root.value+" ");
if (root.left!=null)queue.add(root.left);
if (root.right!=null)queue.add(root.right);
TreeNode treeNode = queue.poll();
if (treeNode!=null)
printLayerRecursion(treeNode);
}
public static void printLayerUnrecursion(TreeNode node){
if (node==null)return;
queue.add(node);
while (!queue.isEmpty()){
TreeNode node1 = queue.poll();
System.out.print(node1.value+" ");
if (node1.left!=null)queue.add(node1.left);
if (node1.right!= null)queue.add(node1.right);
}
}
public static void printBTlikeZHI(TreeNode node){
if (node==null)return;
stack.push(node);
int current = 0;
int next = 1;
while (!stack.empty()||!otherStack.isEmpty()){
TreeNode node1 = (TreeNode) stacks[current].pop();
System.out.print(node1.value+" ");
if (current==0){
if (node1.left!=null)stacks[next].push(node1.left);
if(node1.right!=null)stacks[next].push(node1.right);
}else {
if (node1.right!=null)stacks[next].push(node1.right);
if (node1.left!=null)stacks[next].push(node1.left);
}
if (stacks[current].empty()){
current = 1-current;
next = 1-next;
}
}
}