php-redis-binary-tree/tree.php at master · jian1098/php-redis-binary-tree · GitHub

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
<?php

// 节点类
Class BTNode
{
    public $data;
    public $lChild;
    public $rChild;

    public function __construct($data = null)
    {
        $this->data = $data;
    }
}

// 二叉树类
Class BinaryTree
{
    public $btData;

    public function __construct($data = null)
    {
        $this->btData = $data;
    }

    //创建二叉树
    public function CreateBT(&$root = null)
    {
        $elem = array_shift($this->btData);
        if ($elem == null) {
            return 0;
        } else if ($elem == '#') {
            $root = null;
        } else {
            $root = new BTNode();
            $root->data = $elem;
            $this->CreateBT($root->lChild);
            $this->CreateBT($root->rChild);
        }
        return $root;
    }

    //先序遍历二叉树
    public function PreOrder($root)
    {
        if ($root != null) {
            echo $root->data . " ";
            $this->PreOrder($root->lChild);
            $this->PreOrder($root->rChild);

        } else {
            return;
        }
    }

    //中序遍历二叉树
    public function InOrder($root)
    {
        if ($root != null) {
            $this->InOrder($root->lChild);
            echo $root->data . " ";
            $this->InOrder($root->rChild);

        } else {
            return;
        }
    }

    //后序遍历二叉树
    public function PosOrder($root)
    {
        if ($root != null) {
            $this->PosOrder($root->lChild);
            $this->PosOrder($root->rChild);
            echo $root->data . " ";

        } else {
            return;
        }
    }

    //层序(广度优先)遍历二叉树
    function LeverOrder($root)
    {
        $queue = new SplQueue();//双向链表
        if ($root == null){
            return;
        }else{
            $queue->enqueue($root);
        }

        while (!$queue->isEmpty()) {
            $node = $queue->bottom();
            $queue->dequeue();
            echo $node->data . " ";
            if ($node->lChild){
                $queue->enqueue($node->lChild);
            }else{
//                echo $node->data.'的左子树为空';
            }
            if ($node->rChild){
                $queue->enqueue($node->rChild);
            }else{
//                echo $node->data.'的右子树为空';
            }
        }
    }
}