php实现二叉树

二叉树是数据结构中不可忽略的部分，但是相关的书籍上很少有用php来实现二叉树的，下面是我用php参考C++实现二叉树的代码

一、二叉树的数组实现方式

<?php
/**
 * 二叉树数组表示
 */
class BinaryTree {
    private $size, $array = array();
    //创建树并初始化节点
    function __construct($size, $root) {
        $this->size = $size;
        for ($i = 0; $i < $size; $i++) {
              $this->array[$i] = 0;
        }
        $this->array[0] = $root;
    }
    //查询节点
    function searchNode($nodeCode) {
        if ($nodeCode >= $this->size || $nodeCode < 0) {
            return false;
        } else {
            if ($this->array[$nodeCode] == 0) {
                return null;
            } else {
                return $this->array[$nodeCode];
            }
        }
    }
    //增加树节点
    function addNode($nodeCode, $place, $nodeValue) {
        if ($nodeCode >= $this->size || $nodeCode < 0) {
            return false;
        } else {
            //判断插入节点是左孩子还是右孩子
            if ($place == 0) {
                //判断该位置是否为空，为空进行插入操作
                if ($this->array[$nodeCode * 2 + 1] == 0) {
                    //判断该节点是否是新的叶子节点，如果是，则对相应位置进行补0操作
                    if ($nodeCode * 2 + 1 >= $this->size) {
                        for ($i = $this->size; $i < $nodeCode * 2 + 1; $i++) {
                              $this->array[$i] = 0;
                        }
                        $this->size = $nodeCode * 2 + 2;
                        $this->array[$nodeCode * 2 + 1] = $nodeValue;
                    } else {
                        $this->array[$nodeCode * 2 + 1] = $nodeValue;
                    }
                } else {
                    return false;
                }
            } elseif ($place == 1) {
                if ($this->array[$nodeCode * 2 + 2] == 0) {
                    //判断该节点是否是新的叶子节点，如果是，则对相应位置进行补0操作
                    if ($nodeCode * 2 + 2 >= $this->size) {
                        for ($i = $this->size; $i < $nodeCode * 2 + 1; $i++) {
                              $this->array[$i] = 0;
                        }
                        $this->size = $nodeCode * 2 + 3;
                        $this->array[$nodeCode * 2 + 2] = $nodeValue;
                    } else {
                        $this->array[$nodeCode * 2 + 2] = $nodeValue;
                    }
                } else {
                    return false;
                }
            }
        }
    }
    //删除树节点
    function deleteNode($nodeCode) {
        if ($nodeCode >= $this->size || $nodeCode < 0) {
            return false;
        } else {
            $this->array[$nodeCode] = 0;
        }
    }
    //遍历树
    function showTree() {
        var_dump($this->array);
    }
    //销毁树
    function __destruct() {
        unset($this->array);
    }
}

这种实现方式主要是将二叉树中的节点存储在数组中，通过数组下标索引进而对二叉树的相关节点进行操作

二、二叉树的链表实现方式

<?php
error_reporting(E_ALL ^ E_NOTICE);
/**
 * 二叉树的节点类
 */
class Node {
    //索引 值 左孩子 右孩子 父节点
    public $index, $data, $lChild, $rChild, $parentNode;
    function __construct($index, $data, Node $parentNode = null, Node $lChild = null, Node $rChild = null) {
        //构造函数 用来初始化节点
        $this->index = $index;
        $this->data = $data;
        $this->lChild = $lChild;
        $this->rChild = $rChild;
        $this->parentNode = $partentNode;
    }
    function SearchNode($nodeIndex) {
        //节点的搜索方法
        if ($this->index == $nodeIndex) {
            return $this;
        }
        if ($this->lChild != null) {
            if ($this->lChild->index == $nodeIndex) {
                return $this->lChild;
            } else {
                $tempNode = $this->lChild->SearchNode($nodeIndex);
                if ($tempNode != null) {
                    return $tempNode;
                }
            }
        }
        if ($this->rChild != null) {
            if ($this->rChild->index == $nodeIndex) {
                return $this->rChild;
            } else {
                $tempNode = $this->rChild->SearchNode($nodeIndex);
                if ($tempNode != null) {
                    return $tempNode;
                }
            }
        }
        return null;
    }
    function DeleatNode() {
        //节点的删除
        if ($this->lChild != null) {
            $this->lChild->DeleatNode();
        }
        if ($this->rChild != null) {
            $this->rChild->DeleatNode();
        }
        if ($this->parentNode != null) {
            if ($this->parentNode->lChild == $this) {
                $this->parentNode->lChild = null;
            } elseif ($this->parentNode->rChild == $this) {
                $this->partentNode->rChild = null;
            }
        }
        unset($this);
    }
    function PreOrderTraversal() {
        //节点的前序遍历
        echo $this->data;
        if ($this->lChild != null) {
            $this->lChild->PreOrderTraversal();
        }
        if ($this->rChild != null) {
            $this->rChild->PreOrderTraversal();
        }
    }
    function InOrderTraversal() {
        //节点的中序遍历
        if ($this->lChild != null) {
            $this->lChild->InOrderTraversal();
        }
        echo $this->data;
        if ($this->rChild != null) {
            $this->rChild->InOrderTraversal();
        }
    }
    function PostOrderTraversal() {
        //节点的后序遍历
        if ($this->lChild != null) {
            $this->lChild->PostOrderTraversal();
        }
        if ($this->rChild != null) {
            $this->rChild->PostOrderTraversal();
        }
        echo $this->data;
    }
}
class Tree {
    private $root;
    //构造树并初始化根节点
    function __construct($index, $data) {
        $this->root = new Node($index, $data);
    }
    //搜索节点
    function SearchNode($nodeIndex) {
        return $this->root->SearchNode($nodeIndex);
    }
    //增加节点
    function AddNode($nodeIndex, $direction, Node $node) {
        $searchResult = $this->root->SearchNode($nodeIndex);
        if ($searchResult != null) {
            if ($direction == 0) {
                $searchResult->lChild = $node;
                $searchResult->lChild->parentNode = $searchResult;
                 
            } elseif ($direction == 1) {
                $searchResult->rChild = $node;
                $searchResult->rChild->parentNode = $searchResult;
                 
            }
        } else {
            return false;
        }
    }
    //删除节点
    function DeleatNode($nodeIndex) {
        if ($this->SearchNode($nodeIndex) != null) {
            $this->SearchNode($nodeIndex)->DeleatNode();
        }
    }
    //前序遍历
    function PreOrderTraversal() {
        $this->root->PreOrderTraversal();
    }
    //中序遍历
    function InOrderTraversal() {
        $this->root->InOrderTraversal();
    }
    //后序遍历
    function PostOrderTraversal() {
        $this->root->PostOrderTraversal();
    }
    //析构函数
    function __destruct() {
        unset($this);
    }
}

这种实现方式相对于以数组方式实现二叉树来说稍微复杂一点，首先，创建一个节点类，节点类属性有索引(index)、数据(data)、左孩子、右孩子、父节点，再创建一个二叉树类，有些在二叉树类中相对难以实现的方法我们可以放到节点类中去实现。