本文共 3570 字，大约阅读时间需要 11 分钟。

二叉树操作详解

二叉树基础

二叉树是数据存储的一种树形结构，具有父节点和两个子节点的特点。其核心特性是每个节点最多有两个子节点，通常称为左孩子和右孩子。以下是二叉树的核心操作说明：

二叉树创建

二叉树的创建过程如下：

class Node {    public $data; // 结点数据    public $left; // 左孩子    public $right; // 右孩子    public function __construct($data, $left = null, $right = null) {        $this->data = $data;        $this->left = $left;        $this->right = $right;    }}

class Btree {    public $root;    public function init() {        $this->root = new Node(null);        return $this->root;    }}

二叉树操作

左右插入操作

public function leftInsert($cur, $data) {    if (!$cur) {        return false;    }    $node = new Node($data, $cur->left);    $cur->left = $node;    return $node;}public function rightInsert($cur, $data) {    if (!$cur) {        return false;    }    $node = new Node($data, null, $cur->right);    $cur->right = $node;    return $node;}

遍历操作

public function preView($root, &$res = []) {    if (!$root) {        return false;    }    $res[] = $root->data;    $this->preView($root->left, $res);    $this->preView($root->right, $res);    return $res;}

2. **前序遍历（堆栈实现）**：   ```php   public function pre2($root) {       if (!$root) {           return false;       }       $stack = [];       $res = [];       $stack[] = $root;       while ($stack) {           $cur = array_pop($stack);           $res[] = $cur->data;           if ($cur->right) {               $stack[] = $cur->right;           }           if ($cur->left) {               $stack[] = $cur->left;           }       }       return $res;   }

3. 中序遍历：

   public function midView($root, &$res = []) {    if (!$root) {        return false;    }    $this->midView($root->left, $res);    $res[] = $root->data;    $this->midView($root->right, $res);    return $res;}

4. **后序遍历**：   ```php   public function aftView($root, &$res = []) {       if (!$root) {           return false;       }       $this->aftView($root->left, $res);       $this->aftView($root->right, $res);       $res[] = $root->data;       return $res;   }

5. 层序遍历（队列实现）：

   public function floorView($root) {    if (!$root) {        return false;    }    $queue = [];    $queue[] = $root;    $res = [];    while ($queue) {        $cur = array_shift($queue);        $res[] = $cur->data;        if ($cur->left) {            $queue[] = $cur->left;        }        if ($cur->right) {            $queue[] = $cur->right;        }    }    return $res;}

##### 核心查找与删除操作1. **查找操作**：   ```php   public function find($cur, $data) {       if (!$cur) {           return false;       }       if ($cur->data == $data) {           return true;       }       if ($cur->left && $this->find($cur->left, $data)) {           return true;       }       if ($cur->right && $this->find($cur->right, $data)) {           return true;       }       return false;   }

2. 删除操作：

   public function del($cur) {    if (!$cur) {        return false;    }    if ($cur->left) {        $this->del($cur->left);    }    if ($cur->right) {        $this->del($cur->right);    }    unset($cur);    return true;}

二叉树示例

以下是基于上述二叉树操作创建一个简单树状结构：

$btree = new Btree();$root = $btree->init();$cur = $btree->leftInsert($root, 'A');$cur = $btree->leftInsert($cur, 'B');$cur = $btree->leftInsert($cur, 'D');$btree->rightInsert($cur, 'G');$cur = $btree->rightInsert($root->left, 'C');$btree->rightInsert($cur, 'F');$btree->leftInsert($cur, 'E');

样例输出

• 前序遍历（递归）：ABDGCEF
• 前序遍历（堆栈）：ABDGCEF
• 中序遍历：GDBAECF
• 后序遍历：GDBEFCA
• 层序遍历：ABCDEFG
• 打印结果：

  ---------------F----------C---------------E----A----------B--------------------G---------------D

二叉树查找

$find = $btree->find($root->left, 'E');var_dump($find); // true