這篇文章帶給大家的內容是關於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的右子樹
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 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)
<?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如何實作二元樹的子結構判斷(程式碼)的詳細內容。更多資訊請關注PHP中文網其他相關文章!