数据结构与算法之二叉树的先序遍历，中序遍历，后序遍历

布满荆棘的人生 2021-12-21 17:11 221阅读 0赞

# 数据结构与算法之二叉树的先序遍历，中序遍历，后移遍历 #

--------------------

## 目录 ##

1.  实现二叉树的先序，中序，后序遍历，包括递归方式和非递归方式
2.  在二叉树中找到一个节点的后继节点

--------------------

### 1. 实现二叉树的先序，中序，后序遍历，包括递归方式和非递归方式 ###

###### 1. 先序遍历，中序遍历，后序遍历递归版 ######

//先序遍历递归版
        public static void preOrderRecur(Node head) {
        
            if (head == null) {
        
                return;
            }
            System.out.print(head.value + " ");
            preOrderRecur(head.left);
            preOrderRecur(head.right);
        }
    
        //中序遍历递归版
        public static void inOrderRecur(Node head) {
        
            if (head == null) {
        
                return;
            }
            inOrderRecur(head.left);
            System.out.print(head.value + " ");
            inOrderRecur(head.right);
        }
    
        //后序遍历递归版
        public static void posOrderRecur(Node head) {
        
            if (head == null) {
        
                return;
            }
            posOrderRecur(head.left);
            posOrderRecur(head.right);
            System.out.print(head.value + " ");
        }

###### 2. 先序遍历，中序遍历，后序遍历非递归版 ######

//先序遍历非递归版
        public static void preOrderUnRecur(Node head) {
        
            System.out.print("pre-order: ");
            if (head != null) {
        
                Stack<Node> stack = new Stack<Node>();
                stack.add(head);
                while (!stack.isEmpty()) {
        
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    if (head.right != null) {
        
                        stack.push(head.right);
                    }
                    if (head.left != null) {
        
                        stack.push(head.left);
                    }
                }
            }
            System.out.println();
        }
    
        //中序遍历非递归版
        public static void inOrderUnRecur(Node head) {
        
            System.out.print("in-order: ");
            if (head != null) {
        
                Stack<Node> stack = new Stack<Node>();
                while (!stack.isEmpty() || head != null) {
        
                    if (head != null) {
        
                        stack.push(head);
                        head = head.left;
                    } else {
        
                        head = stack.pop();
                        System.out.print(head.value + " ");
                        head = head.right;
                    }
                }
            }
            System.out.println();
        }
    
        //后序遍历非递归版1
        public static void posOrderUnRecur1(Node head) {
        
            System.out.print("pos-order: ");
            if (head != null) {
        
                Stack<Node> s1 = new Stack<Node>();
                Stack<Node> s2 = new Stack<Node>();
                s1.push(head);
                while (!s1.isEmpty()) {
        
                    head = s1.pop();
                    s2.push(head);
                    if (head.left != null) {
        
                        s1.push(head.left);
                    }
                    if (head.right != null) {
        
                        s1.push(head.right);
                    }
                }
                while (!s2.isEmpty()) {
        
                    System.out.print(s2.pop().value + " ");
                }
            }
            System.out.println();
        }
    
     //后序遍历非递归版2
        public static void posOrderUnRecur2(Node h) {
        
            System.out.print("pos-order: ");
            if (h != null) {
        
                Stack<Node> stack = new Stack<Node>();
                stack.push(h);
                Node c = null;
                while (!stack.isEmpty()) {
        
                    c = stack.peek();
                    if (c.left != null && h != c.left && h != c.right) {
        
                        stack.push(c.left);
                    } else if (c.right != null && h != c.right) {
        
                        stack.push(c.right);
                    } else {
        
                        System.out.print(stack.pop().value + " ");
                        h = c;
                    }
                }
            }
            System.out.println();
        }

###### 3. 先序，中序，后序遍历非递归解析 ######

1.  先序遍历  
    1. 如果节点不为null，则参加栈来存储节点。  
    2. 先将头节点添加到栈。  
    3. 当栈不为null时，从栈中弹出一个头节点  
    4. 由栈特性先进后出和先序遍历中左右知，先添加右节点，再添加左节点，这样弹出的时候就是先左节点，然后右节点。
