我想做的是比較兩個二叉搜索樹。這是為了計算它們發生的重復次數。
首先，我添加了這個在二叉搜索樹中查找特定元素的函式。
node *search(node **tree, char val)
{
if (!(*tree))
{
return NULL;
}
if (val < (*tree)->data)
{
search(&((*tree)->left), val);
}
else if (val > (*tree)->data)
{
search(&((*tree)->right), val);
}
else if (val == (*tree)->data)
{
return *tree;
}
}
然后我正在考慮遍歷其中一棵樹并與每個元素進行比較，但它不起作用。
int countRepetition(node *tree, node *secondTree)
{
node *tempCount;
tempCount = search(&secondTree, tree->data);
if (tempCount->data < tree->data)
{
countRepetition(tree->left, tempCount);
}
else if (tempCount->data > tree->data)
{
countRepetition(tree->right, tempCount);
}
else if (tempCount->data == tree->data)
{
return 1;
}
return 0;
}
例如，我期望的是：如果第一棵樹上有 a、b、c、d，第二棵樹上有 a、d、m、k，那么函式應該回傳 2。如果有人幫助我，我會很好，我快死了，因為我是 C 語言的新手。
這是整個代碼
#include <stdlib.h>
#include <stdio.h>
typedef struct bin_tree
{
char data;
struct bin_tree *right, *left;
} node;
void insert(node **tree, char val)
{
node *temp = NULL;
if (!(*tree))
{
temp = (node *)malloc(sizeof(node));
temp->left = temp->right = NULL;
temp->data = val;
*tree = temp;
return;
}
if (val < (*tree)->data)
{
insert(&(*tree)->left, val);
}
else if (val > (*tree)->data)
{
insert(&(*tree)->right, val);
}
}
node *search(node **tree, char val)
{
if (!(*tree))
{
return NULL;
}
if (val < (*tree)->data)
{
search(&((*tree)->left), val);
}
else if (val > (*tree)->data)
{
search(&((*tree)->right), val);
}
else if (val == (*tree)->data)
{
return *tree;
}
}
int countRepetition(node *tree, node *secondTree)
{
node *tempCount;
tempCount = search(&secondTree, tree->data);
if (tempCount->data < tree->data)
{
countRepetition(tree->left, tempCount);
}
else if (tempCount->data > tree->data)
{
countRepetition(tree->right, tempCount);
}
else if (tempCount->data == tree->data)
{
return 1;
}
return 0;
}
char main(char argc, char const *argv[])
{
node *root, *secondRoot;
node *tmp;
root = NULL;
/*Here i create the first tree*/
insert(&root, 'a');
insert(&root, 'b');
insert(&root, 'c');
insert(&root, 'd');
insert(&root, 'j');
insert(&root, 'k');
insert(&root, 'z');
//Here i create the second tree
insert(&secondRoot, 'p');
insert(&secondRoot, 'b');
insert(&secondRoot, 'f');
insert(&secondRoot, 'd');
insert(&secondRoot, 'g');
insert(&secondRoot, 'k');
insert(&secondRoot, 'h');
printf("\n%d\n", countRepetition(root, secondRoot));
return 0;
}
uj5u.com熱心網友回復：
一些問題：
的宣告
main是錯誤的。它應該是：int main(int argc, char const *argv[])secondRoot未初始化。它應該被初始化為NULLsearch進行遞回呼叫后不回傳值。它應該return是遞回呼叫的結果。search不需要指標-指標引數。由于它不會改變樹，讓它成為它的根，它只需要一個單指標引數。countRepetition應檢查是否tempCount為 NULL，以避免使用tempCount->data.鑒于
search要么回傳具有搜索值或NULL 的節點，因此測驗tempCount->data > tree->data并沒tempCount->data < tree->data有意義。這些永遠都不應該是真的。唯一的
return陳述句countRepetition回傳 0 或 1，所以這個函式不可能回傳另一個整數值。看起來你想實作一些二分搜索，但這意味著即使上述幾點被糾正，你也永遠不會訪問第一棵樹中的所有節點，所以你很可能會錯過一些匹配的值。
時間復雜度
您的想法似乎是訪問第一棵樹中的每個值，并為每個值在第二棵樹中執行搜索，然后計算匹配項。如果我們稱 ?? 為第一棵樹中的節點數，而 ?? 為第二棵樹中的節點數，那么這表示時間復雜度為 O(??log??)。
對于小樹，這很好，但如果 ?? 和 ?? 都很大，我們可以做得更好。我們可以按排序的順序（即中序遍歷）迭代第一棵樹中的值，同時對第二棵樹也這樣做。當它是當前訪問的兩個節點中較小的一個時，我們將轉到兩個遍歷之一中的下一個節點。這樣我們就可以“串聯”地穿過兩棵樹。由于訪問是按值排序的，因此我們一定會以這種方式找到相等的值。
該替代演算法表示時間復雜度 O(?? ??)。當 ?? 和 ?? 具有相同數量級時，這比第一個演算法提供的時間復雜度更好。
執行
我建議為按順序訪問節點創建一種迭代器，以便您可以隨時在遍歷中請求節點的后繼節點。為此，您需要一個堆疊（例如鏈表），以便知道哪些是當前節點的祖先仍需要訪問。
以下是該方面需要添加的代碼：
// Stack implementation
typedef struct node_list
{
struct bin_tree *node;
struct node_list *next;
} nodeList;
void pushFront(nodeList **head, node *newNode) {
nodeList *newHead = malloc(sizeof(nodeList));
newHead->node = newNode;
newHead->next = *head;
*head = newHead;
}
node *popFront(nodeList **head) {
nodeList *front = *head;
node *frontNode = front->node;
*head = front->next;
free(front);
return frontNode;
}
// Inorder tree iterator implementation
nodeList *treeIterator(node *root) {
if (root == NULL) return NULL;
nodeList *head = NULL;
pushFront(&head, root);
// Push path to left-most node (which has least value)
while (root->left != NULL) {
root = root->left;
pushFront(&head, root);
}
return head;
}
node *next(nodeList **head) {
if (*head == NULL) return NULL;
node *currentNode = popFront(head);
node *nextNode = currentNode;
if (nextNode->right != NULL) {
nextNode = nextNode->right;
pushFront(head, nextNode);
while (nextNode->left != NULL) {
nextNode = nextNode->left;
pushFront(head, nextNode);
}
}
return currentNode;
}
然后可以按如下方式實作實際演算法：
int countRepetition(node *tree, node *secondTree)
{
int count = 0;
nodeList *iterator1 = treeIterator(tree);
nodeList *iterator2 = treeIterator(secondTree);
node *node1 = next(&iterator1);
node *node2 = next(&iterator2);
while (node1 != NULL && node2 != NULL) {
if (node1->data < node2->data) {
node1 = next(&iterator1);
} else if (node1->data > node2->data) {
node2 = next(&iterator2);
} else {
count ;
node1 = next(&iterator1);
node2 = next(&iterator2);
}
}
return count;
}
這是該search功能的修復（見上面的評論）：
node *search(node *tree, char val)
{
if (tree == NULL)
{
return NULL;
}
if (val < tree->data)
{
return search(tree->left, val);
}
else if (val > tree->data)
{
return search(tree->right, val);
}
else if (val == tree->data)
{
return tree;
}
}
不要忘記在 中初始化secondTree = NULL，main并釋放你的樹使用的記憶體（我會留給你處理）。
uj5u.com熱心網友回復：
這里有一些重大錯誤
首先你的代碼沒有在這里初始化 root 和 secondRoot
node *root, *secondRoot;
應該
node* root = NULL, * secondRoot = NULL;
接下來這一行
tempCount = search(&secondTree, tree->data);
不檢查是否回傳 NULL ，所以下一行
if (tempCount->data < tree->data)
在這種情況下失敗。
請注意，不需要傳遞雙指標，這會使您的代碼非常難以閱讀。您只需要在實際分配根節點的插入位置上使用它。所有其他呼叫都不會更改傳入的樹指標。我會有一個'createTree'函式回傳一個空樹，然后插入不需要那個特殊情況代碼
但主要是 - 學習使用你的除錯器。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/486355.html