当前位置： 面试刷题>> 完全二叉树 (经典算法题500道)
### 题目描述补充
**题目**： 编写一个算法，用于实现一个完全二叉树的构建、遍历以及层级遍历（或称为广度优先遍历）。完全二叉树是一种特殊的二叉树，其中除了最后一层外，每一层都被完全填满，并且所有节点都尽可能地向左对齐。
**要求**：
1. **构建完全二叉树**：给定一个有序数组（通常是升序或降序），根据数组的值构建一棵完全二叉树。
2. **遍历完全二叉树**：
- 实现前序遍历（根节点 -> 左子树 -> 右子树）。
- 实现中序遍历（左子树 -> 根节点 -> 右子树，但在此上下文中可能不常用，因为完全二叉树不保证有序性）。
- 实现后序遍历（左子树 -> 右子树 -> 根节点）。
3. **层级遍历**：从根节点开始，按从上到下、从左到右的顺序访问所有节点。
### 示例代码
#### PHP 示例
```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 示例
```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 示例
```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);
```
**码小课网站中有更多相关内容分享给大家学习**，涵盖各种算法和数据结构的知识，帮助大家更好地掌握编程技能。