2.  中序遍历
    
    1.  如果head不为null，则创建栈结构进行存储。
    2.  当栈或者head不为null时，如果head不为null，则将它的左孩子全部压入栈。
    3.  当head==null时，则弹出栈顶节点，将head指向它的右孩子。
    4.  总结就是：**当前节点为null，从栈中拿一个节点，打印，当前节点向右移。当前节点不为null，将它压入栈，当前节点向左移**；
3.  后序遍历
    
    1.  由先序遍历为中左右，后序遍历为左右中，我们可以通过两个栈，使进入栈1的顺序为中右左，然后将栈1元素放入栈2，就实现了左右中的结构。
    2.  如果head不为null，创建两个栈s1，s2,。
    3.  将head先压入s1。
    4.  当栈s1不为null时，栈s1弹出一个元素，将弹出的元素加入栈s2（即先序遍历打印的位置）
    5.  判断head左节点是否为null，不为null就加入s1，判断head右节点是否为null，不为null就加入s1.（先加左，后加右，出来就是先右，后左）
    6.  打印出s2中的元素即可。

--------------------

### 2. 在二叉树中找到一个节点的后继节点 ###

1.  题目描述  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]
2.  思路：
    
    1.  node节点如果有右孩子，则右孩子的最左节点就是后继节点。如**1的后继节点是右孩子3的最左节点6**
    2.  node节点如果没有右孩子，则往上找，找到当前节点是父节点的左孩子就停，那个父节点就是后继节点。**如5的后继节点是1的左孩子是2，所以5的后继节点是1**
3.  备注：前驱的找法：
    
    1.  node节点如果有左孩子，那么左孩子最右节点就是前驱节点，**如1的前驱节点是左孩子2的最右节点5**
    2.  如果node节点没有左孩子，则往上找，找到当前节点是父节点的右孩子就停，那个父节点就是前驱节点，**如6的前驱节点是1的右孩子3，所以6的前驱节点是1**  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]
4.  代码实现

public class Code_SuccessorNode {
        
    
    	public static class Node {
        
    		public int value;
    		public Node left;
    		public Node right;
    		public Node parent;
    
    		public Node(int data) {
        
    			this.value = data;
    		}
    	}
    
    	public static Node getSuccessorNode(Node node) {
        
    		if (node == null) {
        
    			return node;
    		}
    		if (node.right != null) {
        
    			return getLeftMost(node.right);
    		} else {
        
    			Node parent = node.parent;
    			while (parent != null && parent.left != node) {
        
    				node = parent;
    				parent = node.parent;
    			}
    			return parent;
    		}
    	}
    
    	public static Node getLeftMost(Node node) {
        
    		if (node == null) {
        
    			return node;
    		}
    		while (node.left != null) {
        
    			node = node.left;
    		}
    		return node;
    	}
    
    	public static void main(String[] args) {
        
    		Node head = new Node(6);
    		head.parent = null;
    		head.left = new Node(3);
    		head.left.parent = head;
    		head.left.left = new Node(1);
    		head.left.left.parent = head.left;
    		head.left.left.right = new Node(2);
    		head.left.left.right.parent = head.left.left;
    		head.left.right = new Node(4);
    		head.left.right.parent = head.left;
    		head.left.right.right = new Node(5);
    		head.left.right.right.parent = head.left.right;
    		head.right = new Node(9);
    		head.right.parent = head;
    		head.right.left = new Node(8);
    		head.right.left.parent = head.right;
    		head.right.left.left = new Node(7);
    		head.right.left.left.parent = head.right.left;
    		head.right.right = new Node(10);
    		head.right.right.parent = head.right;
    
    		Node test = head.left.left;
    		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
    		test = head.left.left.right;
    		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
    		test = head.left;
    		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
    		test = head.left.right;
    		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
    		test = head.left.right.right;
    		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
    		test = head;
    		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
    		test = head.right.left.left;
    		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
    		test = head.right.left;
    		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
    		test = head.right;
    		System.out.println(test.value + " next: " + getSuccessorNode(test).value);
    		test = head.right.right; // 10's next is null
    		System.out.println(test.value + " next: " + getSuccessorNode(test));
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20211220/33f339cffaa646e6b897f9914d950d0c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20211220/24572f7a6cd34e3b81e408d67fba7903.png