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

二叉树操作详解

二叉树基础

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

二叉树创建

二叉树的创建过程如下：

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

转载地址：http://ektfk.baihongyu.com/