1 <?php 2 #輸入一棵二叉樹和一個數字n，要求找出路徑和為n的所有路徑 3 4 class Node { 5 public $data = null; 6 public $parent = null; 7 public $left = null; 8 public $right = null; 9 } 10 11 #使用數組構造完全二叉樹 12 function build_cbtree($a) { 13 $root = new Node(); 14 $root->data = $a[0]; 15 16 for ($i = 1; $i < count($a); $i++) { 17 $node = new Node(); 18 $node->data = $a[$i]; 19 insert_node($root, $node); 20 } 21 22 return $root; 23 } 24 25 #插入完全二叉樹節點 26 function insert_node($root, $inode) { 27 #使用樹的廣度優先遍歷順序取出節點，直到找到第一個左右子節點沒滿的節點，將待插入節點插入節點左邊或右邊 28 $queue = array(); 29 array_unshift($queue, $root); 30 31 while (!empty($queue)) { 32 $cnode = array_pop($queue); 33 if ($cnode->left == null) { 34 $cnode->left = $inode; 35 $inode->parent = $cnode; 36 return $root; 37 } else { 38 array_unshift($queue, $cnode->left); 39 } 40 if ($cnode->right == null) { 41 $cnode->right = $inode; 42 $inode->parent = $cnode; 43 return $root; 44 } else { 45 array_unshift($queue, $cnode->right); 46 } 47 } 48 49 return $root; 50 } 51 52 #樹的廣度優先遍歷 53 function bf_traverse($root) { 54 $queue = array(); 55 array_unshift($queue, $root); 56 57 while (!empty($queue)) { 58 $cnode = array_pop($queue); 59 echo $cnode->data . " "; 60 if ($cnode->left !== null) array_unshift($queue, $cnode->left); 61 if ($cnode->right !== null) array_unshift($queue, $cnode->right); 62 } 63 64 echo "<br>"; 65 } 66 67 function get_paths($root, $paths, $sum) { 68 if ($root != null) { 69 $sum -= $root->data; 70 $paths[] = $root->data; 71 72 if ($sum > 0) { 73 #繼續遞歸 74 #此處paths是傳值調用，所以可以算出多條路徑而互不影響 75 if ($root->left != null) get_paths($root->left, $paths, $sum); 76 if ($root->right != null) get_paths($root->right, $paths, $sum); 77 } else if ($sum == 0) { 78 #輸出路徑 79 foreach ($paths as $val) { 80 echo $val . " "; 81 } 82 echo "<br>"; 83 } 84 } 85 } 86 87 $a = array(9, 8, 7, 6, 8, 4, 3, 2, 1); 88 $root = build_cbtree($a); 89 bf_traverse($root); #廣度優先遍歷 90 $b = array(); 91 get_paths($root, $b, 25); #輸出路徑和為25的路徑 92 ?>
9 8 7 6 8 4 3 2 1?
9 8 6 2?
9 8 8
