算法day09 二叉树

class Node<V>{V  value;Node left;Node right;
}

一、用递归和非递归分别实现二叉树的前序，中序，后序遍历

非递归方式：

前序遍历根左右

0）利用stack后进先出的特点

要输出根左右的顺序，将元素右边先放入栈中元素左边后放入栈中，实现先弹出左边元素再弹出右边元素。

1) 入栈顺序：

①入栈，弹出；弹出的①视为根节点

每次while循环只看这一颗小树：

③入栈，②入栈；

第二次while循环，弹出的②视为根节点：

⑤入栈， ④入栈

第三次while循环，弹出的④视为根节点：

没有元素入栈

第四次while循环，弹出的⑤视为根节点：

没有元素入栈

第五次while循环，弹出的③视为根节点：

⑦入栈， ⑥入栈

. . . . . .

2）代码实现

import java.util.Stack;public class Main {public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.right = new TreeNode(3);root.right.left = new TreeNode(6);root.right.right = new TreeNode(7);System.out.println("Inorder Traversal:");InorderTraversal.inorderTraversal(root); }
}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}class InorderTraversal {public static void inorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode current = root;stack.push(current);while ( !stack.isEmpty()) {// while (current != null) {//     stack.push(current);//     current = current.left;// }// current = stack.pop();// System.out.print(current.val + " ");// current = current.right;current  =  stack.pop();System.out.print(current.val+ " ");if(current.right!=null){stack.push(current.right);}if(current.left!=null){stack.push(current.left);}}}
}

中序遍历左根右

实现左根右的输出，从根节点①加入栈开始，再将所有左节点元素②、④依次加入到栈中

再根据栈的弹出找到最左边最先输出的树，

弹出④，再以④为根节点找④右子节点的元素，没有进入下次循环

每一次while循环只看根据栈的弹出的这一颗树

弹出②，这时根节点为②，找右子节点⑤

接着while循环以⑤为根节点

将从根节点⑤加入栈开始，如果⑤有左右节点的话，再将所有左节点元素加入到栈

. . . . . .

实质上发现while循环还是递归的另一种形式。

import java.util.Stack;public class Main {public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.right = new TreeNode(3);root.right.left = new TreeNode(6);root.right.right = new TreeNode(7);System.out.println("Inorder Traversal:");InorderTraversal.inorderTraversal(root); // Output should be 4 2 5 1 6 3 7}
}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}class InorderTraversal {public static void inorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode current = root;while (current!=null || !stack.isEmpty()) {while (current != null) {stack.push(current);current = current.left;}current = stack.pop();System.out.print(current.val + " ");current = current.right;}}
}

后序遍历左右根

再前序遍历的基础上，每次弹栈出的元素放入到新栈中，就能实现将根左右转换为右左根的顺序。

实现左右根的顺序，只需要将原来的根左右变为根右左。

import java.util.Stack;public class Main {public static void main(String[] args) {TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);root.right = new TreeNode(3);root.right.left = new TreeNode(6);root.right.right = new TreeNode(7);System.out.println("Inorder Traversal:");InorderTraversal.inorderTraversal(root); }
}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}class InorderTraversal {public static void inorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();TreeNode current = root;stack.push(current);while ( !stack.isEmpty()) {// while (current != null) {//     stack.push(current);//     current = current.left;// }// current = stack.pop();// System.out.print(current.val + " ");// current = current.right;current  =  stack.pop();stack2.push(current);//  System.out.print(current.val+ " ");if(current.left!=null){stack.push(current.left);}if(current.right!=null){stack.push(current.right);}}while(!stack2.isEmpty()){System.out.print(stack2.pop().val);}}
}

二、直观的打印一颗二叉树

三、二叉树的宽度优先遍历，找层级最大节点数

第一种方式：

1）实现层级遍历

2）哈希表记录每一节点对应的层级

3）统计每一层级对应节点数

第二种方式：

针对二叉树结构，使用队列，滚动更新变量。

定义四个变量：

currentEnd null    当前层级最后节点对象

nextEnd null 队列中最后一个节点对象

levelNum 0    当前层级节点数

  max null    最大值

遍历过程：从根节点①开始

①入栈:

                                        levelNum = 1

current = ①

①出栈：左右孩子分别进栈

                                        ②入栈， next = ②

③入栈， next = ③

①和current相同：

                                                max = levelNum

                                                levelNum = 0 //重置计数

current = next = ③

next = null //重置下一层级最后节点对象

②出栈，孩子进队列

④入栈，next为④

levelNum = 1

②与current不相同

③出栈，孩子进队列

⑤入栈，next为⑤

⑥入栈，next为⑥

                                         levelNum++

③与current相同：

                                                max = levelNum

                                                levelNum = 0  //重置计数

current = next = ⑥

next = null //重置下一层级最后节点对象

. . . . . .