c编程如何从树中获取叶子列表
我有一个二叉树，我需要列出所有的叶子
树定义是：
typedef struct tree { TreeNode* root; List leafList; } Tree; treeNode定义：
typedef struct treeNode { int data; struct treeNode* parent; struct treeNode* left; struct treeNode* right; } TreeNode;
列表定义
typedef struct list { ListNode* head; ListNode* tail;
}列表; listNode定义
typedef struct listNode { int data; struct listNode* next; } ListNode;
在我的第一步，我建立了树（很好）。
现在，在我的第二步，我需要从所有叶子列出一个列表。 对于前 以下树将返回1-> 2-> 5-> 7的列表
6 / \ 4 3 /\ /\ 1 2 5 7
这是我到目前为止所得到的
我的树构建器function：
Tree BuildTreeFromArrayWithLeafList(int *arr, int size) { Tree T; T.root = BuildTreeRec(arr, size); // till here all working fine T.leafList.head = BuildLeafList(T.root); //function fail return T; }
现在我的问题BuildLeafList函数需要构建树叶列表并返回它，但无论我如何更改我的代码它都会失败。 这是我的BuildLeafList函数代码：
ListNode* BuildLeafList(TreeNode *tn) { ListNode *temp; if (tn == NULL) return; if (tn->left == NULL && tn->right == NULL) return CreateListNode(tn->data); temp = BuildLeafList(tn->left); temp->next = BuildLeafList(tn->right); return temp; }
有人可以帮我做这个函数构建叶子列表并返回它。
这是它应该在树结构的最终图像中查看的方式
感谢任何帮助
提前致谢
回归’临时’是这里的问题。 当您从左子树更改为右子树时，最后一个节点将丢失。
节点6，temp == NULL，终止条件不满足，因此调用buildleaflist（tn-> left == 4）
节点4，temp == NULL，终止条件不满足，因此调用buildleaflist（tn-> left == 1）
节点1，temp == NULL，终止条件满足，因此节点被分配并返回到先前级别（节点4）。
节点4，temp-> data == 1，调用buildleaflist（（tn-> right == 2）
节点2，temp == NULL，终止条件满足，因此节点被分配并返回到先前级别（节点4）。
节点4，temp-> next =（节点分配为2）。 列表看起来像1-> 2，temp指向1.节点4返回节点6。
节点6，temp-> data是1.调用buildleaflist（tn-> right == 3）。
节点3，temp == NULL，终止条件不满足，调用buildleaflist（tn-> left == 5）
节点5，temp == NULL，终止条件满足，因此分配节点并返回节点3。
节点3，temp-> data == 5，调用buildleaflist（tn-> right == 7）。
节点7，temp == NULL，终止条件满足，因此分配节点并返回节点3。
节点3，temp-> next =（节点7）。 因此列表（来自节点3的上下文）看起来像5-> 7。 节点3返回节点6。
问题在于此。 temp是节点6仍然指向’1’。 因此，当您执行temp-> next = buildleaflist（tn-> right）时，节点2会丢失。 该列表现在看起来像1-> 5-> 7。
我建议你传递一个双指针到buildleaflist（），它可以用来携带列表的头部。 然后，从buildleaflist（）返回（temp-> next）。
ListNode* BuildLeafList(TreeNode *tn, TreeNode **head) { ListNode *temp; if (tn == NULL) return; if (tn->left == NULL && tn->right == NULL) return CreateListNode(tn->data); temp = BuildLeafList(tn->left); if (*head == NULL) { *head = temp; } temp->next = BuildLeafList(tn->right); return temp->next; }