遍历二叉树

浅浅的花香味﹌ 2021-11-01 15:28 464阅读 0赞

用递归的方法实现前序遍历，中序遍历，后序遍历：

用递归的方法遍历的时候，其实每个节点都遍历了三遍，根据打印时间的不同，即可实现前序中序及后续，这就是三个遍历代码一样而打印顺序不一样的原因

public static class Node
       {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int data) 
    　　　　 {
                this.value = data;
            }
        }
    
        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 + " ");
        }

用非递归的方法实现前序遍历，中序遍历，后序遍历：

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();
        }
    
        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();
        }
    
        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();
        }

为什么用栈来实现遍历二叉树，而不用队列？

因为树是一个自上而下的结构，只有从上到下的路径，所以需要想一个能让它回去的路径的方法，那就是使用栈。

2、中序遍历后继节点：

如果一个节点X如果有右子树，那么X的后继节点一定是右子树的最左节点。如果X没有右子树，那么就看哪个节点的左子树是以X结尾的（一直往上找，找到某个节点是父亲节点的左孩子就停，那个父节点就是X节点的后继）。

public class 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;
        }

3、树的序列化与反序列化（做成字符串，存文本）

序列化：

public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static String serialByPre(Node head) {
            if (head == null) {
                return "#!";
            }
            String res = head.value + "!";
            res += serialByPre(head.left);
            res += serialByPre(head.right);
            return res;
        }

转载于:https://www.cnblogs.com/roscangjie/p/11039638.html