二叉樹的常用遍歷算法實現(xiàn)
二叉樹的形狀.png
首先定義 二叉樹千埃，節(jié)點值憔儿，左子節(jié)點，右子節(jié)點
public class TreeNode {
private int value;
private TreeNode left;
private TreeNode right;
public TreeNode(int value) {
this.value = value;
}
}
前序遍歷
- 遞歸實現(xiàn)
public static void preOrder(TreeNode treeNode) {
if (treeNode != null) {
System.out.print(treeNode.value + " ");
preOrder(treeNode.left);
preOrder(treeNode.right);
}
}
- 非遞歸實現(xiàn)（1）
- 這個是常規(guī)思路放可，先遍歷到根節(jié)點谒臼，并打印、壓棧耀里，然后遍歷其左子節(jié)點蜈缤，打印、壓棧冯挎。
- 若左子節(jié)點已經(jīng)是葉子節(jié)點底哥，則 while 循環(huán)結(jié)束，開始從棧中彈出根節(jié)點，并訪問根節(jié)點的右子樹趾徽，直到棧為空续滋，則遍歷結(jié)束。
public static void preOrderStack(TreeNode treeNode) {
if (treeNode == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode root = treeNode;
while (root != null || !stack.isEmpty()) {
while (root != null) {
// 注意和 中序非遞歸的區(qū)別孵奶，這里是先打印節(jié)點值疲酌，再去加入棧中
System.out.print(root.value + " ");
stack.push(root);
root = root.left;
}
if (!stack.isEmpty()) {
root = stack.pop();
root = root.right;
}
}
}
- 非遞歸實現(xiàn)（2）
- 這里的思路是利用棧先進(jìn)后出的性質(zhì)， 先將根節(jié)點入棧
- 循環(huán)中了袁，彈出根節(jié)點朗恳，然后先加入右子節(jié)點，后加入左子節(jié)點
- 再一次循環(huán)载绿，新彈出的節(jié)點就是剛壓入的左子節(jié)點
public static void preOrderStack1(TreeNode treeNode) {
if (treeNode == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(treeNode);
while (!stack.isEmpty()) {
TreeNode root = stack.pop();
System.out.print(root.value + " ");
if (root.right != null) {
stack.push(root.right);
}
if (root.left != null) {
stack.push(root.left);
}
}
}
中序遍歷
- 遞歸實現(xiàn)
public static void midOrder(TreeNode treeNode) {
if (treeNode != null) {
midOrder(treeNode.left);
System.out.print(treeNode.value + " ");
midOrder(treeNode.right);
}
}
- 非遞歸實現(xiàn)
- 中序遍歷是 左 根 右
public static void midOrderStack(TreeNode treeNode) {
if (treeNode == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
stack.push(treeNode);
treeNode = treeNode.left;
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
System.out.print(treeNode.value + " ");
treeNode = treeNode.right;
}
}
}
后序遍歷
- 遞歸實現(xiàn)
public static void postOrder(TreeNode treeNode) {
if (treeNode != null) {
postOrder(treeNode.left);
postOrder(treeNode.right);
System.out.print(treeNode.value + " ");
}
}
- 非遞歸實現(xiàn)
- 由于后序遍歷二叉樹的順序是 左 右 根粥诫，故可以使用中間臨時棧保存 根 右 左 的遍歷結(jié)果
public static void postOrderStack(TreeNode treeNode) {
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<TreeNode> stack1 = new Stack<TreeNode>();
while (treeNode != null || !stack.isEmpty()) {
while (treeNode != null) {
stack.push(treeNode);
stack1.push(treeNode);
treeNode = treeNode.right;
}
if (!stack.isEmpty()) {
treeNode = stack.pop();
treeNode = treeNode.left;
}
}
while (!stack1.isEmpty()) {
TreeNode treeNode1 = stack1.pop();
System.out.print(treeNode1.value + " ");
}
}
層次遍歷
public static void levelOrder(TreeNode treeNode) {
if (treeNode == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(treeNode);
while (!queue.isEmpty()) {
TreeNode root = queue.poll();
System.out.print(root.value + " ");
if (root.left != null) {
queue.add(root.left);
}
if (root.right != null) {
queue.add(root.right);
}
}
}
“之” 字型遍歷
public static void printZ(TreeNode treeNode){
if (treeNode == null){
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(treeNode);
boolean flag = true;
while (!stack1.isEmpty() || !stack2.isEmpty()){
if (flag){
while (!stack1.isEmpty()) {
treeNode = stack1.pop();
System.out.print(treeNode.value+" ");
if (treeNode.left != null) {
stack2.add(treeNode.left);
}
if (treeNode.right != null) {
stack2.add(treeNode.right);
}
}
}else {
while (!stack2.isEmpty()) {
treeNode = stack2.pop();
System.out.print(treeNode.value+" ");
if (treeNode.right != null) {
stack1.add(treeNode.right);
}
if (treeNode.left != null) {
stack1.add(treeNode.left);
}
}
}
flag = flag ^ true;
}
}
求最大深度
- 遞歸實現(xiàn)
public static int getDepth(TreeNode treeNode) {
if (treeNode == null) {
return 0;
}
int left = getDepth(treeNode.left);
int right = getDepth(treeNode.right);
return left > right ? left + 1 : right + 1;
}
- 非遞歸實現(xiàn)
public static void getDepth1(TreeNode treeNode){
if (treeNode == null){
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(treeNode);
int depth = 0;
while (!queue.isEmpty()){
int size = queue.size();
while (size > 0){
treeNode = queue.poll();
if (treeNode.left != null){
queue.add(treeNode.left);
}
if (treeNode.right != null){
queue.add(treeNode.right);
}
size--;
}
depth++;
}
System.out.println(depth);
}
求最大寬度
- 對于二叉樹，每一層的節(jié)點數(shù)是不一樣的崭庸，計算二叉樹中具有結(jié)點數(shù)最多的那一層的結(jié)點個數(shù)
用隊列實現(xiàn)怀浆，實質(zhì)就是當(dāng)當(dāng)前層節(jié)點彈出，加入下一層節(jié)點
public static void getWidth(TreeNode treeNode) {
// 根節(jié)點為空冀自，則 最大寬度為 0 揉稚；
if (treeNode == null) {
return;
}
// 此時根節(jié)點入隊，最大寬度為 1
int max = 1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(treeNode);
// 注意循環(huán)條件：隊列不為空
while (!queue.isEmpty()) {
// 記錄當(dāng)前層的節(jié)點數(shù)
int size = queue.size();
// 把當(dāng)前層的所有節(jié)點依次彈出熬粗，循環(huán)結(jié)束時，當(dāng)前層節(jié)點會全部彈出余境，此時隊列中只包含下一層的所有節(jié)點
while (size > 0) {
treeNode = queue.poll();
size--;
// 彈出的同時把下一層的節(jié)點加入隊列中
if (treeNode.left != null) {
queue.add(treeNode.left);
}
if (treeNode.right != null) {
queue.add(treeNode.right);
}
}
// 此時隊列中存放的是下一層的所有節(jié)點驻呐，比較它與上一層節(jié)點的個數(shù)，保存較大值
if (max < queue.size()) {
max = queue.size();
}
}
System.out.println(max);
}
用數(shù)組列表實現(xiàn)求最大寬度芳来，類比隊列含末，用兩個指針 i，j即舌。i 指向當(dāng)前層節(jié)點第一個佣盒，j 指向當(dāng)前層最后一個。彈出時 i++ 顽聂，加入元素時 j++肥惭；
public static void levelOrder(TreeNode treeNode){
if (treeNode == null){
return;
}
List<TreeNode> list = new ArrayList<TreeNode>();
list.add(treeNode);
int max = 1;
int i =0;
int j = 0;
// i，j 最多相等紊搪，遍歷到最后一個元素時蜜葱，i = j ，此時 i 節(jié)點左右子節(jié)點為空耀石，下一步 i 將 大于 j 牵囤，循環(huán)結(jié)束
while (i <= j){
// 臨時保存當(dāng)前層的節(jié)點數(shù)
int size = j-i+1;
while (size > 0){
treeNode = list.get(i);
if (treeNode.left != null){
list.add(treeNode.left);
j++;
}
if (treeNode.right != null){
list.add(treeNode.right);
j++;
}
size--;
i++;
}
if (max < j-i+1){
max = j-i+1;
}
}
System.out.println(max);
}
