二叉树的四种遍历方法
二叉树有四种遍历方式,先序遍历,中序遍历,后序遍历以及层次遍历。
先序遍历
二叉树的先序,中序,后序遍历表示访问二叉树中结点的先后顺序,先序表示先访问结点,中序表示中间访问结点,后序表示最后访问结点。
先序遍历二叉树的顺序:
- 访问根结点。
- 先序遍历左子树。
- 先序遍历右子树。
采用递归的方式来编写遍历二叉树的代码是最直观的。代码实现:
//遍历时结点操作函数指针
typedef void (*operateFunc)(tagTreeNode* node);
void traversalInPreOrder(tagBinTree* root, operateFunc func)
{
if (root == NULL)
return ;
if (func)
func(root);
traversalInPreOrder(root->left, func);
traversalInPreOrder(root->right, func);
}
也可以采用非递归的方式来实现遍历,此时需要借助于栈的数据结构:
- 将根结点入栈。
- 从栈中弹出一个结点并访问。
- 结点右儿子非空则入栈。
- 结点左儿子非空则入栈。
- 重复步骤2,3,4,直到栈为空,遍历结束。
代码实现:
void traversalInPreOrder(tagBinTree* root, operateFunc func)
{
if (root == NULL)
return ;
ttStack* stack = stackInit();
if (stack == NULL)
return ;
push(stack, root);
while (!stackEmpty(stack)) {
tagBinTree* node = pop(stack);
if (func)
func(node);
if (node->right != NULL)
push(stack, node->right);
if (node->left != NULL)
push(stack, node->left);
}
stackDestory(stack);
}
中序遍历
中序遍历二叉树的顺序:
- 中序遍历左子树。
- 访问根结点。
- 中序遍历右子树。
代码实现:
void traversalInPostOrder(tagBinTree* root, operateFunc func)
{
if (root == NULL)
return ;
traversalInPostOrder(root->left, func);
traversalInPostOrder(root->right, func);
if (func)
func(root);
}
非递归实现同先序遍历,略。
后序遍历
后序遍历二叉树的顺序:
- 后序遍历左子树。
- 后序遍历右子树。
- 访问根结点。
代码实现:
void traversalInOrder(tagBinTree* root, operateFunc func)
{
if (root == NULL)
return ;
traversalInOrder(root->left, func);
if (func)
func(root);
traversalInOrder(root->right, func);
}
非递归实现同先序遍历,略。
层次遍历
层次遍历就是按照树的结构从上到下,从左到右的顺序依次访问每个结点。
层次遍历需要借助于一个抽象数据类型-队列:
- 将树的根结点入队列。
- 从队列中取出一个结点并访问。
- 判断结点的左右儿子是否为空,不为空则入队列。
- 重复步骤2, 3,直到队列为空。遍历完成。
代码实现:
void traversalInLevelOrder(tagBinTree* root, operateFunc func)
{
ttQueue* queue = createQueue(0);
if (queue == NULL)
return ;
enqueue(queue, root);
while (!queueEmpty(queue)) {
tagBinTree* node = (tagBinTree*)dequeue(queue);
if (node != NULL) {
if (node->left != NULL)
enqueue(queue, node->left);
if (node->right != NULL)
enqueue(queue, node->right);
if (func != NULL)
func(node);
}
}
disposeQueue(queue);
}
参考:
<数据结构与算法分析-C语言描述> P4 数据结构与算法分析-C语言描述>- 版权声明: