我在 C 中有一個二叉搜索樹，目前的目標是找到樹中的第 N 個元素。我正在嘗試遞回地執行此操作，但這不是最重要的。我可以訪問任何給定節點（含）下的節點數量。
我試過這段代碼：
TreeNode* findNthElement(int N, TreeNode* tree) {
static int count = 0;
printf("nodeCount: %d\nN: %d\nCount: %d\n", tree->nodeCount, N, count);//debug
//null case
if (tree == NULL) {
return NULL;
}
//recursion
if (count <= N) {
findNthElement(N, tree->left);
count ;
if (count == N) {
count = 0;
return tree;
}
findNthElement(N, tree->right);
}
}
這應該是一個遞回函式來完成我的任務，但count它的值始終為 0，即使它是靜態的。我還嘗試在函式外部初始化計數，并在成功或失敗時將其重置為 0，但這也沒有成功。
uj5u.com熱心網友回復：
您的代碼忽略了從遞回呼叫回傳的節點，因此如果該遞回呼叫找到了目標節點，呼叫者將不知道它。而且，findNthElement(N, tree->right)呼叫之后，什么也沒有回傳。
此外，您不應使用靜態計數。可以通過減少將作為 N 引數傳遞給遞回呼叫的值來滿足計數邏輯。
這是一個實作：
TreeNode* findNthElement(int n, TreeNode* tree) {
if (tree == NULL) {
return NULL;
}
int currentNum = tree->left == NULL ? 1 : tree->left->nodeCount 1;
return n == currentNum ? tree // Found it!
: n < currentNum ? findNthElement(n, tree->left)
: findNthElement(n - currentNum, tree->right);
}
uj5u.com熱心網友回復：
這段代碼超出了我的知識范圍，但可能count 需要在遞回之前進行？因為您在不增加代碼計數的情況下呼叫遞回。例子：
if (count <= N) {
count ;
findNthElement(N, tree->left);
uj5u.com熱心網友回復：
您根本不必將 count 定義為靜態，您可以直接遞增引數并遞回呼叫直到 N == count。每當您呼叫該函式時，即使是遞回呼叫，也會在記憶體堆疊中創建一個新的計數變數。
TreeNode* findNthElement(int N, TreeNode* tree, int count) {
TreeNode * nthTree = NULL;
if(tree == NULL)
return NULL;
//Found the Nth element
if (count == N){
return tree;
}
//Not using count just for clarity
//First it will check left subtree, if its Nth then return it else go right
nthTree = findNthElement(N, tree->left, count 1); //Recursive call for left node
//Recursive call for right node
return (nthTree == NULL) ? findNthElement(N, tree->right, count 1) : nthTree;
}
uj5u.com熱心網友回復：
為了找到 BST 中第 n 個最小的元素，您可以應用如下邏輯：
using System.Collections.Generic;
public int smallElement(int k)
{
Node<T> node = Root;
int count = k;
int sizeOfSubTree =0;
while (node != null)
{
sizeOfSubTree = node.SizeOfLeftSubTree();
if(sizeOfSubTree 1 == count)
{
return node.Value;
}
else if(sizeOfSubTree 1 < count)
{
node=node.Right;
count -= sizeOfSubTree 1 ;
}
else
{
node = node.Right;
}
}
return -1;
}
您還可以查看以下資源以獲得幫助：
中序遍歷找到第n個節點
在二叉搜索樹 (BST) 中找到第 k 個最小節點
希望這對你有幫助。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/535801.html
標籤：C递归数据结构二叉搜索树
上一篇：如何在新視窗而不是默認彈出視窗中打開Chrome擴展程式？
下一篇：如何從嵌套結構中獲取子孫串列？