秋木叶 发表于 2019-3-18 15:07:27

求从根节点到每一个叶子节点的路径的值的和

例如
    1
   / \
2   3

答案为 12 + 13 = 25

求C语言的完整代码，感谢感谢！

BngThea 发表于 2019-3-18 16:06:06

直接百度

Croper 发表于 2019-3-18 17:10:10

。。伸手也不是这么伸手的啊，
你要求代码，至少把输入格式写出来啊。。你这输入格式是什么。。。。图片么，那我真的不会。。

Croper 发表于 2019-3-18 18:00:15


struct treenode {
        int val;
        treenode* left;
        treenode* right;
        treenode(int n) :val(n),left(nullptr), right(nullptr) {};
};

int GetTreeSum_Loop(int a, treenode* node) {
        if (node == nullptr) return 0;

        a = a * 10 + node->val;
        if (node->left == nullptr && node->right == nullptr) return a;
        return GetTreeSum_Loop(a, node->left) + GetTreeSum_Loop(a, node->right);

}
int GetTreeSum(treenode* root) {
        return GetTreeSum_Loop(0, root);
}

秋木叶 发表于 2019-3-19 16:21:25

本帖最后由 秋木叶 于 2019-3-19 16:23 编辑

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int ElemType;

typedef struct BiTNode
{
        int data;
        struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef struct sqStack
{
    ElemType *base;
    ElemType *top;                // 用于标注栈顶的位置
    int stackSize;
}sqStack;
//全局栈
sqStack s;
//初始化栈
void initStack(sqStack *s)
{
    s->base = (ElemType *)malloc( STACK_INIT_SIZE * sizeof(ElemType) );
    if( !s->base )
      exit(0);
    s->top = s->base;   // 最开始，栈顶就是栈底
    s->stackSize = STACK_INIT_SIZE;
}
//入栈
void Push(sqStack *s, ElemType e)
{
    // 如果栈满，追加空间
    if( s->base - s->top >= s->stackSize ) // 这个根据自己的编译器 和 系统，来决定 s->base - s->top 还是 s->top - s->base
    {
      s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
      if( !s->base )
            exit(0);
      s->top = s->base + s->stackSize;            // 设置栈顶
      s->stackSize = s->stackSize + STACKINCREMENT; // 设置栈的最大容量
    }

    *(s->top) = e;
    s->top++;
}
//出栈
void Pop(sqStack *s, ElemType *e)
{
    if( s->top == s->base )// 栈已空空是也
      return ;
    *e = *--(s->top);
}
//判断栈是否空
int IsEmpty(sqStack *s){
    if( s->top == s->base )
      return 0;
    else
      return 1;
}
// 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
void CreateBiTree(BiTree *T)
{
        char c;

        scanf("%c", &c);
        if( '#' == c )
        {
                *T = NULL;
        }
        else
        {
                *T = (BiTNode *)malloc(sizeof(BiTNode));
                (*T)->data = c;
                CreateBiTree(&(*T)->lchild);
                CreateBiTree(&(*T)->rchild);
        }
}

// 访问二叉树结点的具体操作，你想干嘛？！
void visit(char c, int level)
{
        printf("%c 位于第 %d 层\n", c, level);
}

// 前序遍历二叉树
void PreOrderTraverse(BiTree T, int level)
{
        if( T )
        {
                visit(T->data, level);
                PreOrderTraverse(T->lchild, level+1);
                PreOrderTraverse(T->rchild, level+1);
        }
}

void AllPath(BiTree T,char path[],int pathLength)
{
    if(T!=NULL)
    {
      if(T->lchild==NULL&&T->rchild==NULL)
      {
            path=T->data;
            printf("根节点到%c叶子节点的路径为: ",T->data);
            int xnum = 0;
            for(int i=0;i<=pathLength;i++){
                printf("%c ",path);
                xnum = path - 48 + xnum * 10 ;// 将树中元素 char 转为 int
            }
            Push(&s, xnum);
            //printf(" x=%d \n",xnum);
            printf("\n");
      }
      else
      {
            path=T->data;
            AllPath(T->lchild,path,pathLength);
            AllPath(T->rchild,path,pathLength);
            pathLength--;
      }
    }
}

int main()
{
        //int level = 1;
        BiTree T = NULL;
    int sum = 0,e;
    initStack(&s);

        char path;
    int pathLength=0;

        CreateBiTree(&T);
        AllPath(T,path,pathLength);
        //PreOrderTraverse(T, level);
    while( IsEmpty(&s) ){
      Pop(&s, &e);
      //printf("sum = %d\n",sum);
      sum += e;
    }
        printf("sum = %d\n",sum);
        return 0;
}

秋木叶 发表于 2019-3-19 16:25:53

Croper 发表于 2019-3-18 18:00


谢谢啦！我自己用本办法解决了

秋木叶 发表于 2019-3-19 16:27:16

Croper 发表于 2019-3-18 17:10
。。伸手也不是这么伸手的啊，
你要求代码，至少把输入格式写出来啊。。你这输入格式是什么。。。。图片么 ...

sorry，当时考官就是这么简洁的问我的{:10_266:}
页: [1]
查看完整版本: 求从根节点到每一个叶子节点的路径的值的和