C语言:如何用递归的方法层序遍历一棵二叉树?

Danmoits
  • 33

层序遍历使用递归,请求大佬描述一下详细思路,或者提供伪代码,感激不尽!

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT  10

typedef int status;
typedef int ElemType;
typedef int KeyType;
//数据元素类型定义

typedef struct {
    //二叉树结点类型定义
    KeyType  key;
    char others[20];
} TElemType;

typedef struct BiTNode {
    //二叉链表结点的定义
    TElemType  data;
    struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;
回复
阅读 371
2 个回答

有个思路,就是给每个节点增加一个指向下一个兄弟节点的指针。然后访问的时候从根开始,向下遍历所有左孩子,对于每一个左孩子,递归遍历它的下一个兄弟节点。

麻烦的地方在于建立树的时候,要设置好指向下一个兄弟节点的指针。

可以用BFS,虽然不符合题目中递归的条件

BiTNode* q[TREE_SIZE];
q[0]=Root;
int head=0,tail=1;
while(head!=tail){
    BiTNode* u=q[head++];
    if(u->lchild) q[tail++]=u->lchild;
    if(u->rchild) q[tail++]=u->rchild;
}
// 此时q内即为答案

非要递归的话,可以给BiTNode增加一个成员depth,递归计算,然后用类似桶排的东西输出(?)总之感觉很难受

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