二叉树
<?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);
//先序遍历 根节点 ---> 左子树 ---> 右子树
//中序遍历,左子树---> 根节点 ---> 右子树
//后序遍历,左子树 ---> 右子树 ---> 根节点
//广度优先遍历:又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。
//二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。