Maison > développement back-end > tutoriel php > PHP实现二叉树的深度优先与广度优先遍历方法_PHP

PHP实现二叉树的深度优先与广度优先遍历方法_PHP

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Libérer: 2016-05-30 08:44:33
original
1138 Les gens l'ont consulté

本文实例讲述了PHP实现二叉树的深度优先与广度优先遍历方法。分享给大家供大家参考。具体如下:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

#二叉树的广度优先遍历

#使用一个队列实现

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);

Copier après la connexion

希望本文所述对大家的php程序设计有所帮助。

Étiquettes associées:
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers numéros
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal