php二叉樹怎樣遍歷節點

在 PHP 中，可以使用遞歸或迭代方法來遍歷二叉樹節點。這里，我們將介紹兩種方法：前序遍歷、中序遍歷和后序遍歷。

首先，定義一個簡單的二叉樹節點類：

class TreeNode {
    public $value;
    public $left;
    public $right;

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

遞歸遍歷

1. 前序遍歷（根->左->右）

function preOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    echo $node->value . " ";
    preOrderTraversal($node->left);
    preOrderTraversal($node->right);
}

2. 中序遍歷（左->根->右）

function inOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    inOrderTraversal($node->left);
    echo $node->value . " ";
    inOrderTraversal($node->right);
}

3. 后序遍歷（左->右->根）

function postOrderTraversal($node) {
    if ($node === null) {
        return;
    }

    postOrderTraversal($node->left);
    postOrderTraversal($node->right);
    echo $node->value . " ";
}

迭代遍歷

1. 前序遍歷（根->左->右）

function preOrderTraversalIterative($node) {
    if ($node === null) {
        return;
    }

    $stack = [$node];

    while ($stack) {
        $current = $stack[count($stack) - 1];
        $stack = array_slice($stack, 0, -1);
        echo $current->value . " ";

        if ($current->right !== null) {
            $stack[] = $current->right;
        }
        if ($current->left !== null) {
            $stack[] = $current->left;
        }
    }
}

2. 中序遍歷（左->根->右）

function inOrderTraversalIterative($node) {
    if ($node === null) {
        return;
    }

    $stack = [];
    $current = $node;

    while ($current !== null || count($stack) > 0) {
        while ($current !== null) {
            $stack[] = $current;
            $current = $current->left;
        }

        $current = array_pop($stack);
        echo $current->value . " ";
        $current = $current->right;
    }
}

3. 后序遍歷（左->右->根）

function postOrderTraversalIterative($node) {
    if ($node === null) {
        return;
    }

    $stack = [];
    $lastVisitedNode = null;

    $current = $node;
    while ($current !== null || count($stack) > 0) {
        if ($current !== null) {
            $stack[] = $current;
            $current = $current->left;
        } else {
            $topNode = array_pop($stack);
            if ($topNode->right !== null && $lastVisitedNode !== $topNode->right) {
                $current = $topNode->right;
            } else {
                echo $topNode->value . " ";
                $lastVisitedNode = $topNode;
            }
        }
    }
}

使用這些遍歷函數，可以方便地遍歷二叉樹的節點。