本节我们来学习二叉树的遍历。二叉树的遍历通常有3种算法:前序遍历、中序遍历和后序遍历。当然,对二叉树来说也可以使用其它的遍历算法,例如从上至下按层级遍历,从左至右或从右至左等等。我们并不打算实现全部的二叉树遍历算法,而只针对前中后这3种算法进行实现。首先来看一下这3种算法的文字描述:
可见,这3种遍历算法都是基于递归来描述的。所谓的前序、中序和后序,就是访问顺序是当前节点在前、在中间和在后面。
接下来我们来实现这3种遍历算法:
//前序遍历 void tree_preamble_visit(s_tree *tree, s_node *node) { if (tree == null) { return; } if (tree->root == null) { return; } if (node == null) { return; } //中 tree->visit_node(node->data); //左 tree_preamble_visit(tree, node->left_child); //右 tree_preamble_visit(tree, node->right_child); } //中序遍历 void tree_inorder_visit(s_tree *tree, s_node *node) { if (tree == null) { return; } if (tree->root == null) { return; } if (node == null) { return; } //左 tree_inorder_visit(tree, node->left_child); //中 tree->visit_node(node->data); //右 tree_inorder_visit(tree, node->right_child); } //后序遍历 void tree_postorder_visit(s_tree *tree, s_node *node) { if (tree == null) { return; } if (tree->root == null) { return; } if (node == null) { return; } //左 tree_postorder_visit(tree, node->left_child); //右 tree_postorder_visit(tree, node->right_child); //中 tree->visit_node(node->data); }
假设我们有一个这样的二叉树:
编写一个main函数来构建这样一棵二叉树,并对其进行前序遍历、中序遍历、后序遍历:
#include <stdio.h> #include <stdlib.h> #include "tree.h" //删除整数函数 void free_int(int *i) { if (i != null) { free(i); } } //访问整数函数 void visit_int(int *i) { if (i != null) { printf("%d ", *i); } } int main(int argc, char **args) { int *t0 = (int *) malloc(sizeof(int)); int *t1 = (int *) malloc(sizeof(int)); int *t2 = (int *) malloc(sizeof(int)); int *t3 = (int *) malloc(sizeof(int)); int *t4 = (int *) malloc(sizeof(int)); int *t5 = (int *) malloc(sizeof(int)); int *t6 = (int *) malloc(sizeof(int)); int *t7 = (int *) malloc(sizeof(int)); int *t8 = (int *) malloc(sizeof(int)); *t0 = 0; *t1 = 1; *t2 = 2; *t3 = 3; *t4 = 4; *t5 = 5; *t6 = 6; *t7 = 7; *t8 = 8; //初始化树 s_tree tree; tree_init(&tree, &visit_int, &free_int); s_node *n0 = (s_node *) malloc(sizeof(s_node)); s_node *n1 = (s_node *) malloc(sizeof(s_node)); s_node *n2 = (s_node *) malloc(sizeof(s_node)); s_node *n3 = (s_node *) malloc(sizeof(s_node)); s_node *n4 = (s_node *) malloc(sizeof(s_node)); s_node *n5 = (s_node *) malloc(sizeof(s_node)); s_node *n6 = (s_node *) malloc(sizeof(s_node)); s_node *n7 = (s_node *) malloc(sizeof(s_node)); s_node *n8 = (s_node *) malloc(sizeof(s_node)); tree_init_node(n0, t0); tree_init_node(n1, t1); tree_init_node(n2, t2); tree_init_node(n3, t3); tree_init_node(n4, t4); tree_init_node(n5, t5); tree_init_node(n6, t6); tree_init_node(n7, t7); tree_init_node(n8, t8); //插入根节点 tree_insert(&tree, null, 0, n0); tree_insert(&tree, n0, 0, n1); tree_insert(&tree, n0, 1, n2); tree_insert(&tree, n1, 0, n3); tree_insert(&tree, n1, 1, n4); tree_insert(&tree, n2, 0, n5); tree_insert(&tree, n2, 1, n6); tree_insert(&tree, n5, 0, n7); tree_insert(&tree, n5, 1, n8); tree_preamble_visit(&tree, tree.root); printf("\n"); tree_inorder_visit(&tree, tree.root); printf("\n"); tree_postorder_visit(&tree, tree.root); printf("\n"); //销毁树 tree_destroy(&tree); return 0; }
运行结果:
0 1 3 4 2 5 7 8 6 3 1 4 0 7 5 8 2 6 3 4 1 7 8 5 6 2 0
本例代码:
code path chapter.05/e.g.5.2/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号