使用PHP创建二叉树

创建二叉树

<?php
/**
 * Created by PhpStorm.
 * User: zooeymoon
 * Date: 2018/5/20
 * Time: 21:12
 */

class TreeNode{

    private $data;
    private $left;
    private $right;

    public function __construct($data,$left,$right)
    {

        $this->data = $data;
        $this->left = $left;
        $this->right = $right;

    }


    public function setLeft($left)
    {
        $this->left = $left;
    }

    public function getLeft()
    {
        return $this->left;
    }

    public function setRight($right)
    {
        $this->right = $right;
    }

    public function getRight()
    {
        return $this->right;
    }

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

    public function getData()
    {
        return $this->data;
    }



}

class BST{

    private $root;

    public function __construct($root = null)
    {
        $this->root = new TreeNode($root,"","");
    }

    public function getRoot()
    {
        return $this->root;
    }

    public function insert($data)
    {

        $n = new TreeNode($data,"","");

        if($this->root->getData() == null){
            $this->root = $n;
        }else{

            $current = $this->root;

            while(true){

                $parent = $current;

                if($data < $current->getData()){

                    $current = $current->getLeft();


                    if($current == null){

                        $parent->setLeft($n);
                        break;

                    }


                }else{

                    $current = $current->getRight();


                    if($current == null){

                        $parent->setRight($n);
                        break;

                    }

                }

            }
        }

    }


    public function inOrder($data)
    {
        if($data != null){
            $this->inOrder($data->getLeft());
            echo $data->getData();
            echo "<br/>";
            $this->inOrder($data->getRight());
        }
    }

    public function preOrder($data)
    {
        if($data != null){

            echo $data->getData();
            echo "<br/>";
            $this->inOrder($data->getLeft());
            $this->inOrder($data->getRight());

        }
    }

    public function postOrder($data)
    {
        if($data != null){

            $this->postOrder($data->getLeft());
            $this->postOrder($data->getRight());
            echo $data->getData();
            echo "<br/>";

        }
    }


    public function getMin()
    {
        $current = $this->root;

        while($current->getLeft() != null){
            $current = $current->getLeft();
        }

        return $current->getData();

    }


    public function getSmallest($node)
    {
        while($node->getLeft() != null){
            $current = $node->getLeft();
        }

        return $node->getData();
    }

    public function getMax()
    {
        $current = $this->root;

        while($current->getRight() != null){
            $current = $current->getRight();
        }

        return $current->getData();

    }

    //查找节点
    public function find($data)
    {

        $current = $this->root;

        while ($current != null){

            if($current->getData() == $data){

                return $current;

            }elseif ( $data < $current->getData()){

                $current = $current->getLeft();

            }else{

                $current = $current->getRight();

            }

        }

        return false;

    }


    public function remove($data)
    {
        $this->root = $this->removeNode($this->root , $data);
    }


    //移除节点    
    public function removeNode($node , $data)
    {
        if($node == null){

            return null;

        }


        if($node->getData() == $data){

            if($node->getRight() == null && $node->getLeft() == null){

                return null;

            }

            //如果没有左节点
            if($node->getLeft() == null){

                return $node->getRight();

            }

            //如果没有右节点
            if($node->getRight() == null){

                return $node->getLeft();

            }

            $tempNode = getSmallest($node->getRight());
            $node->setData( $this->getSmallest($node->getRight()));
            $node->setRight($this->removeNode($node->getRight(),$tempNode->getData()));
            return $node;

        }

        elseif ($data < $node->getData()){

            $node->setLeft($this->removeNode($node->getLeft() , $data));

            return $node;

        }else{

            $node->setRight($this->removeNode($node->getRight() , $data));

            return $node;

        }

    }

}

$tree = new BST(55);
$tree->insert(23);
$tree->insert(45);
$tree->insert(16);
$tree->insert(37);
$tree->insert(3);
$tree->insert(99);
$tree->insert(22);

$tree->inOrder($tree->getRoot());

$tree->remove(45);

echo "<br/>";

$tree->inOrder($tree->getRoot());

echo "<br/>";

$tree->preOrder($tree->getRoot());

echo "<br/>";

$tree->postOrder($tree->getRoot());