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

來源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語言|點(diǎn)擊：次

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

需求

輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）

樹的描述：

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ū)分，該方法主要是按照先序遍歷的方式將樹節(jié)點(diǎn)的數(shù)據(jù)信息拼接為字符串，這樣，兩個(gè)樹的節(jié)點(diǎn)拼接而成的串進(jìn)行判斷是不是包含。

不過，有的資料上說可以通過遞歸的方式進(jìn)行，但是我感覺以及實(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;
    }
  }

樹的構(gòu)建

二叉樹而言，可以通過數(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ù)組中通過-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)過測(cè)試如下用例中是錯(cuò)誤的，但是理論上說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++ 中使用lambda代替 unique_ptr 的Deleter的方法

欄目：C語言

下一篇：C++ 中pragma once 與 #ifndef _XXX_H_ #define _XXX_H_的區(qū)別

本文標(biāo)題：數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹子結(jié)構(gòu)的詳解

本文地址：http://mengdiqiu.com.cn/a1/Cyuyan/1629.html

更多C語言

欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

C語言

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

您可能感興趣的文章

閱讀排行

本欄相關(guān)

隨機(jī)閱讀