第三周 樹
主要講的是二叉樹[靜態(tài)二叉樹崎逃，不進行刪除失尖、增加]的存儲結(jié)構(gòu)與遍歷方式。
存儲結(jié)構(gòu)比較簡單纬朝，還是按照Node的思想收叶，一個Node包含自身的item，以及左子樹與右子樹的指向共苛。
遍歷方式：
- 前序判没、中序、后序【Print Left Right這三者的先后關系區(qū)分隅茎，主要可以利用迭代函數(shù)實現(xiàn)澄峰，或者遞歸地使用Stack】；
- 層序遍歷【利用Queue可以遞歸地實現(xiàn)辟犀，首先俏竞，把根節(jié)點入隊，然后開始做循環(huán)（出隊堂竟，講左右子樹入隊魂毁，直到隊列為空）】
題1：樹的同構(gòu)
給定兩棵樹T1和T2。如果T1可以通過若干次左右孩子互換就變成T2出嘹，則我們稱兩棵樹是“同構(gòu)”的席楚。例如圖1給出的兩棵樹就是同構(gòu)的，因為我們把其中一棵樹的結(jié)點A税稼、B酣胀、G的左右孩子互換后，就得到另外一棵樹娶聘。而圖2就不是同構(gòu)的闻镶。
圖1
圖2
現(xiàn)給定兩棵樹，請你判斷它們是否是同構(gòu)的丸升。
輸入格式:
輸入給出2棵二叉樹樹的信息铆农。對于每棵樹，首先在一行中給出一個非負整數(shù)NNN (≤10\le 10≤10)，即該樹的結(jié)點數(shù)（此時假設結(jié)點從0到N?1N-1N?1編號）墩剖；隨后NNN行猴凹，第iii行對應編號第iii個結(jié)點，給出該結(jié)點中存儲的1個英文大寫字母岭皂、其左孩子結(jié)點的編號郊霎、右孩子結(jié)點的編號。如果孩子結(jié)點為空爷绘，則在相應位置上給出“-”书劝。給出的數(shù)據(jù)間用一個空格分隔。注意：題目保證每個結(jié)點中存儲的字母是不同的土至。
輸出格式:
如果兩棵樹是同構(gòu)的购对，輸出“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
解題思路：
- 根據(jù)輸入構(gòu)建樹骡苞。
- 確認根節(jié)點楷扬。
- 迭代判斷是否同構(gòu)躲株。[主要是邏輯層面的判斷]
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
解題思路：
- 和前一題類似揩环，主要還是先建立樹顾犹，確定根節(jié)點。
- 用層序遍歷的方法遍歷一棵樹，然后將沒有左右子樹的葉節(jié)點保存拘央。
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
解題思路：
- 題目本身有點難理解，仔細看過以后疗韵，就是說一種對stack的操作者疤，能夠遍歷一棵樹。發(fā)現(xiàn)push的順序就是前序訪問的順序，pop的順序結(jié)果就是中序訪問的結(jié)果笔时。通過前序+中序，我們是可以得到后序的結(jié)果的仗岸。
- 利用前序確定根節(jié)點允耿，結(jié)合中序確定左子樹的范圍和右子樹的范圍。
- 循環(huán)迭代扒怖，直到前序讀取完全较锡。
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);
}
}
}
