二叉树(链式存储)-递归实现层次遍历实现思路
层次遍历
层次遍历:自上而下,从左往右访问结点
思路
除了根节点首先需要访问外，其他结点遍历都遵循先访问左孩子结点，后访问右孩子结点,所以只需要传入父节点，就可以访问左右孩子结点了，符合递归的思想。
实现代码
typedef struct BiTNode {
ElemType data;
BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
/*
* 递归实现层次遍历
* 实现思路:根节点只访问一次，左右孩子结点先访问，再递归访问孩子的孩子，就是一层一层访问，使用递归
*/
bool flag = true;
bool LevelOrderRecursion(BiTree T) {
if (T == NULL) {
return false;
}
if (T != NULL && flag == true) {
//只访问一次，用于访问根节点，不然递归会重复访问左右孩子结点
printf("%d ", T->data);
flag = false;
}
if (T->lchild != NULL) {
//访问左孩子
printf("%d ", T->lchild->data);
}
if (T->rchild != NULL) {
//访问右孩子
printf("%d ", T->rchild->data);
}
LevelOrderRecursion(T->lchild); //递归访问
LevelOrderRecursion(T->rchild); //递归访问
return true;
}
下一篇：
删除链表中重复的元素