我正在應對這個挑戰：
撰寫一個函式來回傳樹
height(n, T)節點的高度。給定的是一個樹資料結構（使用兩個陣列）來存盤字符作為標簽和一些運算子。nT樹
T被編碼為一組兩個陣列，其中節點由這兩個陣列中的索引標識（具有相同的長度）。一個陣列保存節點的標簽，另一個陣列將父參考作為索引。-1 的父參考意味著節點是根。
我嘗試了幾件事，但無法解決這個問題。在某些情況下，該height函式會回傳正確的答案，但在其他情況下則不會
我的 C 代碼：
int height(Node n, Tree *pT){
// if invalid
if ( n < 0 || n> pT->maxNode) return -1;
if ( leftmostChild(n, pT) == NULL_NODE && rightSibling(leftmostChild(n,pT),pT) == NULL_NODE) return 0;
//find
int L = height(leftmostChild(n, pT), pT);
int R = height(rightSibling(leftmostChild(n, pT),pT), pT);
if ( L > R) return L 1;
return R 1;
}
這是完整的代碼：
#include<stdio.h>
#define MAXLENGTH 100
#define NULL_NODE -1
typedef int Node;
typedef char LabelType;
typedef struct {
Node P[MAXLENGTH];
LabelType L[MAXLENGTH];
int maxNode;
} Tree;
Node leftmostChild(Node n, Tree *pT){
if ( n < 0 || n > pT->maxNode) return NULL_NODE;
for ( Node i = n 1; i <= pT->maxNode; i ){
if ( pT->P[i] == n ) return i;
}
return NULL_NODE;
}
Node rightSibling(Node n, Tree *pT){
if ( n < 0 || n > pT->maxNode) return NULL_NODE;
for ( Node i = n 1; i <= pT->maxNode; i ){
if ( pT->P[i] == pT->P[n] ) return i;
}
return NULL_NODE;
}
int height(Node n, Tree *pT){
if ( n < 0 || n>pT->maxNode) return -1;
if ( leftmostChild(n, pT) == NULL_NODE && rightSibling(leftmostChild(n,pT),pT) == NULL_NODE) return 0;
int L = height(leftmostChild(n,pT), pT);
int R = height(rightSibling(leftmostChild(n,pT),pT), pT);
if ( L > R) return L 1;
return R 1;
}
int main(){
Tree T = { {-1, 0, 0, 0, 0, 0, 3, 6, 2, 5, 1, 10, 9, 4, 7, 5},
{'S', 'L', 'K', 'J', 'A', 'V', 'R', 'E', 'F', 'T', 'C', 'X', 'U', 'I', 'H', 'D'}, 15};
for (int i = 0; i <= T.maxNode; i )
printf("height(%d) = %d\n", i, height(i, &T));
}
}
預期輸出：
height(0) = 4
height(1) = 2
height(2) = 1
height(3) = 3
height(4) = 1
height(5) = 2
height(6) = 2
height(7) = 1
height(8) = 0
height(9) = 1
height(10) = 1
height(11) = 0
height(12) = 0
height(13) = 0
height(14) = 0
height(15) = 0
當前，錯誤的輸出：
height(0) = 3
height(1) = 2
height(2) = 1
height(3) = 3
height(4) = 1
height(5) = 2
height(6) = 2
height(7) = 1
height(8) = 0
height(9) = 1
height(10) = 1
height(11) = 0
height(12) = 0
height(13) = 0
height(14) = 0
height(15) = 0
您還可以看到它在ideone上運行。
uj5u.com熱心網友回復：
您的功能存在一些問題height：
在第二個
if陳述句中，如果第一個條件為真，那么您根本不需要呼叫rightSibling，但當它為真時無論如何回傳 0。另外，當第一個條件不成立時，是否有右兄弟也無關緊要，回傳值肯定不應該為0。您的代碼期望樹是二叉樹，但這不能保證。一個節點可以有兩個以上的子節點，因此您需要迭代所有兄弟節點。為此，您可以使用
for回圈。
修正版：
int height(Node n, Tree *pT){
if ( n < 0 || n>pT->maxNode) return -1;
int h = -1;
for (int child = leftmostChild(n, pT); child != NULL_NODE; child = rightSibling(child, pT)) {
int childHeight = height(child, pT);
h = h < childHeight ? childHeight : h;
}
return h 1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/515762.html
標籤：C递归数据结构