欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

打印叶节点到根的路径

程序员文章站 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);
}