Week 3 - 树（上）

第三周 树

主要讲的是二叉树[静态二叉树，不进行删除、增加]的存储结构与遍历方式。
存储结构比较简单，还是按照Node的思想，一个Node包含自身的item，以及左子树与右子树的指向。
遍历方式：

  1. 前序、中序、后序【Print Left Right这三者的先后关系区分，主要可以利用迭代函数实现，或者递归地使用Stack】；
  2. 层序遍历【利用Queue可以递归地实现，首先，把根节点入队，然后开始做循环（出队，讲左右子树入队，直到队列为空）】

题1：树的同构

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。

图1
图1

图2
图2

现给定两棵树，请你判断它们是否是同构的。

输入格式:
输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数NNN (≤10\le 10≤10)，即该树的结点数（此时假设结点从0到N−1N-1N−1编号）；随后NNN行，第iii行对应编号第iii个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
输出格式:
如果两棵树是同构的，输出“Yes”，否则输出“No”。

输入样例1（对应图1）：

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

输出样例1:
Yes

输入样例2（对应图2）：

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

输出样例2:
No

解题思路：

  1. 根据输入构建树。
  2. 确认根节点。
  3. 迭代判断是否同构。[主要是逻辑层面的判断]
import java.util.Scanner;

public class StaticTree {

    private int N;
    private Node[] treeArray;
    private int rootIndex = -1;

    private static class Node {
        private char c;
        private int lchild;
        private int rchild;
        private boolean check = false;
    }
    public StaticTree() {
        N = 0;
        treeArray = null;
        rootIndex = -1;
    }

    public StaticTree(int N) {
        this.N = N;
        treeArray = new Node[N];
        for (int i = 0; i < N; i++)
            treeArray[i] = new Node();
        rootIndex = -1;
    }

    public void addNode(int index, char c, int lchild, int rchild) {
        if (treeArray[index] != null) {
            treeArray[index].c = c;
            treeArray[index].lchild = lchild;
            treeArray[index].rchild = rchild;
        }
        else
            System.out.println("treeArray[index] is not defined.");
    }

    public void confirmRoot() {
        if (N == 0) {
            this.rootIndex = -1;
            return;
        }

        for (int i = 0; i < N; i++) {
            int lchild = treeArray[i].lchild;
            int rchild = treeArray[i].rchild;
            if (lchild != -1)
                treeArray[lchild].check = true;
            if (rchild != -1)
                treeArray[rchild].check = true;
        }
        int i = 0;
        while (i < N) {
            if (!(treeArray[i].check))
                break;
            i++;
        }
        rootIndex = i;
    }

    public boolean isomorph(StaticTree T2, int rootT1, int rootT2) {
        if (rootT1 == -1 && rootT2 == -1)
            return true;
        if ((rootT1 != -1 && rootT2 == -1 ) || (rootT1 == -1 && rootT2 != -1))
            return false;
        if (this.treeArray[rootT1].c != T2.treeArray[rootT2].c)
            return false;
        int lchildT1 = this.treeArray[rootT1].lchild;
        int lchildT2 = T2.treeArray[rootT2].lchild;
        int rchildT1 = this.treeArray[rootT1].rchild;
        int rchildT2 = T2.treeArray[rootT2].rchild;
        if (lchildT1 == -1 && lchildT2 == -1)
            return (isomorph(T2, rchildT1, rchildT2));
        if (lchildT1 != -1 && lchildT2 != -1 && (this.treeArray[lchildT1].c == T2.treeArray[lchildT2].c))
            return (isomorph(T2, lchildT1, lchildT2) && isomorph(T2, rchildT1, rchildT2));
        else
            return (isomorph(T2, lchildT1, rchildT2) && isomorph(T2, rchildT1, lchildT2));
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            // generate T1 tree;
            int N = in.nextInt();
            in.nextLine();
            StaticTree T1 = new StaticTree(N);
            String str;
            char c;
            int lchild=0, rchild=0;
            for (int i = 0; i < N; i++) {
                str = in.nextLine();
                c = str.charAt(0);
                if (str.charAt(2) == '-')
                    lchild = -1;
                else
                    lchild = (int)str.charAt(2)-48;
                if (str.charAt(4) == '-')
                    rchild = -1;
                else
                    rchild = (int)str.charAt(4)-48;

                T1.addNode(i, c, lchild, rchild);
            }
            // generate T2 tree;
            N = in.nextInt();
            in.nextLine();
            StaticTree T2 = new StaticTree(N);
            for (int i = 0; i < N; i++) {
                str = in.nextLine();
                c = str.charAt(0);
                if (str.charAt(2) == '-')
                    lchild = -1;
                else
                    lchild = (int)str.charAt(2)-48;
                if (str.charAt(4) == '-')
                    rchild = -1;
                else
                    rchild = (int)str.charAt(4)-48;

                T2.addNode(i, c, lchild, rchild);
            }

            T1.confirmRoot();
            T2.confirmRoot();
            if (T1.isomorph(T2,T1.rootIndex,T2.rootIndex))
                System.out.println("Yes");
            else
                System.out.println("No");
        }
    }
}

