c - 关于二叉搜索树的两个问题

Question

我有两个关于二叉搜索树的问题 - 一个关于我正在编写的代码，另一个更多关于理论。首先，我在下面编写的代码工作正常，除了当我尝试显示 BST 实际上为空的情况时；当我希望它打印出一条错误消息时，它给了我一个段错误。我觉得我可能在某个时候混淆了我的指示，所以这给了我错误。这是我的代码:

#include <stdio.h>
#include <stdlib.h>

struct Node {
char *word;
struct Node *left;
struct Node *right;
};

/* Function that creates a new node as a leaf; that is, its     */
/* left and right children are NULL.                */
/* Require: node -> word != NULL                    */
struct Node * createNode (char *word) {
struct Node *item = malloc(sizeof(struct Node));
item -> word = word;
item -> left = NULL;
item -> right = NULL;
return item;
}

/* Recursive function that inserts a node into proper position by   */
/* searching through    tree.                   */
struct Node * insertNode (struct Node *root, char *word) {
// If tree is empty, node becomes root
if(root == NULL)
    return createNode(word);
else {

    if(strcmp(word, root -> word) < 0) {
        root -> left = insertNode(root -> left, word);
        return root;
    } else if(strcmp(word, root -> word) > 0) {
        root -> right = insertNode(root -> right, word);
        return root;
    } else if(strcmp(word, root -> word) == 0)
        printf("Word is already present in the tree.");
}
}

/* Function to display Binary Search Tree via inorder traversal.    */
/*  -- prints entire left subtree, then root, then right subtree    */
void display (struct Node *root) {
if(root -> word == NULL)
    printf("Tree is empty.");
if(root -> left != NULL)
    display(root -> left);
printf("%s\n", root -> word);
if(root -> right != NULL)
    display(root -> right);
}

void main () {
struct Node root;
struct Node *rootP = &root;
root = createNode("
}

第二个问题涉及填充二叉树。我想使用一本小词典，当然它会按字母顺序排列。如果我将这些单词输入以“aardvark”开头的二叉树中，树会不会最终变得难以置信地倾斜，因为所有后续单词都将按字母顺序排在第一个单词之后，因此总是正确的 child ？我担心我最终会得到一棵非常不平衡的树!有什么方法可以在我填充树时将其随机播放吗？

感谢您花时间阅读本文!

Answer 1

在您的display 函数中，您首先需要在测试root -> word == null 之前测试是否root == null。这应该可以解决段错误。

关于理论问题:答案是肯定的，这棵树最终会非常倾斜。这就是balanced binary trees都是关于。