二叉树基本概念


二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。

二叉树特点是每个结点最多只能有两棵子树,且有左右之分。

详细介绍请参考二叉树的概念

遍历类型

由于二叉树每个节点有不同的方向,所以我们必须指定一个遍历的顺序,不同的遍历顺序得到的结果也不一样,所以一般分为深度优先遍历(前序遍历中序遍历后续遍历,和广度优先遍历(层序遍历

对于前序遍历中序遍历后续遍历而言,是以根节点为主,根在前表示前序,根在中间表示中序,根在后,表示后续,而左右两个节点按照左在前,右在后的顺序,所以,这三种遍历的方式他们的顺序分别是:

  • 前序遍历:访问根结点->遍历左子树->遍历右子树

  • 后续遍历:遍历左子树->遍历右子树->访问根结点

  • 中序遍历:遍历左子树->访问根结点->遍历右子树

如下图二叉树:

image.png


深度优先遍历
先序遍历
中序遍历
后序遍历
解释
对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。
即根节点->左子树->右子树。
对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。
即左子树->根节点->右子树。
对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。
即左子树->右子树->根节点。
原则
①输出根。
②访问左子树。【先访问左子树中的左子树,再访问左子树中的右子树。】直到访问到叶子节点后输出。
③访问右子树。【先访问右子树中的左子树,再访问右子树中的右子树。】直到访问到叶子节点后输出。
①访问左子树。【先访问左子树中的左子树,再访问左子树中的右子树。】直到访问到叶子节点后输出。
②输出根。
③访问右子树。【先访问右子树中的左子树,再访问右子树中的右子树。】直到访问到叶子节点后输出。
①访问左子树。【先访问左子树中的左子树,再访问左子树中的右子树】。直到访问到叶子节点后输出。
②访问右子树。【先访问右子树中的左子树,再访问右子树中的右子树】。直到访问到叶子节点后输出。
③再返回访问根,并输出。
遍历步骤

A作为根,先输出A。
从A开始,先访问A的左子树。B为左子树的根节点,输出B。B的左子树为D,输出D。D无左右子树,则看B的右子树,为E,输出E。E无左右子树,则A的左子树全部输出完。
 
再访问A的右子树,C为右子树的根节点,输出C。C的左子树为F,输出F。F无左右子树,且C无右子树,A的右子树全部输出完。
A作为根。从A开始,先访问A的左子树。
B的左子树为D,输出D。D无左右子树,则B的左子树已访问完,访问并输出B。再看B的右子树,为E,输出E。E无左右子树,则A的左子树全部输出完,返回并输出A。
 
同理,再看A的右子树。
C的左子树为F,输出F。F无左右子树,则C的左子树已访问完,返回并输出C。C无右子树,则A的右子树全部输出完。
先访问A的左子树。再访问左子树中的左子树。即A的左子树为B,再访问B的左子树D。D没有左右子树,输出D。
然后访问左子树中的右子树。即访问B的右子树E,E没有左右子树,输出E。再输出B。
然后访问A的右子树。再访问右子树中的左子树。即A的右子树为C,再访问C的左子树F。F没有左右子树,输出F。
然后访问右子树中的右子树。即访问C的右子树,C没有右子树,输出C。再输出A。
遍历结果
A(BDE)(CF)
(DBE)A(FC)
(DEB)(FC)A

PHP用递归、非递归方式实现深度优先遍历二叉树

1、先序遍历

<?php
class Node {
    public $value;
    public $left;
    public $right;
}
class BT {
    // 非递归
    // 前序遍历 根节点→左子树→右子树
    // 先访问根节点,再遍历左子树,最后遍历右子树;并且在遍历左右子树时,仍需先遍历根节点,然后访问左子树,最后遍历右子树
    public function preOrder($root) {
        $stack = array();
        array_push($stack, $root);
        while (!empty($stack)) {
            $center_node = array_pop($stack);
            echo $center_node->value . "  "; // 先输出根节点
            if ($center_node->right != null) {
                array_push($stack, $center_node->right); // 压入左子树
            }
            if ($center_node->left != null) {
                array_push($stack, $center_node->left);
            }
        }
    }

    // 递归
    // 前序遍历
    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);    //递归遍历右树
            }
        }
    }
}
// 测试
$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();

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

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

