专栏首页琯琯博客PHP二叉树(二):二叉搜索树

PHP二叉树(二):二叉搜索树

二叉搜索树

<?php
/**
 * description: 二叉查找树
 */
//结点
class Node
{
    public $key;
    public $parent;
    public $left;
    public $right;

    public function __construct($key)
    {
        $this--->key = $key;
        $this->parent = NULL;
        $this->left = NULL;
        $this->right = NULL;
    }
}

//二叉搜索树
class Bst
{
    public $root;

    /**
     * 初始化树结构
     * @param $arr 初始化树结构的数组
     * @return null
     */
    public function init($arr)
    {
        $this->root = new Node($arr[0]);
        for ($i = 1; $i < count($arr); $i++) {
            $this->Insert($arr[$i]);
        }
    }

    /**
     * (对内)中序遍历
     * @param $root (树或子树的)根节点
     * @return null
     */
    private function mid_order($root)
    {
        if ($root != NULL) {
            $this->mid_order($root->left);
            echo $root->key . " ";
            $this->mid_order($root->right);
        }
    }

    /**
     * (对外)中序遍历
     * @param null
     * @return null
     */
    public function MidOrder()
    {
        $this->mid_order($this->root);
    }

    /**
     * 查找树中是否存在$key对应的节点
     * @param $key 待搜索数字
     * @return $key对应的节点
     */
    function search($key)
    {
        $current = $this->root;
        while ($current != NULL) {
            if ($current->key == $key) {
                return $current;
            } elseif ($current->key > $key) {
                $current = $current->left;
            } else {
                $current = $current->right;
            }
        }
        return $current;
    }

    /**
     * 查找树中的最小关键字
     * @param $root 根节点
     * @return 最小关键字对应的节点
     */
    function search_min($root)
    {
        $current = $root;
        while ($current->left != NULL) {
            $current = $current->left;
        }
        return $current;
    }

    /**
     * 查找树中的最大关键字
     * @param $root 根节点
     * @return 最大关键字对应的节点
     */
    function search_max($root)
    {
        $current = $root;
        while ($current->right != NULL) {
            $current = $current->right;
        }
        return $current;
    }


    /**
     * 查找某个$key在中序遍历时的直接前驱节点
     * @param $x 待查找前驱节点的节点引用
     * @return 前驱节点引用
     */
    function predecessor($x)
    {
        //左子节点存在,直接返回左子节点的最右子节点
        if ($x->left != NULL) {
            return $this->search_max($x->left);
        }
        //否则查找其父节点,直到当前结点位于父节点的右边
        $p = $x->parent;
        //如果x是p的左孩子,说明p是x的后继,我们需要找的是p是x的前驱
        while ($p != NULL && $x == $p->left) {
            $x = $p;
            $p = $p->parent;
        }
        return $p;
    }

    /**
     * 查找某个$key在中序遍历时的直接后继节点
     * @param $x 待查找后继节点的节点引用
     * @return 后继节点引用
     */
    function successor($x)
    {
        if ($x->left != NULL) {
            return $this->search_min($x->right);
        }
        $p = $x->parent;
        while ($p != NULL && $x == $p->right) {
            $x = $p;
            $p = $p->parent;
        }
        return $p;
    }

    /**
     * 将$key插入树中
     * @param $key 待插入树的数字
     * @return null
     */
    function Insert($key)
    {
        if (!is_null($this->search($key))) {
            throw new Exception('结点' . $key . '已存在,不可插入!');
        }
        $root = $this->root;
        $inode = new Node($key);
        $current = $root;
        $prenode = NULL;
        //为$inode找到合适的插入位置
        while ($current != NULL) {
            $prenode = $current;
            if ($current->key > $inode->key) {
                $current = $current->left;
            } else {
                $current = $current->right;
            }
        }

        $inode->parent = $prenode;
        //如果$prenode == NULL, 则证明树是空树
        if ($prenode == NULL) {
            $this->root = $inode;
        } else {
            if ($inode->key < $prenode->key) {
                $prenode->left = $inode;
            } else {
                $prenode->right = $inode;
            }
        }
        //return $root;
    }

