#include <stdio.h>

#include <stdlib.h>

typedef struct TreeNode

{

struct TreeNode *left, *right, *next;

int data;

}TreeNode;

typedef TreeNode * Tree;

void LeafLinked(Tree t, TreeNode **prevLeaf, TreeNode **head)

{

if(t) {

if(t->left == NULL && t->right == NULL) { //leaf

if(*head == NULL)

*head = t;

else if(*prevLeaf)

(*prevLeaf)->next = t;

*prevLeaf = t;

}

else { //at least one child

LeafLinked(t->left, prevLeaf, head);

LeafLinked(t->right, prevLeaf, head);

}

}

}

/*Utilities*/

inline TreeNode * makeTreeNode(int data)

{

TreeNode *n = calloc(sizeof(TreeNode), 1);

n->data = data;

return n;

}

inline void printList(Tree t)

{

while(t)

{

printf("%d ", t->data);

t = t->next;

}

printf("\n");

}

int main()

{

/*level 0*/

Tree t = makeTreeNode(10);

/*level 1*/

t->left = makeTreeNode(20);

t->right = makeTreeNode(30);

/*level 2*/

t->left->left = makeTreeNode(40);

t->left->right = makeTreeNode(70);

t->right->left = makeTreeNode(50);

t->right->right = makeTreeNode(60);

/*level 3*/

t->left->left->left = makeTreeNode(70);

t->right->right->left = makeTreeNode(60);

t->right->right->right = makeTreeNode(160);

/*Empty List head*/

TreeNode *head = NULL, *prevLeaf = NULL;

/*Convert tree to list*/

LeafLinked(t, &prevLeaf, &head);

/*print list*/

printList(head);

return 0;

}

`Python Version:`

class BinaryTree:

def __init__(self, e):

self.left = self.right = self.next = None

self.data = e

def LinkLeaves(t):

if t:

if t.left or t.right:

for x in LinkLeaves(t.left):

yield x

for x in LinkLeaves(t.right):

yield x

else:

yield t

def printList(t):

while t:

print t.data,

t = t.next

def main():

t = BinaryTree(10);

t.left = BinaryTree(20)

t.right = BinaryTree(30)

t.left.left = BinaryTree(40)

t.left.right = BinaryTree(70)

t.right.left = BinaryTree(50)

t.right.right = BinaryTree(60)

t.left.left.left = BinaryTree(70)

t.right.right.left = BinaryTree(60)

t.right.right.right = BinaryTree(160)

head = None

prevLeaf = None

for x in LinkLeaves(t):

if head is None:

head = x

else:

prevLeaf.next = x

prevLeaf = x

printList(head)

if __name__ == '__main__':

main()

Advertisements