php数据结构运用（树）

树

在这里插入图片描述

树是一种数据结构，它是由n个有限节点组成一个具有层次关系的集合
树的特点：
- 每个节点有零个或多个子节点
- 没有父节点的节点称为根节点
- 每一个非根节点有且只有一个父节点
- 除了根节点外，每个子节点可以分为多个不相交的子树

二叉树

概念

在这里插入图片描述

二叉树是树的特殊一种，具有如下特点：
- 每个结点最多有两颗子树，结点的度最大为2
- 左子树和右子树是有顺序的，次序不能颠倒
- 即使某结点只有一个子树，也要区分左右子树
二叉树是一种有用的折中方案，既有链表的好处，也有数组的好处
添加，删除元素都很快，并且在查找方面也有很多的算法优化

代码示例：

php">    class TreeNode{
        public $value = null;
        
        public $right = null;
        
        public $left = null;
        
        function __construct($value) {
            $this->value = $value;
        }
    }

二叉树遍历算法：

前置遍历（根——>左——>右）

php">function preTraverse(TreeNode $node) {
    if(!$node) {
        return;
    }
    $this->visit($node->value);
    $this->preTraverse($node->left);
    $this->preTraverse($node->right);
}

中区遍历（左——>根——>右）

php">function midTraverse(TreeNode $node) {
    if(!$node) {
        return;
    }
    $this->midTraverse($node->left);
    $this->visit($node->value);
    $this->midTraverse($node->right);
}

后置遍历（左——>右——>根）

php">function sufTraverse(TreeNode $node) {
    if(!$node) {
        return;
    }
    $this->sufTraverse($node->left);
    $this->sufTraverse($node->right);
    $this->visit($node->value);
}

层次遍历

php">function levelTraverse(TreeNode $node) {
    $queue = [$node];
    while (!empty($queue)) {
        $temp = array_pop($queue);
        $this->visit($temp);
        if($temp->left) {
            array_push($queue, $temp->left);
        }
        if($temp->right) {
            array_push($queue, $temp->right);
        }
    }
}

满二叉树

高度为h，由2^h-1个节点构成的二叉树称为满二叉树
在这里插入图片描述

完全二叉树

完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。注：左右两边没有大小关系。

堆一般都是用完全二叉树来实现的

完全<a class= 二叉树" />

二叉查找树

没有键值相等的节点
若左子树不为空，左子树上节点值均小于根节点的值
若右子树不为空，右子树上节点值均大于根节点的值

二叉查找树查找算法

步骤：

1、若根结点的关键字值等于查找的关键字，成功。
2、否则，若小于根结点的关键字值，递归查左子树。
3、若大于根结点的关键字值，递归查右子树。
4、若子树为空，查找不成功。

php">    public function find(int $data) {
        $p = $this->tree;
        while ($p) {
             if ($data < $p->data) {
                 $p = $p->left;
             } elseif ($data > $p->data) {
                 $p = $p->right;
             } else {
                 return $p;
            }
        }
        return null;
    }

二叉查找树插入算法

步骤：

1、首先执行查找算法，找出被插结点的父亲结点。
2、判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
3、若二叉树为空。则首先单独生成根结点。

php">    public function insert(int $data) {
        if (!$this->tree) {
            $this->tree = new TreeNode($data);
            return true;
        }
        $p = $this->tree;
        while ($p) {
            if ($data < $p->data) {
                if(!$p->left){
                    $p->left = new TreeNode($data);
                    return true;
                }
                $p = $p->left;
            } elseif ($data > $p->data) {
                if(!$p->right){
                    $p->right = new TreeNode($data);
                    return true;
                }
                $p = $p->right;
            } else {
                return false;
            }
        }
    }