在二叉树中找到最大的按字典顺序排列的根到叶子路径

Question

我必须创建二叉树，其中节点存储char值。任务是找到由这些字符创建的最大的按字典顺序排列的根到叶子路径。

给定的输入应该是一个字符串，其中第一个char是要存储的值，在空格之后有一些提示存储它的节点。 L表示左侧节点，R当然是右侧节点。输出应该是一个找到的字符串和输入中给出的字符数（不是空格）。

这是我的代码。我很确定错误在rootToLeafPath（）中，因为我已经检查了创建树的方法。如果你想查看所有路径，我也会给你打印方法。

#include <stdio.h>
#include <iostream>
#include <string.h>
int allCharCounter = 0;
char oldest_word[65];

struct Tree_node{
    struct Tree_node *right;
    struct Tree_node *left;
    char value;
};

Tree_node* getTree(struct Tree_node* root){
    char c = getchar();
    char edge = c;
    Tree_node* korzen = new Tree_node();
    if(root == NULL){
        root = new Tree_node(); 
    }
    korzen = root;
    while(!feof(stdin)){
        c = getchar();
        if(c == 82){//R
            allCharCounter++;
            if(root->right == NULL){
                root->right = new Tree_node();
            }
            root = root->right;
        }else if(c == 76){//L
            allCharCounter++;
            if(root->left == NULL){
                root->left = new Tree_node();
            }
            root = root->left;
        }else if(c > 96 && c < 123){
            allCharCounter++;
            root->value = edge;
            root = korzen;      
            edge = c;
        } 
    }
    root->value = edge;
    root = korzen; 
    return root;
}

void printPath(char *path, int length){
    int i;
    for(i = 0; i <= length; i++){
        printf("%c ", path[i]);
    }
    printf("\n");
}

void rootToLeafPath(struct Tree_node *nodeptr, char *current_path, int index){

    if(nodeptr != NULL){
        current_path[index] = nodeptr->value;
        if(nodeptr->left == NULL && nodeptr->right == NULL){
            if(strcmp(oldest_word,current_path)< 0){
                //memset(oldest_word,0,sizeof(oldest_word));
                strncpy(oldest_word, current_path, 65);
            }
            //printPath(current_path, index);
        }
        rootToLeafPath(nodeptr->left, current_path,index+1);
        rootToLeafPath(nodeptr->right, current_path,index+1);
    }
}



int main(){
    struct Tree_node* root = NULL;
    struct Tree_node* test = NULL;
    root = getTree(root);
    char current_path [65] ={};
    rootToLeafPath(root, current_path,0);
    std::cout<< oldest_word;
    fprintf(stdout,"\n%d", allCharCounter+1); //-> ok
}

所以输入：

s LR

来自LRR

m RR

p LRLRL

至

在LRL

一个LL

t L

h R

j LRLR

LRRR

输出应该是：

结缔组织

38

但我的代码创建：

ktszap

38

我想也许我需要在给它一个新值之前清除oldest_word，但是没有用。对我来说，它似乎记得以前的更长的价值。在这个例子中，'ktswjp'是之前的数组中的单词，但后来发现了新的'ktsza'，但'p'仍然存在。

感谢任何帮助。

Answer 1

在rootToLeafPath中，您为current_path[index] = nodeptr->value;指定一个值以存储下一个字符。当你完成那个角色时，你不会清除它，所以它会留在缓冲区中，导致它出现在应该更短的字符串的末尾。

解决方法是在返回之前将其重置为nul字符

current_path[index] = '\0';

在你完成对rootToLeafPath的递归调用之后。