$bst = new BT();
echo "----深度优先----";
echo "</br>";
echo "非递归--前序遍历:";
$bst->preOrder($a);
echo "</br>";
echo "递归--前序遍历:";
$bst->pre_order($a);

PHP用递归、非递归方式实现二叉树的先序遍历

2、中序遍历

class Node {
    public $value;
    public $left;
    public $right;
}
class BT {
    // 非递归
    // 中序遍历
    // 左子树→根节点→右子树
    public function inOrder($root) {
        $stack = array();
        $current_node = $root;
        while (!empty($stack) || $current_node != null) {
            while ($current_node != null) {
                array_push($stack, $current_node);
                $current_node = $current_node->left;
            }
            $current_node = array_pop($stack);
            echo $current_node->value . " ";
            $current_node = $current_node->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); // 递归遍历右树
            }
        }
    }
}

// 测试
$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();

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

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

$bst = new BT();

echo "----深度优先----";
echo "</br>";
echo "非递归--中序遍历:";
$bst->inOrder($a);
echo "</br>";
echo "递归--中序遍历:";
$bst->in_order($a);
echo "</br>";

PHP用递归、非递归方式实现二叉树的中序遍历

3、后序遍历

<?php
class Node {
    public $value;
    public $left;
    public $right;
}
class BT {
    // 非递归
    // 后序遍历 左子树→右子树→根节点
    // 先遍历左子树,然后遍历右子树,最后访问根节点;同样,在遍历左右子树的时候同样要先遍历左子树,然后遍历右子树,最后访问根节点
    public function postOrder($root) {
        $stack = array();
        $out_stack = array();
        array_push($stack, $root);
        while (!empty($stack)) {
            $center_node = array_pop($stack);
            array_push($out_stack, $center_node); // 最先压入根节点,最后输出
            if ($center_node->left != null) {
                array_push($stack, $center_node->left);
            }
            if ($center_node->right != null) {
                array_push($stack, $center_node->right);
            }
        }
        while (!empty($out_stack)) {
            $center_node = array_pop($out_stack);
            echo $center_node->value . "  ";
        }
    }

    // 递归
    // 后序遍历
    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 . " ";    // 根
        }
    }
}

// 测试
$a = new Node();
$b = new Node();
$c = new Node();
$d = new Node();
$e = new Node();
$f = new Node();

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

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

$bst = new BT();

echo "----深度优先----";
echo "</br>";
echo "非递归--后序遍历:";
$bst->postOrder($a);
echo "</br>";
echo "递归--后序遍历:";
$bst->post_order($a);
echo "</br>";

PHP用递归、非递归方式实现二叉树的后序遍历

PHP用递归、非递归方式实现广度优先遍历二叉树

序遍历

<?php
class Node {
    public $value;
    public $left;
    public $right;
}
class BT {
    // 非递归
    public function levelOrder($root) {
        if ($root == null) {
            return;
        }
        $node = $root;
        $queue = array();
        array_push($queue, $node);  // 根节点入队
        while (!empty($queue)) {    // 持续输出节点,直到队列为空
            $node = array_shift($queue);    // 队首元素出队
            echo $node->value . " ";
            // 左节点先入队
            if ($node->left != null) {
                array_push($queue, $node->left);
            }
            // 然后右节点入队
            if ($node->right != null) {
                array_push($queue, $node->right);
            }
        }
    }

    // 递归
    // 获取树的层数(最大深度)
    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;
//        return $left_depth > $right_depth ? ($left_depth + 1) : ($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();

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

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

$bst = new BT();
echo "----广度优先----";
echo "</br>";
echo "非递归:";
$bst->levelOrder($a);
echo "</br>";
echo "递归:";
$bst->level_order($a);

PHP用递归、非递归方式实现二叉树的层次遍历