建立二叉树 先序、中序、后序遍历二叉树
时间: 2023-11-01 15:08:56 浏览: 101
二叉树是一种树形结构,其中每个节点最多有两个子节点。建立二叉树的方法有很多种,其中一种常用的方法是通过输入带空格的前序序列建立二叉链表。具体步骤如下:
1. 读取输入的带空格的前序序列,将其存储在一个数组中。
2. 定义一个栈,将根节点入栈。
3. 从数组中取出下一个元素,如果该元素不为空,则将其作为当前节点的左子节点,并将该节点入栈。
4. 如果该元素为空,则从栈中弹出一个节点,将其作为当前节点,并从数组中取出下一个元素,将其作为当前节点的右子节点,并将该节点入栈。
5. 重复步骤3和4,直到数组中的所有元素都被处理完毕。
建立二叉树后,可以通过递归或非递归的方式进行先序、中序和后序遍历。其中,先序遍历的顺序是先遍历根节点,然后遍历左子树,最后遍历右子树;中序遍历的顺序是先遍历左子树,然后遍历根节点,最后遍历右子树;后序遍历的顺序是先遍历左子树,然后遍历右子树,最后遍历根节点。
以下是PHP基于非递归算法实现先序、中序及后序遍历二叉树的代码示例:
```php
// 定义二叉树节点类
class TreeNode {
public $val;
public $left;
public $right;
public function __construct($val) {
$this->val = $val;
$this->left = null;
$this->right = null;
}
}
// 建立二叉树
function buildTree($preorder) {
$stack = array();
$root = new TreeNode(array_shift($preorder));
array_push($stack, $root);
while (!empty($preorder)) {
$node = array_shift($preorder);
if ($node !== null) {
$cur = new TreeNode($node);
$stack[count($stack) - 1]->left = $cur;
array_push($stack, $cur);
} else {
$stack[count($stack) - 1]->right = null;
array_pop($stack);
}
}
return $root;
}
// 非递归实现先序遍历
function preorderTraversal($root) {
$stack = array();
$res = array();
array_push($stack, $root);
while (!empty($stack)) {
$node = array_pop($stack);
if ($node !== null) {
array_push($res, $node->val);
array_push($stack, $node->right);
array_push($stack, $node->left);
}
}
return $res;
}
// 非递归实现中序遍历
function inorderTraversal($root) {
$stack = array();
$res = array();
$cur = $root;
while ($cur !== null || !empty($stack)) {
while ($cur !== null) {
array_push($stack, $cur);
$cur = $cur->left;
}
$node = array_pop($stack);
array_push($res, $node->val);
$cur = $node->right;
}
return $res;
}
// 非递归实现后序遍历
function postorderTraversal($root) {
$stack = array();
$res = array();
array_push($stack, $root);
while (!empty($stack)) {
$node = array_pop($stack);
if ($node !== null) {
array_push($res, $node->val);
array_push($stack, $node->left);
array_push($stack, $node->right);
}
}
return array_reverse($res);
}
```
阅读全文
相关推荐














