PHP實現二叉樹的深度優先與廣度優先遍歷方法

2024-05-04 23:39:19

字體：大中小

來源：轉載

供稿：網友

這篇文章主要介紹了PHP實現二叉樹的深度優先與廣度優先遍歷方法,涉及php針對二叉樹進行遍歷的相關技巧,具有一定參考借鑒價值,需要的朋友可以參考下

本文實例講述了PHP實現二叉樹的深度優先與廣度優先遍歷方法。分享給大家供大家參考。具體如下：

#二叉樹的廣度優先遍歷

#使用一個隊列實現

class Node {

public $data = null;

public $left = null;

public $right = null;

}

#@param $btree 二叉樹根節點

function breadth_first_traverse($btree) {

$traverse_data = array();

$queue = array();

array_unshift($queue, $btree); #根節點入隊

while (!empty($queue)) { #持續輸出節點，直到隊列為空

$cnode = array_pop($queue); #隊尾元素出隊

$traverse_data[] = $cnode->data;

#左節點先入隊，然后右節點入隊

if ($cnode->left != null) array_unshift($queue, $cnode->left);

if ($cnode->right != null) array_unshift($queue, $cnode->right);

}

return $traverse_data;

}

#深度優先遍歷,使用一個棧實現

function depth_first_traverse($btree) {

$traverse_data = array();

$stack = array();

array_push($stack, $btree);

while (!empty($stack)) {

$cnode = array_pop($stack);

$traverse_data[] = $cnode->data;

if ($cnode->right != null) array_push($stack, $cnode->right);

if ($cnode->left != null) array_push($stack, $cnode->left);

}

return $traverse_data;

}

$root = new Node();

$node1 = new Node();

$node2 = new Node();

$node3 = new Node();

$node4 = new Node();

$node5 = new Node();

$node6 = new Node();

$root->data = 1;

$node1->data = 2;

$node2->data = 3;

$node3->data = 4;

$node4->data = 5;

$node5->data = 6;

$node6->data = 7;

$root->left = $node1;

$root->right = $node2;

$node1->left = $node3;

$node1->right = $node4;

$node2->left = $node5;

$node2->right = $node6;

$traverse = breadth_first_traverse($root);

print_r($traverse);

echo "";

$traverse = depth_first_traverse($root);

print_r($traverse);