1. 前序遍历:
遍历顺序为:根 左子树 右子数
如图:
实现是非常简单的
代码为:
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->_data);
BinaryTreePrevOrder(root->_left);
BinaryTreePrevOrder(root->_right);
}
2.中序遍历
中序遍历顺序为:左子树 根 右子树 。
和前序遍历类似 如图:
实现利用递归的方法 先进左子树 再根 然后 再右子树.
代码为:
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
BinaryTreeInOrder(root->_left);
printf("%d ", root->_data);
BinaryTreeInOrder(root->_right);
}
3. 后序遍历:
遍历的顺序为:右子树 左子树 根
如图:
代码:
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
BinaryTreeInOrder(root->_left);
BinaryTreeInOrder(root->_right);
printf("%d ", root->_data);
}
4.层序遍历
层序遍历的意思为: 分层遍历,先遍历第一层、第二层、第三层…..直到遍历最后一层结束.
如图:
实现 :
C需要使用大家自己手搓的队列,实现逻辑为,首先队列 Push 二叉树的根(根入队列),
然后出队列并让这个根的两个孩子入队列(先入左,再入右),出到NULL的时候没有孩子,直接
出下一个根,直到队列里的数据出完。
如图:
实现:
代码为:
void BinaryTreeLevelOrder(BTNode* root)
{
Con H_E;
Queue *List=(Queue*)malloc(sizeof(Queue));
QueInit(List, &H_E);
if (root != NULL)
{
QuePush(List, &H_E, root);
}
while (H_E.Frist)
{
printf("%c", H_E.Frist->Date->_data);
if (H_E.Frist->Date->_left)
{
QuePush(List, &H_E, H_E.Frist->Date->_left);
}
if (H_E.Frist->Date->_right)
{
QuePush(List, &H_E, H_E.Frist->Date->_right);
}
QuePop(&H_E);
}
QueDestroy(&H_E);
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net