PHP实现 二叉树

//定义二叉树的节点
class Node{
    public $left = null;
    public $right = null;
    public $data = '';
    public function __construct($data){
        $this->data = $data;
    }
    //二叉树的添加
    function buildTree(Node $lchild = Null,Node $rchild = Null){
        if(!is_null($lchild)){
            $this->left = $lchild;
        }
        if(!is_null($rchild)){
            $this->right = $rchild;
        }
    }
}
//二叉树的前序遍历
function preOrder($tree){
    if($tree != null){
        echo $tree->data;
        preOrder($tree->left);
        preOrder($tree->right);
    }
}
//二叉树的中序遍历
function inOrder($tree){
    if($tree != null){
        inOrder($tree->left);
        echo $tree->data;
        inOrder($tree->right);
    }
}
//二叉树的后序遍历
function postOrder($tree){
    if($tree != null){
        postOrder($tree->left);
        postOrder($tree->right);
        echo $tree->data;
    }
}
//二叉树前序查找某个值
function preSearchOrder($tree,$value){
    if($tree != null){
        if($tree->data == $value){
            return ;
        }
        preSearchOrder($tree->left,$value);
        preSearchOrder($tree->right,$value);
    }
}
//二叉树广度优先遍历
//使用队列来实现
function breathSearchOrder($tree){
    $result = array();
    $queue = array();
    array_unshift($queue,$tree);    //插入队列头部

    while(!empty($queue)){
        $cnode = array_pop($queue);      //从队尾取出节点
        $result[] = $cnode->data;       //向数组末尾添加元素

        if($cnode->left != null){
            array_unshift($queue,$cnode->left);
        }
        if($cnode->right != null){
            array_unshift($queue,$cnode->right);
        }
    }
    return $result;
}


//二叉树深度度优先遍历
//使用栈来实现
function DeapSearchOrder($tree){
    $result = array();
    $stack = array();
    array_push($stack,$tree);

    while(!empty($stack)){
        $cnode = array_pop($stack);      //从队尾取出节点
        $result[] = $cnode->data;       //向数组末尾添加元素

        if($cnode->left != null){
            array_push($stack,$cnode->left);
        }
        if($cnode->right != null){
            array_push($stack,$cnode->right);
        }
    }
    return $result;
}

$a = new Node('A');
$b = new Node('B');
$c = new Node('C');
$d = new Node('D');
$e = new Node('E');
$f = new Node('F');
$g = new Node('G');
$h = new Node('H');
$i = new Node('I');
$a->buildTree($b,$c);
$b->buildTree($d,$e);
$c->buildTree($f,$g);
$e->buildTree($h,$i);
preOrder($a);echo "<br>";
inOrder($a);echo "<br>";
var_dump(breathSearchOrder($a));echo "<br>";
var_dump(DeapSearchOrder($a));echo "<br>";
————————————————
版权声明：本文为CSDN博主「baimayou」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_41895535/article/details/89452613