關於二叉搜索樹的兩個問題

我對二叉搜索樹有兩個問題 - 一個關於我正在編寫的代碼，另一個關於理論。首先，我在下面寫的代碼工作正常，除了當我試圖顯示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」作爲開頭，將這些單詞輸入到二叉樹中，那麼樹會不會因爲所有後續單詞在第一個按字母順序排列後出現令人難以置信的偏斜，從而始終是正確的孩子？我恐怕最終會得到一棵令人難以置信的不平衡的樹！當我填充它時，有什麼方法可以用來隨機播放樹嗎？

感謝您花時間閱讀本文！

來源

2011-04-06 A D

在您的display函數中，您首先需要測試root == null之前測試是否爲root -> word == null。這應該解決seg故障。

關於理論問題：答案是肯定的，這棵樹最終會變得難以置信地傾斜。這就是balanced binary trees的全部內容。

來源

2011-04-06 06:08:37

謝謝你的答案！我現在要讀的是:) – 2011-04-06 06:14:13

if(root -> word == NULL) 
    printf("Tree is empty.");

您的問題在於此。如果root本身爲空，會發生什麼？在解除引用之前請仔細檢查該指針。

是的，如果你按排序順序（或相對排序）插入項目，你會得到一個傾斜的樹。研究平衡二叉樹中節點的旋轉算法。

來源

2011-04-06 06:12:29 octal9

d'oh，再次擊敗 – octal9 2011-04-06 06:13:15

非常感謝！這解決了問題。我將嘗試閱讀平衡二叉樹和旋轉算法。 – 2011-04-06 06:15:17

關於你的第二個問題，其他人已經提到尋找平衡你的二叉樹。但是，作爲替代方案，如果已知輸入已排序，則更適合使用帶二進制搜索的線性數組來查找感興趣的項目，而不是二叉樹。排序數組的二進制搜索與平衡二叉樹搜索具有相同的時間複雜度。

來源

2011-04-06 06:17:56 caf

我沒有想到這一點。如果我想添加一個額外的元素到數組中，但是它不是按順序的 - 時間效率是否仍然相同？ – 2011-04-06 06:25:49

@Brittany：不，要使二進制搜索起作用，您必須按排序順序維護列表。 – caf 2011-04-06 06:39:34

關於二叉搜索樹的兩個問題

回答

相關問題