:数据结构之二叉树

✏一.二叉树的定义

既然都叫二叉树了，那么二叉树的特点是每个至多只有两棵子树。换句话来说，每个结点的度不超过两个，并且二叉树的子树还存在左右之分，它的次序不能任意颠倒。

✏二叉树的表现形态

1.满二叉树:棵深度为k有且有2^k-1结点的树称之为满二叉树，比如图中的a(深度为4,拥有15个结点)。这里我们就可以得到二叉树的一个特性:在二叉树的第i层中至多有2^i-1个结点(i>=1)。当然了他不止这一个特性。。。

2.完全二叉树:深度为k,有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n一一对应时，才是完全二叉树。这里图c不是完全二叉树，假设根节点A是1，那么图c在n等于12这个点上就没有对应。所以不是完全二叉树。所以完全二叉树的特点:(1)叶子结点只可能在层次最大的两层上出现。(2)对任意一个结点，若其右子树的最大层次是l，那么其左子树的最大层数必须是l或者l+1。

三·二叉树的存储树这种结构的存储不像线性结构那样简单，并不能直接用前后关系来描述。一个树有有很多的子树，一个结点不止一个后继。下面用图来说明用数组存储和链表存储。

✏三.二叉树的存储

按照顺序存储的结构。用一组连续的存储单元至上而下，至左到右存储，图中的0表示不存在该结点，每一个不存在的点我们都需要浪费一个空间。所以在最坏的情况下，一个深度为k且只有k个结点的单支树(树中不存在度为2的结点)却需要长度为2^k-1的一维数组。所以这种顺序存储适合完全二叉树。

链式存储的结构是由一个数据元素和分别指向其左右子树的两个分支构成。包含了三个域：数据域,左右指针域。链表的头指向树的根节点。

✏四·二叉树的前中后序遍历

//二叉树
class Tree{
    public $res='';
    public $left=null;
    public $right=null;
    public function __construct($res)
{
        $this->res=$res;
    }

}
//前序遍历
 function front($tree){
    if($tree==null){
        return ;
    }
    echo $tree->res.'
';
    front($tree->left);
    front($tree->right);
}

//中序遍历
 function middle($tree)
{
    if($tree==null){
        return ;
    }
    middle($tree->left);
    echo $tree->res.'
';
    middle($tree->right);
 }

//后序遍历
 function backend($tree)
{
    if($tree==null){
        return ;
    }
    backend($tree->right);
    backend($tree->left);
    echo $tree->res.'
';
}

$treeA=new Tree('a');
$treeB=new Tree('b');
$treeC=new Tree('c');
$treeA->left=$treeB;
$treeA->right=$treeC;
//
//front($treeA);
//echo "-------------------".'
';
//middle($treeA);
//echo "-------------------".'
';
//backend($treeA);

✏五.二叉排序树的插入,查找,删除.

我主要说明一下删除操作，删除操作主要分三种情况:(1)如果待删除结点中，只有一个左子结点，那么只要把待删除结点的父结点的left指向待删除结点的左子结点。(2)如果待删除结点只有一个右子结点，那么只要把带删除结点的父结点的right指向带删除结点的右子结点。(3)如果待删除结点有左右结点，那么需要找到这个结点右子树中最小的结点，把他替换到待删除的结点上面。

class Tree{
    public $res='';
    public $left=null;
    public $right=null;
    public function __construct($res)
{
        $this->res=$res;
    }

}

class BinarySortTree
{
    public $tree;

    public function getTree()
{
        return $this->tree;
    }

    //插入
    public function insertTree($data)
    {
        if(!$this->tree){
            $this->tree=new Tree($data);
            return ;
        }
        $p=$this->tree;
        while($p){
            if($data<$p->res){  //如果插入结点当前结点
                if(!$p->left){  //并且不存在左子结点
                   $p->left=new Tree($data);
                   return ;
                }
                $p=$p->left;
            }elseif ($data>$p->res){
                if(!$p->right){
                    $p->right=new Tree($data);
                    return ;
                }
                $p=$p->right;
            }else{
                return ;
            }
        }
    }

   

    //删除
    public function deleteTree($data)
{
        if (!$this->tree) {
            return;
        }
        $p = $this->tree;
        $fatherP = null;
        while ($p && $p->res !== $data) {
            $fatherP=$p; //结点的父结点
            if ($data > $p->res) {
                $p = $p->right;
            }else{
                $p=$p->left;
            }
        }

        //如果二叉树不存在
        if($p==null){
            var_dump('当前树中没有此结点');return;
        }

        //待删除待有两个子结点
        if($p->left && $p->right){
            $minR=$p->right;
            $minRR=$p;// 最小结点的父结点
            //查找右子树的最小结点
            while($minR->left){
                $minRR=$minR;
                $minR=$minR->left;
            }
            $p->res=$minR->res;//把右子树上最小结点的值赋值给待删除结点
            $p=$minR;
            $fatherP=$minRR;

        }
        $child=null;
        if($p->left){
            $child=$p->left;
        }elseif($p->right){
            $child=$p->right;
        }else{
            $child=null;
        }

        if(!$fatherP){ //待删除结点是根结点
            $this->tree=$child;
        }elseif ($fatherP->left==$p){ //待删除结点只有一个左结点，把待删除结点的父结点的left指向待删除结点的子节点
            $fatherP->left=$child;
        }else{                        //待删除结点只有一个右结点，把待删除结点的父结点的right指向待删除结点的子节点
            $fatherP->right=$child;
        }

    }
}

$sortTree=new BinarySortTree();
$sortTree->insertTree(9);
$sortTree->insertTree(8);
$sortTree->insertTree(10);
$sortTree->insertTree(5);
$sortTree->insertTree(6);
$sortTree->insertTree(4);
//$sortTree->search(1);
//$sortTree->deleteTree(8);
//var_dump($sortTree->getTree());

转载链接：https://leetcode.cn/