數據結構與算法中二叉樹子結構的詳解。本站提示廣大學習愛好者：（數據結構與算法中二叉樹子結構的詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是數據結構與算法中二叉樹子結構的詳解正文
數據結構與算法中二叉樹子結構的詳解
需求
輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）
樹的描述：
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
解決思路
使用了棧將元素入棧，並不斷的彈出元素，彈出一個元素的時候，拼接成字符串，並用特殊符號進行區分，該方法主要是按照先序遍歷的方式將樹節點的數據信息拼接為字符串，這樣，兩個樹的節點拼接而成的串進行判斷是不是包含。
不過，有的資料上說可以通過遞歸的方式進行，但是我感覺以及實踐以後發現是錯誤的。後面會給出代碼，讀者自行嘗試。
public static boolean HasSubtree2(TreeNode root1, TreeNode root2) {
if (root2 == null)
return false;
String str = "";
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(null);
stack.push(root1);
TreeNode node = null;
while ((node = stack.pop()) != null) {
str += '_' + node.val + '_';
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
String str2 = "";
node = null;
stack.push(null);
stack.push(root2);
while ((node = stack.pop()) != null) {
str2 += '_' + node.val + '_';
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
if (str.contains(str2)) {
return true;
} else {
return false;
}
}
樹的構建
二叉樹而言，可以通過數組的方式進行存放，首節點放在數組0號位置處，其左節點在1號位置處，其右節點在2號位置處。由此該index的映射關系為：
index_parent.left => 2* index_parent + 1;
index_parent.right=> 2* index_parent + 2;
構建思路，左節點和右節點分別構建，根節點的左節點就一直追溯其子節點，根節點的右節點一直追溯其子節點，由此，形成的是遞歸的結構。
代碼如下：
注：這裡數組中通過-1作為區分，讀者可自行擴充。
public static TreeNode getTree(int[] node, int index) {
if (index >= node.length)
return null;
TreeNode n = null;
if (node[index] != -1) {
n = new TreeNode(node[index]);
n.left = getTree(node, index * 2 + 1);
n.right = getTree(node, index * 2 + 2);
}
return n;
}
完整代碼
包括了資料中提供的代碼，但是經過測試如下用例中是錯誤的，但是理論上說tree2應該是tree1的子結構才對。
import java.util.Stack;
public class HasSubtree {
public static void main(String[] args) {
TreeNode tree = getTree(new int[] { 8, 8, 7, 9, 2, -1, -1, -1, -1, 4, 7 }, 0);
TreeNode tree2 = getTree(new int[] { 2, 4, 7 }, 0);
boolean bool = HasSubtree(tree, tree2);
System.out.println(bool);
boolean bool2 = HasSubtree2(tree, tree2);
System.out.println(bool2);
}
public static boolean HasSubtree2(TreeNode root1, TreeNode root2) {
if (root2 == null)
return false;
String str = "";
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(null);
stack.push(root1);
TreeNode node = null;
while ((node = stack.pop()) != null) {
str += '_' + node.val + '_';
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
String str2 = "";
node = null;
stack.push(null);
stack.push(root2);
while ((node = stack.pop()) != null) {
str2 += '_' + node.val + '_';
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
if (str.contains(str2)) {
return true;
} else {
return false;
}
}
public static TreeNode getTree(int[] node, int index) {
if (index >= node.length)
return null;
TreeNode n = null;
if (node[index] != -1) {
n = new TreeNode(node[index]);
n.left = getTree(node, index * 2 + 1);
n.right = getTree(node, index * 2 + 2);
}
return n;
}
public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
boolean result = false;
if (root1 != null && root2 != null) {
if (root1.val == root2.val) {
result = isSubTree(root1, root2);
}
if (!result) {
result = isSubTree(root1.left, root2);
}
if (!result) {
result = isSubTree(root1.right, root2);
}
}
return result;
}
private static boolean isSubTree(TreeNode root1, TreeNode root2) {
if (root1 == null)
return false;
if (root2 == null)
return true;
if (root1.val != root2.val)
return false;
return isSubTree(root1.left, root2.left)
&& isSubTree(root1.right, root2.right);
}
}
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
