打印叶节点到根的路径
程序员文章站
2022-05-24 18:15:09
...
#include<stdio.h>
#include<malloc.h>
typedef struct node{
int data;
struct node *lchild;
struct node *rchild;
} *binaryTree;
binaryTree init();
void printLeavesToRoot(binaryTree root, int* arr, int pos);
int main()
{
/*
input:
1
2 3
4 5 6 7
*/
binaryTree root = init();
int arr[100] = {0}, pos = 0;
printLeavesToRoot(root, arr, pos);
}
binaryTree init()
{
binaryTree node1 = (binaryTree)malloc(sizeof(struct node)); node1->data = 1;
binaryTree node2 = (binaryTree)malloc(sizeof(struct node)); node2->data = 2;
binaryTree node3 = (binaryTree)malloc(sizeof(struct node)); node3->data = 3;
binaryTree node4 = (binaryTree)malloc(sizeof(struct node)); node4->data = 4;
binaryTree node5 = (binaryTree)malloc(sizeof(struct node)); node5->data = 5;
binaryTree node6 = (binaryTree)malloc(sizeof(struct node)); node6->data = 6;
binaryTree node7 = (binaryTree)malloc(sizeof(struct node)); node7->data = 7;
node1->lchild = node2; node1->rchild = node3;
node2->lchild = node4; node2->rchild = node5;
node3->lchild = node6; node3->rchild = node7;
node4->lchild = NULL; node4->rchild = NULL;
node5->lchild = NULL; node5->rchild = NULL;
node6->lchild = NULL; node6->rchild = NULL;
node7->lchild = NULL; node7->rchild = NULL;
return node1;
}
void printLeavesToRoot(binaryTree root, int *arr, int pos)
{
if(root == NULL)
return;
arr[pos++] = root->data;
if(root->lchild == NULL && root->rchild == NULL)
{
pos --;
for(int i = pos; i >=0; i--)
printf("%d ", arr[i]);
printf("\n");
return;
}
printLeavesToRoot(root->lchild, arr, pos);
printLeavesToRoot(root->rchild, arr, pos);
}