php如何实现二叉树的子结构判断(代码)

阅读量:29
2021-04-17

本篇文章给大家带来的内容是关于php如何实现二叉树的子结构判断(代码),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
1.子树的意思是包含了一个节点,就得包含这个节点下的所有节点,两棵树同时到底
2.子结构可以是A树的任意一部分
思路:
1.第一个递归:A和B两棵树,先在A中找到与B的根结点相同的点,如果A的根不是,那就递归A的左右子树来找
2.第二个递归:从两棵树的根结点开始进行比较,遍历的过程中,如果B树为空,则返回true;如果B不为空,A为空,返回false
A树的结点值与B树的不同,返回false;
短路运算符&& ,递归A的左子树,B的左子树;递归A的右子树,B的右子树

HasSubtree(treeA,treeB)
    if(treeA->val==treeB->val)//根结点相同
        res=tree1HasTreeB(treeA.treeB)
    if !res
        res=HasSubtree(treeA->left.treeB)//第一层遍历
    if !res
        res=HasSubtree(treeA->right.treeB)//第一层遍历
    return res
tree1HasTreeB(treeA,treeB)
    //顺序不能变
    if treeB==null  //B到底的时候,就是true
        return true
    if treeA==null
        return /B没到底,A到底了,就是false
    if treeA->val!=treeB->val //A和B的结点没对上
        return false
    //短路语法 ,如果前面的是false,直接返回false,后面不用走
    return tree1HasTreeB(treeA->left,treeB->left)&&tree1HasTreeB(treeA->right,treeB->right)
<?php
class TreeNode{
    public $val;
    public $left = NULL;
    public $right = NULL;
    public function __construct($val){
        $this->val = $val;
    }   
}
//构造两棵树
$node1=new TreeNode(1);
$node2=new TreeNode(2);
$node3=new TreeNode(3);
$node4=new TreeNode(4);
$node5=new TreeNode(5);
$treeA=$node1;
$node1->left=$node2;
$node1->right=$node3;
$node3->left=$node4;
$node3->right=$node5;
//var_dump($treeA);
$node6=new TreeNode(3);
$node7=new TreeNode(4);
$node6->left=$node7;
$treeB=$node6;
//var_dump($treeB);
function HasSubtree($pRoot1,$pRoot2){
        $res=false;
        if($pRoot1==null || $pRoot2==null) return $res;
        if($pRoot1->val==$pRoot2->val) $res=tree1HasTree2($pRoot1,$pRoot2);
        if(!$res) $res=HasSubtree($pRoot1->left,$pRoot2);
        if(!$res) $res=HasSubtree($pRoot1->right,$pRoot2);
        return $res;
}
function tree1HasTree2($treeA,$treeB){
        if($treeB==null) return true;
        if($treeA==null) return false;
        if($treeA->val!=$treeB->val) return false;
        return tree1HasTree2($treeA->left,$treeB->left)&&tree1HasTree2($treeA->right,$treeB->right);
}
var_dump(HasSubtree($treeA,$treeB));

以上就是php如何实现二叉树的子结构判断(代码)的详细内容,更多请关注星网无限其它相关文章!

声明:本文转载于:博客园,如有侵犯,请联系admin@删除

THE END

发表评论

相关推荐

  • php getdate函数怎么用

    php getdate函数用于返回当前本地的“日期/时间”的“日期/时间”信息,其语法为“getdate(timestamp)”,该函数会返回带有与时间 ...

    阅读量:99
    2021-04-19
  • column的10篇内容推荐

    column-fill属性会将不同高度的指定列以高度差最小化的方式进行对齐,这里我们就来看一下CSS3的column-fill属性对齐列内容高 ...

    阅读量:100
    2021-04-19
  • PHPMailer 中文使用说明小结_PHP教程

    A开头: $AltBody --属性 出自:PHPMailer : $AltBody 文件:class.phpmailer .php 说明:该属性的设置是在邮件正文不支持HT ...

    阅读量:133
    2021-04-19
  • php date与gmdate的获取日期的区别_PHP教程

    date -- 格式化一个本地时间/日期   gmdate -- 格式化一个 /UTC 日期/时间,返回的是格林威治标准时(GMT)。   举个 ...

    阅读量:115
    2021-04-19
  • php 正确解码javascript中通过escape编码后的字符_PHP教程

    这是很久以前收集的一个,不知道谁写的了,但经过测试没有问题~ JavaScript代码

    阅读量:114
    2021-04-19