我無法找到使用遞回函式查找搜索二叉樹的最長路徑的代碼。
void maxDepth(bst_node *node)
{ ....
}
bst_node 是搜索二叉樹的節點。
退出遞回的條件很簡單：
if(node->leftChild==NULL&&node->rightChild==NULL)
{
return;
}
在遞回之前列印節點的值：
printf("%d ",node->value);
如果假設深度為 x 的節點只有一個左孩子，那么最長的路徑通過節點的左孩子，通過使用遞回，我們可以這樣寫：
if(node->rightChld==NULL)
{
maxDepth(node->leftChild);
}
如果深度為 x 的節點只有一個右孩子，那么最長的路徑通過節點的右孩子，通過使用遞回，我們可以這樣寫
if(node->leftChild==NULL)
{
maxDepth(node->rightChild);
}
但是如果節點有左右孩子怎么辦？我不明白我怎么能做到這一點。
例如，對于這個二叉搜索樹，輸出應該是：
“11 13 57 25 17”
幫助表示贊賞。
uj5u.com熱心網友回復：
#define max(a, b) a > b ? a : b
int max_left = 0
int max_right = 0;
if (node->rightChild != NULL) {
max_right = maxDepth(node->rightChild);
}
if (node->leftChild != NULL) {
mew_left = maxDepth(node->leftChild);
}
return max(max_left, max_right);
uj5u.com熱心網友回復：
訣竅是仔細考慮每種可能的情況。要么是基本情況，要么需要將其分解為可以通過遞回呼叫解決的較小問題。
int max(int a, int b) { return a > b ? a : b; }
int maxDepth(bst_node *node)
{
// If the tree is empty, the depth is zero.
if (!node) return 0;
// If the right subtree is empty, it's this node plus the max height of the left.
if (!node->rightChild) return 1 maxDepth(node->leftChild);
// ...and symmetrically if the left subtree is empty.
if (!node->leftChild) return 1 maxDepth(node->rightChild);
// Otherwise there are two children. It's this node plus the max.
return 1 max(maxDepth(node->leftChild), maxDepth(node->rightChild));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/379872.html
上一篇：使用指標的字符陣列未在C中更新
下一篇：C編程中讀帶空格的行并分割單詞