遍历二叉树(递归法)¶
前序遍历¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | /**
* preorder traverse a binary tree
**/
void
preorder_traverse(struct binary_tree_node *root,
void handle(struct binary_tree_node *))
{
// return immediately if given tree is NULL
if (root == NULL) {
return;
}
// handle root node before traversing subtrees
handle(root);
// traverse left subtree recursively if not NULL
if (root->left) {
preorder_traverse(root->left, handle);
}
// traverse right subtree recursively if not NULL
if (root->right) {
preorder_traverse(root->right, handle);
}
}
|
中序遍历¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | /**
* inorder traverse a binary tree
**/
void
inorder_traverse(struct binary_tree_node *root,
void handle(struct binary_tree_node *))
{
// return immediately if given tree is NULL
if (root == NULL) {
return;
}
// traverse left subtree recursively if not NULL
if (root->left) {
inorder_traverse(root->left, handle);
}
// handle root node
handle(root);
// traverse right subtree recursively if not NULL
if (root->right) {
inorder_traverse(root->right, handle);
}
}
|
后序遍历¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | /**
* postorder traverse a binary tree
**/
void
postorder_traverse(struct binary_tree_node *root,
void handle(struct binary_tree_node *))
{
// return immediately if given tree is NULL
if (root == NULL) {
return;
}
// traverse left subtree recursively if not NULL
if (root->left) {
postorder_traverse(root->left, handle);
}
// traverse right subtree recursively if not NULL
if (root->right) {
postorder_traverse(root->right, handle);
}
// traverse right subtree recursively if not NULL
handle(root);
}
|