碼迷,mamicode.com
首頁 > 其他好文 > 詳細

遍歷二叉樹

時間:2019-06-18 17:02:36      閱讀:32      評論:0      收藏:0      [點我收藏+]

標簽:sso   his   bsp   ==   str   遍歷   node   ati   先序遍歷   

用遞歸的方法實現前序遍歷,中序遍歷,后序遍歷:

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

 

遍歷二叉樹

標簽:sso   his   bsp   ==   str   遍歷   node   ati   先序遍歷   

原文地址:https://www.cnblogs.com/roscangjie/p/11039638.html

(0)
(0)
   
舉報
評論 一句話評論(0
登錄后才能評論!
? 2014 mamicode.com 版權所有 京ICP備13008772號-2
迷上了代碼!
25选5历史开奖结果百度