题2：List Leaves

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.

Output Specification:
For each test case, print in one line all the leaves' indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input:

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Sample Output:
4 1 5

解题思路：

  1. 和前一题类似，主要还是先建立树，确定根节点。
  2. 用层序遍历的方法遍历一棵树，然后将没有左右子树的叶节点保存。
package com.zja;
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class StaticTreeLeaves {

    private int N;
    private Node[] treeArray;
    private int rootIndex = -1;

    private static class Node {
        private char c = 'o';
        private int lchild;
        private int rchild;
        private boolean check = false;
    }

    public StaticTreeLeaves() {
        N = 0;
        treeArray = null;
        rootIndex = -1;
    }

    public StaticTreeLeaves(int N) {
        this.N = N;
        treeArray = new Node[N];
        for (int i = 0; i < N; i++)
            treeArray[i] = new Node();
        rootIndex = -1;
    }

    public void addNode(int index, int lchild, int rchild) {
        if (treeArray[index] != null) {
            treeArray[index].lchild = lchild;
            treeArray[index].rchild = rchild;
        }
        else
            System.out.println("treeArray[index] is not defined.");
    }

    public void confirmRoot() {
        if (N == 0) {
            this.rootIndex = -1;
            return;
        }

        for (int i = 0; i < N; i++) {
            int lchild = treeArray[i].lchild;
            int rchild = treeArray[i].rchild;
            if (lchild != -1)
                treeArray[lchild].check = true;
            if (rchild != -1)
                treeArray[rchild].check = true;
        }
        int i = 0;
        while (i < N) {
            if (!(treeArray[i].check))
                break;
            i++;
        }
        rootIndex = i;
    }

    public int[] findLeaves(int[] result, int root, Queue<Integer> q) {
        if (root == -1)
            return result;

        q.offer(root);    // the root of the tree
        int rootIndex, lchild, rchild;
        while(!q.isEmpty()) {
            rootIndex = q.poll();
            lchild = this.treeArray[rootIndex].lchild;
            rchild = this.treeArray[rootIndex].rchild;

            if (lchild == -1 && rchild == -1)
                result[++result[0]] = rootIndex;
            if (lchild != -1)
                q.offer(lchild);
            if (rchild != -1)
                q.offer(rchild);
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            // generate T1 tree;
            int N = in.nextInt();
            in.nextLine();
            StaticTreeLeaves T1 = new StaticTreeLeaves(N);
            String str = new String();
            int lchild=-1, rchild=-1;
            for (int i = 0; i < N; i++) {
                str = in.nextLine();
                if (str.charAt(0) == '-')
                    lchild = -1;
                else
                    lchild = (int)str.charAt(0)-48;
                if (str.charAt(2) == '-')
                    rchild = -1;
                else
                    rchild = (int)str.charAt(2)-48;

                T1.addNode(i, lchild, rchild);
            }

            T1.confirmRoot();
            int[] result = new int[N+1]; 
            for (int i = 1; i < N+1; i++) {
                result[i] = -1;
            }
            result[0] = 0; // number of leavers;
            Queue<Integer> q = new LinkedList<Integer>();
            result = T1.findLeaves(result, T1.rootIndex, q);

            String rsstr = String.valueOf(result[1]);
            for (int i = 2; i < N+1; i++) {
                if (result[i] == -1)
                    break;
                rsstr += " " + String.valueOf(result[i]);
            }
            System.out.println(rsstr); 
        }
    }
}

