백엔드 개발 PHP 튜토리얼 二叉树遍历算法

二叉树遍历算法

Jun 05, 2016 am 11:50 AM

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	二叉树遍历,是值从根节点出发,按照某种次序依次访问二叉树中的所有节点,使得每个节点被访问一次且仅被访问依次。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;text-align:center;">
	<img src="/static/imghw/default1.png" data-src="http://lanecn-upload.stor.sinaapp.com/image/20140709_1404896527_874807.gif" class="lazy" title="20140709_1404896527_874807.gif" alt="tupan062.gif"   style="max-width:90%"> 
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;text-align:center;">
	图是百度搜的。。。谢谢提供图的英雄。。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    前序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则先遍历左树,再遍历右树,遍历顺序为ABCDEGF。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    中序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则从根节点开始,中序遍历根节点的左子树,然后是访问根节点,最后中序遍历右子树,遍历顺序为CBEGDFA。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    后序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则从左到右先叶子后节点的访问遍历访问左右子树,最后是访问根节点。访问顺序为CGEFDBA。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    层序遍历二叉树:如果二叉树为空则返回,若二叉树非空,则从树的第一层,也就是根节点开始访问,从上而下逐层遍历,在同一层中,按照从左到右的顺序对节点逐个访问。访问顺序为ABCDEFG。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br>

</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    现在,我们用PHP代码,来遍历二叉树结构。二叉树是放一个大数组,每一个节点都有三个字段,data表示这个节点的值,lChild表示这个节点的左边子节点,rChild表示这个节点的右边子节点。二叉树的结构我们用上面那张图。
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br>

</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	二叉树结构代码如下:
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br>

</p>

<pre class='brush:php;toolbar:false;'>
<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br />

</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<?php
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	//二叉树
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	$arr = array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    'data' => 'A',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    'lChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        'data' => 'B',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        'lChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'data' => 'C',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'lChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'rChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        'rChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'data' => 'D',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'lChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'data' => 'E',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'lChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'rChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                    'data' => 'G',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                    'lChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                    'rChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            'rChild' => array(
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'data' => 'F',
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'lChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	                'rChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	            ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	        ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    ),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	    'rChild' => array(),
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	);
</p>

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">
	<br />

</p>
로그인 후 복사



遍历算法一:前序遍历二叉树


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

60

61

62

63

64

65

66

67

68

69

70

71

72

73

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    <br />

 

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    <?php

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    //前序遍历二叉树算法

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    echo '前序遍历二叉树算法:';

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    PreOrderTraverse($arr);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    echo '<Br>';

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    function PreOrderTraverse($node){

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        if(empty($node)){

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

            return;

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        }

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        //输出值

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        print_r($node['data']);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        //左节点

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        PreOrderTraverse($node['lChild']);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        //右节点

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        PreOrderTraverse($node['rChild']);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    }

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    <br />

 

</p>

로그인 후 복사



遍历算法二:中序遍历二叉树


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

60

61

62

63

64

65

66

67

68

69

70

71

72

73

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    <br />

 

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    <?php

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    //中序遍历二叉树算法

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    echo '中序遍历二叉树算法:';

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    inOrderTraverse($arr);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    echo '<Br>';

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    function inOrderTraverse($node){

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        if(empty($node)){

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

            return;

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        }

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        //左节点

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        inOrderTraverse($node['lChild']);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        //输出值

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        print_r($node['data']);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        //右节点

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        inOrderTraverse($node['rChild']);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    }

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    <br />

 

</p>

로그인 후 복사



遍历算法三:后序遍历二叉树


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

60

61

62

63

64

65

66

67

68

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    <br />

 

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;white-space:normal;">

    <?php

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    //后序遍历二叉树算法

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    echo '后序遍历二叉树算法:';

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    postOrderTraverse($arr);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    echo '<Br>';

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    function postOrderTraverse($node){

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        if(empty($node)){

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

            return;

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        }

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        //左节点

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        postOrderTraverse($node['lChild']);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        //右节点

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        postOrderTraverse($node['rChild']);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        //输出值

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

        print_r($node['data']);

</p>

 

<p style="box-sizing:border-box;margin-top:0px;margin-bottom:10px;">

    }

</p>

로그인 후 복사
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

뜨거운 기사 태그

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

11 최고의 PHP URL 쇼트너 스크립트 (무료 및 프리미엄) 11 최고의 PHP URL 쇼트너 스크립트 (무료 및 프리미엄) Mar 03, 2025 am 10:49 AM

11 최고의 PHP URL 쇼트너 스크립트 (무료 및 프리미엄)

Instagram API 소개 Instagram API 소개 Mar 02, 2025 am 09:32 AM

Instagram API 소개

Laravel의 플래시 세션 데이터로 작업합니다 Laravel의 플래시 세션 데이터로 작업합니다 Mar 12, 2025 pm 05:08 PM

Laravel의 플래시 세션 데이터로 작업합니다

Laravel 테스트에서 단순화 된 HTTP 응답 조롱 Laravel 테스트에서 단순화 된 HTTP 응답 조롱 Mar 12, 2025 pm 05:09 PM

Laravel 테스트에서 단순화 된 HTTP 응답 조롱

PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법 PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법 Mar 14, 2025 am 11:42 AM

PHP의 컬 : REST API에서 PHP Curl Extension 사용 방법

Laravel Back End : Part 2, React가있는 React 앱 구축 Laravel Back End : Part 2, React가있는 React 앱 구축 Mar 04, 2025 am 09:33 AM

Laravel Back End : Part 2, React가있는 React 앱 구축

Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트 Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트 Mar 13, 2025 pm 12:08 PM

Codecanyon에서 12 개의 최고의 PHP 채팅 스크립트

라 라벨에서 알림 라 라벨에서 알림 Mar 04, 2025 am 09:22 AM

라 라벨에서 알림

See all articles