二叉树

<?php
/**
 * Created by PhpStorm.
 * User: Alex
 * Date: 2019/5/13
 * Time: 12:02
 */


// 排序二叉树
// 完成以下任务.
// 1. 将节点插入到对应位置
// 2. 使用中序遍历遍历这个二叉树
// 3. 找到这个二叉树的极值
// 4. 搜索一个特定的值
class  Node
{
    public $key, $left, $right;

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

class BinaryTree
{
    public $root;
    public $sortArr = [];

    public function insertNode($node, $newNode)
    {
        if ($node->key < $newNode->key) {
            //新节点大于旧节点; 在右边位置找到一个合适位置插入，如果右边空就直接插入，如果右边不为空，使用右边节点作为根节点递归找到合适位置
            if (empty($node->right)) {
                $node->right = $newNode;
            } else {
                $this->insertNode($node->right, $newNode);
            }
        } else if ($node->key > $newNode->key) {
            //新节点小于旧节点，往左边插入
            if (empty($node->left)) {
                $node->left = $newNode;
            } else {
                $this->insertNode($node->left, $newNode);
            }
        }
    }

    //插入节点
    public function insert($key)
    {
        $newNodes = new Node($key);
        if (empty($this->root)) {
            $this->root = $newNodes;
        } else {
            $this->insertNode($this->root, $newNodes);
        }
    }

    //中序遍历 : 左、根、右
    public function midSort()
    {
        $this->sortArr = [];
        $this->midSortNode($this->root);
    }

    public function midSortNode($node)
    {
        if (!empty($node)) {
            $this->midSortNode($node->left);
            array_push($this->sortArr, $node->key);  //递归遍历后，从里往外打印 ，一次最小到最大值
            $this->midSortNode($node->right);
        }
    }


    //先序遍历 : 根、左、右
    public function preSort()
    {
        $this->sortArr = [];
        $this->preSortNode($this->root);
    }

    public function preSortNode($node)
    {
        if (!empty($node)) {
            $this->sortArr[] = $node->key;

            if (!empty($node->left)) {
                $this->preSortNode($node->left);
            }

            if (!empty($node->right)) {
                $this->preSortNode($node->right);
            }

        }
    }

    //后续遍历：左、右、根
    public function lastSort()
    {
        $this->sortArr = [];
        $this->lastSortNode($this->root);
    }

    public function lastSortNode($node)
    {
        if (!empty($node)) {
            if (!empty($node->left)) {
                $this->lastSortNode($node->left);
            }


            if (!empty($node->right)) {
                $this->lastSortNode($node->right);
            }

            $this->sortArr[] = $node->key;
        }
    }

    //层次遍历 ： 先根、然后层级左右，依次层级往下遍历完
    public function levelSort()
    {
        $this->sortArr = [];
        $this->levelSortNode($this->root);
    }

    //如果使用地柜就需要先获取层级、不适用递归直接顺序遍历即可
    public function levelSortNode($root, $level = 0)
    {
        if (!empty($root)) {
            $node = $root;
            $queue = [];

            array_push($queue,$node);
            $this->sortArr[] = $node->key;
            while (!empty($queue)) {
                $node = array_shift($queue);


                if (!empty($node->left)) {
                    array_push($queue,$node->left);
                    $this->sortArr[] = $node->left->key;
                }

                if (!empty($node->right)) {
                    array_push($queue,$node->right);
                    $this->sortArr[] = $node->right->key;
                }
            }
        }

    }

    //寻找极值
    public function findMin()
    {
        if (!empty($this->root)) {
            $this->findMinNode($this->root);
        }
    }

    public function findMinNode($node)
    {
        if (!empty($node->left)) {
            $this->findMinNode($node->left);
        } else {
            echo "min node key " . $node->key . "\n";
        }
    }

    //寻找最大值
    public function findMax()
    {
        if (!empty($this->root)) {
            $this->findMaxNode($this->root);
        }
    }

    public function findMaxNode($node)
    {
        if (!empty($node->right)) {
            $this->findMaxNode($node->right);
        } else {
            echo "max node key " . $node->key . "\n";
        }
    }

    //查找特殊值
    public function find($val = "")
    {
        if (!empty($val)) {
            $this->findNode($this->root, $val);
        }
    }

    public function findNode($node, $val)
    {
        if ($node->key == $val) {
            echo "finded key " . $node->key . "\n";
            //var_dump($node);
        } else if ($node->key > $val) { //做子树查找
            if (!empty($node->left)) {
                $this->findNode($node->left, $val);
            } else {
                echo "左子树未找到 \n";
            }
        } else if ($node->key < $val) { //右子树查找
            if (!empty($node->right)) {
                $this->findNode($node->right, $val);
            } else {
                echo "右子树未找到\n";
            }
        }
    }


}

function dump($arr)
{
    $res = json_encode($arr);
    echo $res . " \n";
}

$tree  = new BinaryTree();
$nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
foreach ($nodes as $k => $v) {
    $tree->insert($v);
}
dump($tree);
$tree->midSort();
dump($tree->sortArr);

$tree->findMin();
$tree->findMax();

$tree->find(8);

$tree->preSort();
dump($tree->sortArr);

$tree->lastSort();
dump($tree->sortArr);

$tree->levelSort();
dump($tree->sortArr);

//先序遍历 根节点 ---> 左子树 ---> 右子树
//中序遍历，左子树---> 根节点 ---> 右子树
//后序遍历，左子树 ---> 右子树 ---> 根节点

//广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。
//二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。