不同于线性数据结构,二叉树的遍历需要将非线性关联的节点转化为线性序列,因此转换遍历的方式不同,遍历的结果也各有区别。从大角度来说,二叉树有两种遍历方式:
- 深度优先遍历 (前序遍历,中序遍历,后序遍历)
- 广度优先遍历 (层序遍历)
首先定义一个简单的二叉树结构,用代码实现一个基本的二叉树的示例如下:
# 单节点 结构定义
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# 创建二叉树
def create_binary_tree(input_list):
if input_list is None or len(input_list) == 0:
return None
data = input_list.pop(0)
if data is None:
return None
node = TreeNode(data)
node.left = create_binary_tree(input_list)
node.right = create_binary_tree(input_list)
return node
如图:。
深度优先遍历
所谓深度优先遍历,顾名思义就是在一个纵深的角度访问到底,下面分别说明下深度优先下的各个遍历方式。
1.前序遍历
前序遍历顺序是 根节点 -> 左子树 -> 右子树 示例中的访问顺序是 1->2->4->5->3->6
def pre_order_traversal(node):
if node is None:
return
print(node.data)
pre_order_traversal(node.left)
pre_order_traversal(node.right)
return node
2.中序遍历
中序遍历顺序是 左子树 -> 根节点 -> 右子树 示例中的访问顺序是 4->2->5->1->3->6
def in_order_traversal(node):
if node is None:
return
in_order_traversal(node.left)
print(node.data)
in_order_traversal(node.right)
return node
3.后序遍历
后序遍历顺序是 右子树 -> 左子树 -> 根节点 示例中的访问顺序是 4->5->2->6->3->1
def post_order_traversal(node):
if node is None:
return
post_order_traversal(node.left)
post_order_traversal(node.right)
print(node.data)
return node
广度优先遍历
广度优先的定义比较难理解,在各个方向上逐步去访问,直到当前的方向已经没有有效值了。
3.层序遍历
以层序遍历作为例子:在二叉树的每依次层上面横向遍历所有的节点,直到没有节点可以访问为止。那示例的二叉树的访问结果为 1->2->3->4->5->6
def level_order_traversal(node):
queue = Queue()
queue.put(node)
while not queue.empty():
node = queue.get()
print(node.data)
if node.left is not None:
queue.put(node.left)
if node.right is not None:
queue.put(node.right)
作为理解的练习代码,下面贴上PHP的实现:
class TreeNode
{
public $data = null;
public $left = null;
public $right = null;
public function __construct($data)
{
$this->data = $data;
}
}
function create_tree(array &$list)
{
if ($list === null || empty($list)) {
return null;
}
$data = array_shift($list);
if ($data === null) {
return null;
}
$node = new TreeNode($data);
$node->left = create_tree($list);
$node->right = create_tree($list);
return $node;
}
function pre_order_traversal($node)
{
if ($node === null) {
return;
}
echo $node->data . PHP_EOL;
pre_order_traversal($node->left);
pre_order_traversal($node->right);
return $node;
}
function in_order_traversal($node)
{
if ($node === null) {
return;
}
in_order_traversal($node->left);
echo $node->data . PHP_EOL;
in_order_traversal($node->right);
return $node;
}
function post_order_traversal($node)
{
if ($node === null) {
return;
}
post_order_traversal($node->left);
post_order_traversal($node->right);
echo $node->data . PHP_EOL;
return $node;
}
function level_order_traversal($node)
{
$queue = [];
array_push($queue, $node);
while (!empty($queue)) {
$node = array_shift($queue);
echo $node->data.PHP_EOL;
if($node->left) {
array_push($queue, $node->left);
}
if($node->right) {
array_push($queue, $node->right);
}
}
}
没有评论