c++ - 在二叉树中找到最大的字典序根到叶路径

Question

我必须创建二叉树，其中节点存储一个 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

z LRR

m RR

p LRLRL

k

w LRL

a LL

t L

h R

j LRLR

a LRRR

输出应该是:

ktsza

38

但是我的代码创建了:

ktszap

38

我想也许我需要在给它一个新值之前清除 oldest_word，但是没有用。对我来说，它似乎记得以前更长的值(value)。在此示例中，'ktswjp' 是之前数组中的单词，但后来它找到了新的单词 'ktsza'，但 'p' 保留了下来。

感谢任何帮助。

Answer 1

在 rootToLeafPath 中，您将值分配给 current_path[index] = nodeptr->value; 以存储下一个字符。当您处理完该字符后，您不会将其清除，因此它会保留在缓冲区中，导致它出现在应该更短的字符串末尾。

解决方案是在返回前将其重置为空字符，用

current_path[index] = '\0';

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