php如何实现二叉树的子结构判断（代码）
php如何实现二叉树的子结构判断（代码）
内容导读
收集整理的这篇技术教程文章主要介绍了php如何实现二叉树的子结构判断（代码），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2324字，纯文字阅读大概需要4分钟。
内容图文
本篇文章给大家带来的内容是关于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 restree1HasTreeB(treeA,treeB) //顺序不能变 if treeB==null //B到底的时候，就是true return true if treeA==null return false//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)
<?phpclass 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如何实现二叉树的子结构判断（代码）的详细内容，更多请关注Gxl网其它相关文章！
内容总结
以上是为您收集整理的php如何实现二叉树的子结构判断（代码）全部内容，希望文章能够帮你解决php如何实现二叉树的子结构判断（代码）所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
