欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹(shù)子結(jié)構(gòu)的詳解

 更新時(shí)間:2017年04月26日 09:44:14   投稿:lqh  
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹(shù)子結(jié)構(gòu)的詳解的相關(guān)資料,需要的朋友可以參考下

數(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ì)本站的支持!

相關(guān)文章

  • C++中new和delete的介紹

    C++中new和delete的介紹

    今天小編就為大家分享一篇關(guān)于C++中new和delete的介紹,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2018-12-12
  • c++如何使用openssl接口來(lái)生成隨機(jī)數(shù)

    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++實(shí)現(xiàn)Range序列生成器的示例代碼

    在C++編程中,經(jīng)常需要迭代一系列數(shù)字或其他可迭代對(duì)象,本文將使用C++來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的Range封裝,文中的示例代碼講解詳細(xì),感興趣的可以了解下
    2023-11-11
  • 深入了解c++11 移動(dòng)語(yǔ)義與右值引用

    深入了解c++11 移動(dòng)語(yǔ)義與右值引用

    這篇文章主要介紹了c++ 移動(dòng)語(yǔ)義與右值引用的相關(guān)資料,幫助大家更好的理解和學(xué)習(xí)c++,感興趣的朋友可以了解下
    2020-08-08
  • C++實(shí)現(xiàn)簡(jiǎn)單版通訊錄管理系統(tǒng)

    C++實(shí)現(xiàn)簡(jiǎn)單版通訊錄管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單版通訊錄管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-06-06
  • 淺談c++ hook 鉤子的使用介紹

    淺談c++ hook 鉤子的使用介紹

    本篇文章主要介紹了淺談c++ hook 鉤子的使用介紹,詳細(xì)的介紹了c++ hook 鉤子的原理和運(yùn)行機(jī)制,有興趣的可以了解一下
    2017-11-11
  • C++實(shí)操之內(nèi)聯(lián)成員函數(shù)介紹

    C++實(shí)操之內(nèi)聯(lián)成員函數(shù)介紹

    大家好,本篇文章主要講的是C++實(shí)操之內(nèi)聯(lián)成員函數(shù)介紹,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話記得收藏一下,方便下次瀏覽
    2021-12-12
  • C語(yǔ)言中判斷素?cái)?shù)(求素?cái)?shù))的思路與方法實(shí)例

    C語(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)

    一起來(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)于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

最新評(píng)論