    /**
     * 在树中删除$key对应的节点
     * @param $key 待删除节点的数字
     * @return null
     */
    function Delete($key)
    {
        if (is_null($this->search($key))) {
            throw new Exception('结点' . $key . "不存在,删除失败!");
        }
        $root = $this->root;
        $dnode = $this->search($key);
        if ($dnode->left == NULL || $dnode->right == NULL) { #如果待删除结点无子节点或只有一个子节点,则c = dnode
            $c = $dnode;
        } else { #如果待删除结点有两个子节点,c置为dnode的直接后继,以待最后将待删除结点的值换为其后继的值
            $c = $this->successor($dnode);
        }

        //无论前面情况如何,到最后c只剩下一边子结点
        if ($c->left != NULL) {
            $s = $c->left;
        } else {
            $s = $c->right;
        }

        if ($s != NULL) {
        #将c的子节点的父母结点置为c的父母结点,此处c只可能有1个子节点,因为如果c有两个子节点,则c不可能是dnode的直接后继
            $s->parent = $c->parent;
        }
        if ($c->parent == NULL) {
        #如果c的父母为空,说明c=dnode是根节点,删除根节点后直接将根节点置为根节点的子节点,
        此处dnode是根节点,且拥有两个子节点,则c是dnode的后继结点,c的父母就不会为空,就不会进入这个if
            $this->root = $s;
        } else if ($c == $c->parent->left) {
        #如果c是其父节点的左右子节点,则将c父母的左右子节点置为c的左右子节点
            $c->parent->left = $s;
        } else {
            $c->parent->right = $s;
        }

        #如果c!=dnode,说明c是dnode的后继结点,交换c和dnode的key值
        if ($c != $dnode) {
            $dnode->key = $c->key;
        }

        #返回根节点
        // return $root;
    }

    /**
     * (对内)获取树的深度
     * @param $root 根节点
     * @return 树的深度
     */
    private function getdepth($root)
    {
        if ($root == NULL) {
            return 0;
        }

        $dl = $this->getdepth($root->left);
        $dr = $this->getdepth($root->right);

        return ($dl > $dr ? $dl : $dr) + 1;
    }

    /**
     * (对外)获取树的深度
     * @param null
     * @return null
     */
    public function Depth()
    {
        return $this->getdepth($this->root);
    }
}

(完)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [第33期] 树,二叉树, 二叉搜索树

    比如想想访问中间某个结点的时候,或者倒数第几个结点 就只能从头往后一个一个查, 效率不高。

    皮小蛋
  • 纸上谈兵: 树, 二叉树, 二叉搜索树

    树的特征和定义 树(Tree)是元素的集合。我们先以比较直观的方式介绍树。下面的数据结构是一个树: ? 树有多个节点(node),用以储存元素。某些节点之间存在...

    Vamei
  • 二叉搜索树

    用户1733462
  • 二叉搜索树

    一、操作: 判断元素是否存在:递归的在左右子树中查找 查找最小元素:在左子树中递归或者循环 查找最大元素:在右子树中递归或循环 插入:递归的插入,大于则插入在节...

    lwen
  • 二叉搜索树

    二叉搜索树(Binary Search Tree)的定义: 它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它...

    指点
  • 二叉搜索树

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.ne...

    zy010101
  • 普通二叉树转换成搜索二叉树

    struct ListNode { int data; ListNode *lchild,*rchild; }; void CreateBST...

    用户1624346
  • 判断二叉树是否为二叉搜索树

    这题利用二叉搜索树的特性:左子树的所有的关键字小于根节点的关键字,右子树的所有关键字都大于根结点 的关键字。二叉搜索树的中序遍历一定是个有序序列。根据这一特性可...

    AI那点小事
  • BinarySearchTree二叉搜索树

    二叉树具有唯一的根节点 二叉树每个节点最多有两个孩子 二叉树每个节点最多有一个父亲节点,根节点是唯一没有父亲节点的。 二叉树具有天然递归结构。 每个节点...

    羊羽shine
  • 【算法】搜索二叉树,完全二叉树,平衡二叉树的判断

    它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

    MapleYe
  • Algorithms_二叉树&二分搜索树初探

    按照上图, 16就是 28根节点的左孩子, 30 就是28的右孩子 。 依次类推 13是16的左孩子, 22是16的右孩子。 29是30的左孩子, 42是3...

    小小工匠
  • 验证二叉搜索树

    大忽悠爱学习
  • 验证二叉搜索树

    最开始看到这道题的时候,以为是直接判断 node.right.val > node.val 和 node.left.val < node.val 对每个结点是否...

    木子星兮
  • 二叉搜索树登场!

    到了二叉搜索树,开始要换一个思路了,如果没有利用好二叉搜索树的特性,就容易把简单题做成了难题了。

    代码随想录
  • 数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)

    前言:前面了解了树的概念和基本的存储结构类型及树的分类,而在树中应用最广泛的种类是二叉树

  • PHP二叉树(一):平衡二叉树(AVL)

    平衡二叉树 <?php /** * description: 平衡二叉树 */ //结点 class Node { public $key; ...

    guanguans
  • 判断一棵满二叉树是否为二叉搜索树

    给定一棵满二叉树,判定该树是否为二叉搜索树,是的话打印 True,不是的话打印 False。

    echobingo
  • 2021-04-12:判断二叉树是否是搜索二叉树?

    福大大架构师每日一题
  • 二叉树:搜索树转成累加树

    今天应该是一个程序猿普天同庆的日子,所以今天的题目比较简单,只要认真把前面每天的文章都看了,今天的题目就是分分钟的事了,毕竟程序猿何苦为难程序猿呢,大家都愉快过...

    代码随想录

扫码关注云+社区

领取腾讯云代金券