數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹(shù)子結(jié)構(gòu)的詳解
數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹(shù)子結(jié)構(gòu)的詳解
需求
輸入兩棵二叉樹(shù)A,B,判斷B是不是A的子結(jié)構(gòu)。(ps:我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu))
樹(shù)的描述:
class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } }
解決思路
使用了棧將元素入棧,并不斷的彈出元素,彈出一個(gè)元素的時(shí)候,拼接成字符串,并用特殊符號(hào)進(jìn)行區(qū)分,該方法主要是按照先序遍歷的方式將樹(shù)節(jié)點(diǎn)的數(shù)據(jù)信息拼接為字符串,這樣,兩個(gè)樹(shù)的節(jié)點(diǎn)拼接而成的串進(jìn)行判斷是不是包含。
不過(guò),有的資料上說(shuō)可以通過(guò)遞歸的方式進(jìn)行,但是我感覺(jué)以及實(shí)踐以后發(fā)現(xiàn)是錯(cuò)誤的。后面會(huì)給出代碼,讀者自行嘗試。
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; } }
樹(shù)的構(gòu)建
二叉樹(shù)而言,可以通過(guò)數(shù)組的方式進(jìn)行存放,首節(jié)點(diǎn)放在數(shù)組0號(hào)位置處,其左節(jié)點(diǎn)在1號(hào)位置處,其右節(jié)點(diǎn)在2號(hào)位置處。由此該index的映射關(guān)系為:
index_parent.left => 2* index_parent + 1;
index_parent.right=> 2* index_parent + 2;
構(gòu)建思路,左節(jié)點(diǎn)和右節(jié)點(diǎn)分別構(gòu)建,根節(jié)點(diǎn)的左節(jié)點(diǎn)就一直追溯其子節(jié)點(diǎn),根節(jié)點(diǎn)的右節(jié)點(diǎn)一直追溯其子節(jié)點(diǎn),由此,形成的是遞歸的結(jié)構(gòu)。
代碼如下:
注:這里數(shù)組中通過(guò)-1作為區(qū)分,讀者可自行擴(kuò)充。
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; }
完整代碼
包括了資料中提供的代碼,但是經(jīng)過(guò)測(cè)試如下用例中是錯(cuò)誤的,但是理論上說(shuō)tree2應(yīng)該是tree1的子結(jié)構(gòu)才對(duì)。
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; } }
感謝閱讀,希望能幫助到大家,謝謝大家對(duì)本站的支持!
- 使用C語(yǔ)言構(gòu)建基本的二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)
- Java中二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)示例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的統(tǒng)計(jì)與轉(zhuǎn)換實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的遍歷實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的建立實(shí)例
- python數(shù)據(jù)結(jié)構(gòu)樹(shù)和二叉樹(shù)簡(jiǎn)介
相關(guān)文章
c++如何使用openssl接口來(lái)生成隨機(jī)數(shù)
OpenSSL是一個(gè)強(qiáng)大的加密庫(kù),不僅支持加密解密,還能生成隨機(jī)數(shù),設(shè)置過(guò)程包括下載資源文件、配置項(xiàng)目及修改屬性頁(yè)等步驟,確保庫(kù)文件正確包含,在Visual Studio中正確配置后,可使用RAND_bytes函數(shù)生成隨機(jī)數(shù),此過(guò)程需要注意文件路徑和附加目錄的設(shè)置2024-10-10使用C++實(shí)現(xiàn)Range序列生成器的示例代碼
在C++編程中,經(jīng)常需要迭代一系列數(shù)字或其他可迭代對(duì)象,本文將使用C++來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的Range封裝,文中的示例代碼講解詳細(xì),感興趣的可以了解下2023-11-11C++實(shí)現(xiàn)簡(jiǎn)單版通訊錄管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單版通訊錄管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-06-06C++實(shí)操之內(nèi)聯(lián)成員函數(shù)介紹
大家好,本篇文章主要講的是C++實(shí)操之內(nèi)聯(lián)成員函數(shù)介紹,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話記得收藏一下,方便下次瀏覽2021-12-12C語(yǔ)言中判斷素?cái)?shù)(求素?cái)?shù))的思路與方法實(shí)例
計(jì)算機(jī)或者相關(guān)專(zhuān)業(yè)基本上大一新生開(kāi)始學(xué)編程都會(huì)接觸的一個(gè)問(wèn)題就是判斷質(zhì)數(shù),下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中判斷素?cái)?shù)(求素?cái)?shù))的思路與方法,需要的朋友可以參考下2022-03-03一起來(lái)學(xué)習(xí)C++的構(gòu)造和析構(gòu)
這篇文章主要為大家詳細(xì)介紹了C++構(gòu)造和析構(gòu),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助2022-03-03關(guān)于C++友元類(lèi)的實(shí)現(xiàn)講解
今天小編就為大家分享一篇關(guān)于關(guān)于C++友元類(lèi)的實(shí)現(xiàn)講解,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2018-12-12