题3：Tree Traversals Again

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Figure 1

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.
Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:
3 4 2 6 5 1

解题思路：

  1. 题目本身有点难理解，仔细看过以后，就是说一种对stack的操作，能够遍历一棵树。发现push的顺序就是前序访问的顺序，pop的顺序结果就是中序访问的结果。通过前序+中序，我们是可以得到后序的结果的。
  2. 利用前序确定根节点，结合中序确定左子树的范围和右子树的范围。
  3. 循环迭代，直到前序读取完全。
import java.util.Scanner;
import java.util.Stack;
import java.util.Arrays;

public class PostOrder {
    
    private static int[] result;    // postOrder;
    private static int[] advOrder;  // advOrder;
    private static int[] midOrder;  // midOrder;
    private static int N;           // number of nodes;
    
    public static void setPostOrder(int advLeft, int midLeft, int postLeft, int numNode) {
        // postLeft for postOrder; midLeft for # of midOrderHaveProcess; advLeft for # of rootHaveProcessed
        if (numNode == 0 || advLeft >= N)
            return;
        if (numNode == 1) {
            result[postLeft] = advOrder[advLeft];
            return;
        }
        
        int root = advOrder[advLeft];
        result[postLeft + numNode - 1] = root;
        int i;
        for (i = 0; i < numNode; i++) {
            if (midOrder[midLeft+i] == root)
                break;
        }
        
        setPostOrder(advLeft+1, midLeft, postLeft, i);                     // process left tree;
        setPostOrder(advLeft+i+1, midLeft+i+1, postLeft+i, numNode-i-1);   // process right tree;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String inputLine = new String();
        while (in.hasNext()) {
            N = in.nextInt();
            in.nextLine();
            int numPop = 0;     // number of pop operation;
            int numPush = 0;    // number of push operation;
            Stack<Integer> st = new Stack<Integer>();
            advOrder = new int[N];
            midOrder = new int[N];
            for (int i = 0; i < 2*N; i++) {
                inputLine = in.next();
                if (inputLine.substring(0,3).equals("Pop")) {
                    midOrder[numPop++] = st.pop();
                }
                    
                else {
                    advOrder[numPush++] = in.nextInt();
                    st.push(advOrder[numPush-1]);
                }
                in.nextLine();
            }

            result = new int[N];
            PostOrder.setPostOrder(0,0,0,N);
            
            String rsstr = String.valueOf(result[0]);
            for (int i = 1; i < N; i++) {
                rsstr += " " + String.valueOf(result[i]);
            }
            System.out.println(rsstr);
        }
    } 
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 树与树的表示
    编译环境：python v3.5.0, mac osx 10.11.4 前述内容： 线性表 队列 堆栈 线性结构...
    掷骰子的求阅读 2,520评论 1赞 7
  • LeetCode/LintCode ReviewPage 题解-总结
    背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪：刷leetcod...
    土汪阅读 12,787评论 0赞 33
  • 【数据结构和算法】笔记
    课程介绍 先修课：概率统计，程序设计实习，集合论与图论 后续课：算法分析与设计，编译原理，操作系统，数据库概论，人...
    ShellyWhen阅读 2,377评论 0赞 3
  • 工程接卸销售经常会遇到的六个问题
    一、销售员的人格 作为公司线下推广的主要“载体”，销售人员不仅要在装着、言谈、举止等外在形象上得体，更重要的是要有...
    hello贡阅读 992评论 0赞 0
  • 封少，好久不见
    “快起床了，再不起床就迟到了。” “嗯～～再睡一会……” “李枫你再不起来，老娘就把你从被窝儿拎出来。”
    芜恋阅读 155评论 0赞 0