题目描述补充

题目： 编写一个算法，用于实现一个完全二叉树的构建、遍历以及层级遍历（或称为广度优先遍历）。完全二叉树是一种特殊的二叉树，其中除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地向左对齐。

要求：

1. 构建完全二叉树：给定一个有序数组（通常是升序或降序），根据数组的值构建一棵完全二叉树。
2. 遍历完全二叉树：
   • 实现前序遍历（根节点 -> 左子树 -> 右子树）。
   • 实现中序遍历（左子树 -> 根节点 -> 右子树，但在此上下文中可能不常用，因为完全二叉树不保证有序性）。
   • 实现后序遍历（左子树 -> 右子树 -> 根节点）。
3. 层级遍历：从根节点开始，按从上到下、从左到右的顺序访问所有节点。

示例代码

PHP 示例

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

    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function buildCompleteBinaryTree($arr) {
    if (empty($arr)) return null;
    return buildTreeHelper($arr, 0);
}

function buildTreeHelper($arr, $index) {
    if ($index >= count($arr)) return null;
    $node = new TreeNode($arr[$index]);
    $node->left = buildTreeHelper($arr, 2 * $index + 1);
    $node->right = buildTreeHelper($arr, 2 * $index + 2);
    return $node;
}

function levelOrderTraversal($root) {
    if ($root === null) return [];
    $queue = new SplQueue();
    $queue->enqueue($root);
    $result = [];
    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();
        $result[] = $node->val;
        if ($node->left) $queue->enqueue($node->left);
        if ($node->right) $queue->enqueue($node->right);
    }
    return $result;
}

// 使用示例
$arr = [1, 2, 3, 4, 5, 6];
$root = buildCompleteBinaryTree($arr);
$levelOrder = levelOrderTraversal($root);
print_r($levelOrder);

Python 示例

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildCompleteBinaryTree(arr):
    def build(index):
        if index >= len(arr):
            return None
        node = TreeNode(arr[index])
        node.left = build(2 * index + 1)
        node.right = build(2 * index + 2)
        return node
    return build(0)

def levelOrderTraversal(root):
    if not root:
        return []
    queue, result = [root], []
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

# 使用示例
arr = [1, 2, 3, 4, 5, 6]
root = buildCompleteBinaryTree(arr)
level_order = levelOrderTraversal(root)
print(level_order)

JavaScript 示例

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function buildCompleteBinaryTree(arr) {
    function build(index) {
        if (index >= arr.length) return null;
        const node = new TreeNode(arr[index]);
        node.left = build(2 * index + 1);
        node.right = build(2 * index + 2);
        return node;
    }
    return build(0);
}

function levelOrderTraversal(root) {
    if (!root) return [];
    const queue = [root];
    const result = [];
    while (queue.length > 0) {
        const node = queue.shift();
        result.push(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return result;
}

// 使用示例
const arr = [1, 2, 3, 4, 5, 6];
const root = buildCompleteBinaryTree(arr);
const levelOrder = levelOrderTraversal(root);
console.log(levelOrder);

码小课网站中有更多相关内容分享给大家学习，涵盖各种算法和数据结构的知识，帮助大家更好地掌握编程技能。