我有這個函式可以遍歷二叉搜索樹并將節點附加到串列中，如果它們在給定的下限和上限之間。
// n - the current node
// l - a list to accumulate results
static void doTreeSearchBetween(Tree t, Node n, Record lower,
Record upper, List l) {
// empty tree
if (n == NULL) {
return;
}
int cmpUpper = t->compare(n->rec, upper);
int cmpLower = t->compare(n->rec, lower);
// search left subtree
doTreeSearchBetween(t, n->left, lower, upper, l);
// if node if between lower and upper records append to list
if (cmpLower >= 0 && cmpUpper <= 0) {
ListAppend(l, n->rec);
}
// search right subtree
doTreeSearchBetween(t, n->right, lower, upper, l);
}
我意識到這段代碼的問題是它按順序遍歷整個串列，這使得它非常低效，我正在尋找一種允許我訪問盡可能少的節點的方法。邏輯不適合我，我想知道是否有人有任何想法？我嘗試在當前節點小于下限和大于上限時添加幾個 if 陳述句，這對我來說不起作用。
輸出示例：
Inserting: 11 13 17 19 23 29 31 37 41 43
Searching between 10 and 20
Search returned: 11 13 17 19
型別定義：
typedef struct node *Node;
struct node {
Record rec;
Node left;
Node right;
};
struct tree {
Node root;
int (*compare)(Record, Record);
};
struct list {
Record *items;
int numItems;
int maxItems;
};
struct record {
char familyName[MAX_FAMILY_NAME_LENGTH 1];
char givenName[MAX_GIVEN_NAME_LENGTH 1];
};
uj5u.com熱心網友回復：
您應該依靠比較來確定是否在左和/或右分支上遞回：
- 如果樹節點低于下限，則可以修剪其左子樹。
- 如果樹節點高于上限，則可以修剪其右子樹。
假設根節點處為空，則鏈表將按構造排序。
// n - the current node
// l - a list to accumulate results
static void doTreeSearchBetween(Tree t, Node n, Record lower,
Record upper, List l) {
// empty tree
if (n == NULL) {
return;
}
int cmpUpper = t->compare(n->rec, upper);
int cmpLower = t->compare(n->rec, lower);
if (cmpLower >= 0) {
// search left subtree
doTreeSearchBetween(t, n->left, lower, upper, l);
// if node if between lower and upper records append to list
if (cmpUpper <= 0) {
ListAppend(l, n->rec);
}
}
if (cmpUpper <= 0) {
// search right subtree
doTreeSearchBetween(t, n->right, lower, upper, l);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/512711.html
上一篇：使用指標計算字串的算術平均值