树和二叉树-二叉树遍历

树和二叉树-二叉树遍历

二叉树遍历

主要有深度优先遍历和广度优先遍历  

深度优先遍历

对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。

广度优先遍历

又叫层次遍历,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。
四种主要的遍历思想为:
前序遍历:根结点 ---> 左子树 ---> 右子树
中序遍历:左子树---> 根结点 ---> 右子树
后序遍历:左子树 ---> 右子树 ---> 根结点
层次遍历:只需按层次遍历即可

undefined


undefined


undefined


class Node {
public $value;
public $left;
public $right;
}
class BT {
// 递归
// 前序遍历
public function pre_order($root) {
if ($root != null) {
echo $root->value . " "; // 根
if ($root->left != null) {
$this->pre_order($root->left); //递归遍历左树
}
if ($root->right != null) {
$this->pre_order($root->right); //递归遍历右树
}
}
}

// 中序遍历
public function in_order($root) {
if ($root != null) {
if ($root->left != null) {
$this->in_order($root->left); // 递归遍历左树
}
echo $root->value . " ";
if ($root->right != null) {
$this->in_order($root->right); // 递归遍历右树
}
}
}

// 后序遍历
public function post_order($root) {
if ($root != null) {
if ($root->left != null) {
$this->post_order($root->left); // 递归遍历左树
}
if ($root->right != null) {
$this->post_order($root->right); // 递归遍历右树
}
echo $root->value . " "; // 根
}
}

// 递归
// 层次遍历
public function getDepth($root) {
if ($root == null) { // 节点为空
return 0;
}
if ($root->left == null && $root->right == null) { // 只有根节点
return 1;
}

$left_depth = $this->getDepth($root->left);
$right_depth = $this->getDepth($root->right);

return ($left_depth > $right_depth ? $left_depth : $right_depth) + 1;
}

public function level_order($root) {
// 空树或层级不合理
$depth = $this->getDepth($root);
if ($root == null || $depth < 1) {
return;
}
for ($i = 1; $i <= $depth; $i++) {
$this->printTree($root, $i);
}
}

public function printTree($root, $level) {
// 空树或层级不合理
if ($root == null || $level < 1) {
return;
}
if ($level == 1) {
echo $root->value;
}
$this->printTree($root->left, $level - 1);
$this->printTree($root->right, $level - 1);
}
}
// 测试
$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();
$g = new Node();

$a->value = "A";
$b->value = "B";
$c->value = "C";
$d->value = "D";
$e->value = "E";
$f->value = "F";
$g->value = "G";

$a->left = $b;
$a->right = $c;
$b->left = $d;
$b->right = $e;
$c->left = $f;
$c->right = $g;

$bst = new BT();
echo "----深度优先----";
echo "</br>";
echo "递归--前序遍历:";
$bst->pre_order($a);
echo "</br>";
echo "递归--中序遍历:";
$bst->in_order($a);
echo "</br>";
echo "递归--后序遍历:";
$bst->post_order($a);
echo "</br>";
echo "递归--层次遍历:";
$bst->level_order($a);