返回父節點的二進制樹C

Question

我想在C中實現遞歸函數，其中返回值是二叉樹中節點的父節點。作爲參數我有t，這是問題樹和字符n，節點的名稱。我想找到這個節點的父節點。我試圖做到這一點，但它沒有奏效。

Tree* 
tree_par (Tree* t, char n) 
{ 
    if (!tree_null(t)) 
    { 
     if (info(t->lft) || info(t->rgt) == n) 
      return t; 

     else 
     { 
      tree_par(t->lft, n); 
      tree_par(t->rgt, n); 
     } 
    } 
} 

如果樹空info返回節點的名稱和功能tree_null檢查功能。下面是樹形結構：

struct tree 
{ 
    struct tree *lft, *rgt; //left node and right node 
    char n; 
}; 

信息功能：

char 
info (Tree* t) 
{ 
    return t->n; 
} 

tree_null功能：

int 
tree_null (Tree* t) 
{ 
    return (t == NULL); 
} 

Answer 1

if (info(t->lft) || info(t->rgt) == n) 
      return t; 

這裏的問題。在||運營商的雙方是來自其他獨立的，所以這是不等於

if (info(t->lft) == n || info(t->rgt) == n) 

這是你想要的。

你必須把平等上試||

if (info(t->lft) == n || info(t->rgt) == n) 
      return t; 

編輯，也請注意，如果你這樣做

else 
     { 
      tree_par(t->lft, n); 
      tree_par(t->rgt, n); 
     } 

你實際上是放棄了遞歸的返回值的兩側函數調用，您需要更改它以檢查哪個遞歸調用（如果有的話）是成功的;另外，不要忘記爲空樹添加一個類似return NULL的東西，否則你會得到未定義的返回值。

這將是類似這樣的：

Tree* tree_par (Tree* t, char n) 
{ 
    if (!tree_null(t)) 
    { 
     if ((info(t->lft) == n) || (info(t->rgt) == n)) 
      return t; 
     else 
     { 
      Tree tt*; 
      tt=tree_par(t->lft, n); 
      if (tt==NULL) 
       tt= tree_par(t->rgt, n); 
      return tt; 
     } 
    } 
    else 
     return NULL; 
}