题目：输入两棵二叉树A和B，判断B是不是A的子结构。二叉树结点的定义如下：
struct BinaryTreeNode{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
}
代码实现：
package com.yyq; /**
* Created by Administrator on 2015/9/15.
*/
public class SubstructureInTree {
public static boolean hashSubTree(BinaryTreeNode pRoot1, BinaryTreeNode pRoot2) {
boolean result = false;
if (pRoot1 != null && pRoot2 != null) {
if (pRoot1.getM_nValue() == pRoot2.getM_nValue()) {
result = doesTree1HaveTree2(pRoot1, pRoot2);
}
if (!result) {
result = hashSubTree(pRoot1.getM_pLeft(), pRoot2);
}
if (!result) {
result = hashSubTree(pRoot1.getM_pRight(), pRoot2);
}
}
return result;
} public static boolean doesTree1HaveTree2(BinaryTreeNode pRoot1, BinaryTreeNode pRoot2) {
if (pRoot2 == null)
return true;
if (pRoot1 == null)
return false;
if (pRoot1.getM_nValue() != pRoot2.getM_nValue())
return false;
return doesTree1HaveTree2(pRoot1.getM_pLeft(), pRoot2.getM_pLeft()) && doesTree1HaveTree2(pRoot1.getM_pRight(), pRoot2.getM_pRight());
} // ====================测试代码====================
public static void Test(String testName, BinaryTreeNode pRoot1, BinaryTreeNode pRoot2, boolean expected) {
if (hashSubTree(pRoot1, pRoot2) == expected)
System.out.println(testName + " passed.");
else
System.out.println(testName + " fail.");
} // 树中结点含有分叉，树B是树A的子结构
// 8 8
// / \ / \
// 8 7 9 2
// / \
// 9 2
// / \
// 4 7
public static void Test1() {
BinaryTreeNode pNodeA1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA2 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA3 = new BinaryTreeNode(7);
BinaryTreeNode pNodeA4 = new BinaryTreeNode(9);
BinaryTreeNode pNodeA5 = new BinaryTreeNode(2);
BinaryTreeNode pNodeA6 = new BinaryTreeNode(4);
BinaryTreeNode pNodeA7 = new BinaryTreeNode(7); pNodeA1.connectTreeNodes(pNodeA2, pNodeA3);
pNodeA2.connectTreeNodes(pNodeA4, pNodeA5);
pNodeA5.connectTreeNodes(pNodeA6, pNodeA7); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeB2 = new BinaryTreeNode(9);
BinaryTreeNode pNodeB3 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(pNodeB2, pNodeB3);
Test("Test1", pNodeA1, pNodeB1, true);
pNodeA1 = null;
pNodeB1 = null;
} // 树中结点含有分叉，树B不是树A的子结构
// 8 8
// / \ / \
// 8 7 9 2
// / \
// 9 3
// / \
// 4 7
public static void Test2() {
BinaryTreeNode pNodeA1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA2 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA3 = new BinaryTreeNode(7);
BinaryTreeNode pNodeA4 = new BinaryTreeNode(9);
BinaryTreeNode pNodeA5 = new BinaryTreeNode(3);
BinaryTreeNode pNodeA6 = new BinaryTreeNode(4);
BinaryTreeNode pNodeA7 = new BinaryTreeNode(7); pNodeA1.connectTreeNodes(pNodeA2, pNodeA3);
pNodeA2.connectTreeNodes(pNodeA4, pNodeA5);
pNodeA5.connectTreeNodes(pNodeA6, pNodeA7); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeB2 = new BinaryTreeNode(9);
BinaryTreeNode pNodeB3 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(pNodeB2, pNodeB3); Test("Test2", pNodeA1, pNodeB1, false);
pNodeA1 = null;
pNodeB1 = null;
} // 树中结点只有左子结点，树B是树A的子结构
// 8 8
// / /
// 8 9
// / /
// 9 2
// /
// 2
// /
//
public static void Test3() {
BinaryTreeNode pNodeA1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA2 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA3 = new BinaryTreeNode(9);
BinaryTreeNode pNodeA4 = new BinaryTreeNode(2);
BinaryTreeNode pNodeA5 = new BinaryTreeNode(5); pNodeA1.connectTreeNodes(pNodeA2, null);
pNodeA2.connectTreeNodes(pNodeA3, null);
pNodeA3.connectTreeNodes(pNodeA4, null);
pNodeA4.connectTreeNodes(pNodeA5, null); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeB2 = new BinaryTreeNode(9);
BinaryTreeNode pNodeB3 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(pNodeB2, null);
pNodeB2.connectTreeNodes(pNodeB3, null); Test("Test3", pNodeA1, pNodeB1, true);
pNodeA1 = null;
pNodeB1 = null;
} // 树中结点只有左子结点，树B不是树A的子结构
// 8 8
// / /
// 8 9
// / /
// 9 3
// /
// 2
// /
//
public static void Test4() {
BinaryTreeNode pNodeA1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA2 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA3 = new BinaryTreeNode(9);
BinaryTreeNode pNodeA4 = new BinaryTreeNode(2);
BinaryTreeNode pNodeA5 = new BinaryTreeNode(5); pNodeA1.connectTreeNodes(pNodeA2, null);
pNodeA2.connectTreeNodes(pNodeA3, null);
pNodeA3.connectTreeNodes(pNodeA4, null);
pNodeA4.connectTreeNodes(pNodeA5, null); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeB2 = new BinaryTreeNode(9);
BinaryTreeNode pNodeB3 = new BinaryTreeNode(3); pNodeB1.connectTreeNodes(pNodeB2, null);
pNodeB2.connectTreeNodes(pNodeB3, null); Test("Test4", pNodeA1, pNodeB1, false);
pNodeA1 = null;
pNodeB1 = null;
} // 树中结点只有右子结点，树B是树A的子结构
// 8 8
// \ \
// 8 9
// \ \
// 9 2
// \
// 2
// \
// 5
public static void Test5() {
BinaryTreeNode pNodeA1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA2 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA3 = new BinaryTreeNode(9);
BinaryTreeNode pNodeA4 = new BinaryTreeNode(2);
BinaryTreeNode pNodeA5 = new BinaryTreeNode(5); pNodeA1.connectTreeNodes(null, pNodeA2);
pNodeA2.connectTreeNodes(null, pNodeA3);
pNodeA3.connectTreeNodes(null, pNodeA4);
pNodeA4.connectTreeNodes(null, pNodeA5); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeB2 = new BinaryTreeNode(9);
BinaryTreeNode pNodeB3 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(null, pNodeB2);
pNodeB2.connectTreeNodes(null, pNodeB3); Test("Test5", pNodeA1, pNodeB1, true);
pNodeA1 = null;
pNodeB1 = null;
} // 树A中结点只有右子结点，树B不是树A的子结构
// 8 8
// \ \
// 8 9
// \ / \
// 9 3 2
// \
// 2
// \
// 5
public static void Test6() {
BinaryTreeNode pNodeA1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA2 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA3 = new BinaryTreeNode(9);
BinaryTreeNode pNodeA4 = new BinaryTreeNode(2);
BinaryTreeNode pNodeA5 = new BinaryTreeNode(5); pNodeA1.connectTreeNodes(null, pNodeA2);
pNodeA2.connectTreeNodes(null, pNodeA3);
pNodeA3.connectTreeNodes(null, pNodeA4);
pNodeA4.connectTreeNodes(null, pNodeA5); BinaryTreeNode pNodeB1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeB2 = new BinaryTreeNode(9);
BinaryTreeNode pNodeB3 = new BinaryTreeNode(3);
BinaryTreeNode pNodeB4 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(null, pNodeB2);
pNodeB2.connectTreeNodes(pNodeB3, pNodeB4); Test("Test6", pNodeA1, pNodeB1, false);
pNodeA1 = null;
pNodeB1 = null;
} // 树A为空树
public static void Test7() {
BinaryTreeNode pNodeB1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeB2 = new BinaryTreeNode(9);
BinaryTreeNode pNodeB3 = new BinaryTreeNode(3);
BinaryTreeNode pNodeB4 = new BinaryTreeNode(2); pNodeB1.connectTreeNodes(null, pNodeB2);
pNodeB2.connectTreeNodes(pNodeB3, pNodeB4); Test("Test7", null, pNodeB1, false);
pNodeB1 = null;
} // 树B为空树
public static void Test8() {
BinaryTreeNode pNodeA1 = new BinaryTreeNode(8);
BinaryTreeNode pNodeA2 = new BinaryTreeNode(9);
BinaryTreeNode pNodeA3 = new BinaryTreeNode(3);
BinaryTreeNode pNodeA4 = new BinaryTreeNode(2); pNodeA1.connectTreeNodes(null, pNodeA2);
pNodeA2.connectTreeNodes(pNodeA3, pNodeA4); Test("Test8", pNodeA1, null, false);
pNodeA1 = null;
} // 树A和树B都为空
public static void Test9() {
Test("Test9", null, null, false);
} public static void main(String[] args) {
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
Test8();
Test9();
}
}
输出结果：
Test1 passed.
Test2 passed.
Test3 passed.
Test4 passed.
Test5 passed.
Test6 passed.
Test7 passed.
Test8 passed.
Test9 passed.