php 二叉樹遍歷

二叉樹是邏輯結構，二叉鏈表是二叉樹的物理實作，是它的一種存盤結構，兩者之間的關系屬于概念和實作，抽象和具體的關系，

• 前序遍歷：根節點->左子樹->右子樹
• 中序遍歷：左子樹->根節點->右子樹
• 后序遍歷：左子樹->右子樹->根節點

深度優先遍歷：

    前序遍歷：10 8 7 9 12 11 13
    中序遍歷：7 8 9 10 11 12 13
    后序遍歷：7 9 8 11 13 12 10

廣度優先遍歷：

    層次遍歷：10 8 12 7 9 11 13

二叉樹的深度優先遍歷的非遞回的通用做法是采用堆疊，廣度優先遍歷的非遞回的通用做法是采用佇列，

<?php
/********************************************************
 * 我寫的PHP都是從C語言的資料結構中演化而來************************
 **************************************************************
 * /**
 *    ******二叉樹圖****
 *      A                    *
 *     * *                   *
 *    *   *                  *
 *   B     C                *
 *        *                   *
 *       *                    *
 *      D                    *
 *       *                    *
 *         *E                *
 ******************
 * PHP- 鏈式二叉樹的遍歷---先序遍歷（根,左,右）-中序遍歷(左,根,右)-后序遍歷(左,右，根)
 * 先 A B C D E
 * 中 B A D E C
 * 后 B E D C A
 * @time
 * @Author
 ****/
Class  BTreeNode
{
    public $data; //資料域
    public $LeftHand = NULL; //左指標
    public $RightHand = NULL; //右指標

    public function __construct ($data)
    {
        if (!empty($data)) {
            $this->data = https://www.cnblogs.com/yangzailu/p/$data;
        }
    }

    //先序遍歷（根，左，右）遞回實作
    public function PreTraverseBTree ($BTree)
    {
        if (NULL !== $BTree) {
            var_dump($BTree->data);//根
            if (NULL !== $BTree->LeftHand) {
                $this->PreTraverseBTree($BTree->LeftHand); //遞回遍歷左樹
            }
            if (NULL !== $BTree->RightHand) {
                $this->PreTraverseBTree($BTree->RightHand); //遞回遍歷右樹
            }
        }
    }

    //中序遍歷(左，根，右)遞回實作
    public function InTraverseBTree ($BTree)
    {
        if (NULL !== $BTree) {
            if (NULL !== $BTree->LeftHand) {
                $this->InTraverseBTree($BTree->LeftHand); //遞回遍歷左樹
            }
            var_dump($BTree->data); //根
            if (NULL !== $BTree->RightHand) {
                $this->InTraverseBTree($BTree->RightHand); //遞回遍歷右樹
            }
        }
    }

    //后序遍歷(左，右，根)遞回實作
    public function FexTraverseBTree ($BTree)
    {
        if (NULL !== $BTree) {
            if (NULL !== $BTree->LeftHand) {
                $this->FexTraverseBTree($BTree->LeftHand); //遞回遍歷左樹
            }
            if (NULL !== $BTree->RightHand) {
                $this->FexTraverseBTree($BTree->RightHand); //遞回遍歷右樹
            }
            var_dump($BTree->data); //根
        }
    }
}

header("Content-Type:text/html;charset=utf-8");
echo '先的記憶體為' . var_dump(memory_get_usage());
echo '<hr/>';
//創建五個節點
$A = new  BTreeNode('A');
$B = new  BTreeNode('B');
$C = new  BTreeNode('C');
$D = new  BTreeNode('D');
$E = new  BTreeNode('E');
//連接形成一個二叉樹
$A->LeftHand = $B;
$A->RightHand = $C;
$C->LeftHand = $D;
$D->RightHand = $E;

//先序遍歷
echo '先序遍歷的結果' . '<br>';
$A->PreTraverseBTree($A);
echo '<br/>中序遍歷的結果' . '<br>';
$A->InTraverseBTree($A);
echo '<br/>后序列遍歷的結果' . '<br/>';
$A->FexTraverseBTree($A);
echo '<hr/>';
echo '后的記憶體為' . var_dump(memory_get_usage());

標籤：PHP

上一篇：java 面向物件編程

下一篇：PHP中命名空間是怎樣的存在？（三）