使用C語(yǔ)言求二叉樹(shù)結(jié)點(diǎn)的最低公共祖先的方法
算法分析
我們直接來(lái)分析O(n)的算法。
比如求節(jié)點(diǎn)F和節(jié)點(diǎn)H的最低公共祖先,先求出從根節(jié)點(diǎn)A到F的路徑,再求出A到H的路徑,那么最后一個(gè)相同的節(jié)點(diǎn)就是最低公共祖先。A->B->D->F和A->B->E->H,最后相同的節(jié)點(diǎn)事B,所以最低公共祖先是B節(jié)點(diǎn)。求根節(jié)點(diǎn)到指定節(jié)點(diǎn)的算法先前已經(jīng)更新過(guò)了,復(fù)雜度是O(n),所以總的時(shí)間復(fù)雜度是O(n)。
條件細(xì)化:
(1)樹(shù)如果是二叉樹(shù),而且是二叉排序樹(shù)。
             這中條件下可以使用二叉排序樹(shù)的搜索功能找到最低公共祖先。
(2)樹(shù)不是二叉排序樹(shù),連二叉樹(shù)都不是,就是普通的樹(shù)。
      1,如果樹(shù)中有指向父節(jié)點(diǎn)的指針。
              這問(wèn)題可以將問(wèn)題轉(zhuǎn)化為兩個(gè)鏈表相交,求兩個(gè)鏈表的第一個(gè)交點(diǎn)。
      2,如果樹(shù)中沒(méi)有指向父節(jié)點(diǎn)的指針。
              這問(wèn)題就有點(diǎn)麻煩了。
       
       
具體來(lái)看獲取從根節(jié)點(diǎn)到指定節(jié)點(diǎn)的函數(shù)代碼:
struct BinaryNode
{
 char value;
 BinaryNode *left;
 BinaryNode *right;
};
求跟節(jié)點(diǎn)到指定節(jié)點(diǎn)路徑:
bool GetNodePath(BinaryNode *pRoot,BinaryNode *pNode,vector<BinaryNode*> &v)
{
 if(pRoot==NULL)
  return false;
 v.push_back(pRoot);
 if(pRoot==pNode)
  return true;
 bool found=GetNodePath(pRoot->left,pNode,v);
 if(!found)
  found=GetNodePath(pRoot->right,pNode,v);
 if(!found)
  v.pop_back();
}
求最低公共祖先節(jié)點(diǎn):
BinaryNode* GetCommonParent(BinaryNode *pRoot,BinaryNode *pNode1,BinaryNode *pNode2)
{
 if(pRoot==NULL || pNode1==NULL || pNode2==NULL)
  return NULL;
 vector<BinaryNode*> v1,v2;
 GetNodePath(pRoot,pNode1,v1);
 GetNodePath(pRoot,pNode2,v2);
 BinaryNode *pLast=pRoot;
 vector<BinaryNode*>::iterator ite1=v1.begin();
 vector<BinaryNode*>::iterator ite2=v2.begin();
 while(ite1!=v1.end() && ite2!=v2.end())
 {
  if(*ite1==*ite2)
   pLast=*ite1;
  ite1++;
  ite2++;
 }
 return pLast;
}
來(lái)看一道具體的ACM題目
    題目描述:  
    給定一棵樹(shù),同時(shí)給出樹(shù)中的兩個(gè)結(jié)點(diǎn),求它們的最低公共祖先。
    輸入:  
    輸入可能包含多個(gè)測(cè)試樣例。  
    對(duì)于每個(gè)測(cè)試案例,輸入的第一行為一個(gè)數(shù)n(0<n<1000),代表測(cè)試樣例的個(gè)數(shù)。  
    其中每個(gè)測(cè)試樣例包括兩行,第一行為一個(gè)二叉樹(shù)的先序遍歷序列,其中左右子樹(shù)若為空則用0代替,其中二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)node_num<10000。  
    第二行為樹(shù)中的兩個(gè)結(jié)點(diǎn)的值m1與m2(0<m1,m2<10000)。  
    輸出:  
    對(duì)應(yīng)每個(gè)測(cè)試案例,  
    輸出給定的樹(shù)中兩個(gè)結(jié)點(diǎn)的最低公共祖先結(jié)點(diǎn)的值,若兩個(gè)給定結(jié)點(diǎn)無(wú)最低公共祖先,則輸出“My God”。  
    樣例輸入:  
    2  
    1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0  
    6 8  
    1 2 4 6 0 0 7 0 0 5 8 0 0 9 0 0 3 0 0  
    6 12  
    樣例輸出:  
    2  
    My God 
思路
這道題我考慮的思路是
(1)后序遍歷的思想,用棧保存到查找點(diǎn)的路徑
(2)然后求兩個(gè)棧第一個(gè)公共節(jié)點(diǎn)
AC代碼
  #include <stdio.h> 
  #include <stdlib.h> 
    
  #define N 7000 
    
  typedef struct btree { 
    struct btree *lchild, *rchild; 
    int data; 
  } btree; 
    
  typedef struct stack { 
    int top; 
    btree* data[N]; 
  } stack; 
    
  stack *first, *second; 
  int oneflag, secflag; 
    
  /** 
   * 根據(jù)前序序列遞歸構(gòu)建二叉樹(shù) 
   */ 
  void createBtree(btree **t) 
  { 
    int data; 
    scanf("%d", &data); 
    
    if (data == 0) { 
      *t = NULL; 
    } else { 
      *t = (btree *)malloc(sizeof(btree)); 
      (*t)->data = data; 
      createBtree(&(*t)->lchild); 
      createBtree(&(*t)->rchild); 
    } 
  } 
    
  /** 
   * 后序遍歷二叉樹(shù),構(gòu)造遍歷棧 
   */ 
  void postTraverse(btree *t, stack *s, int srcnum, int *flag) 
  { 
    if (t != NULL) { 
      btree *pre; 
      pre = NULL; 
    
      s->data[s->top ++] = t; 
      while (s->top > 0 || t) { 
        if (t) { 
          s->data[s->top ++] = t; 
          if (t->data == srcnum) { 
            *flag = 1; 
            break; 
          } 
          t = t->lchild; 
        } else { 
          t = s->data[-- s->top]; 
          if (t->rchild == NULL || t->rchild == pre) { 
            pre = t; 
            t = NULL; 
          } else { 
            s->data[s->top ++] = t; 
            t = t->rchild; 
          } 
        } 
      } 
    } 
  } 
    
  /** 
   * 查找兩個(gè)棧第一個(gè)公共元素 
   * 
   * T = O(n) 
   * 
   */ 
  void stackCommonData(stack *f, stack *s) 
  { 
    int top, data, flag; 
    
    top = (f->top > s->top) ? s->top : f->top; 
    
    while (top > 0) { 
      if (f->data[top - 1]->data == s->data[top - 1]->data) { 
        data = f->data[top - 1]->data; 
        flag = 1; 
        break; 
      } else { 
        top --; 
      } 
    } 
    
    if (flag) { 
      printf("%d\n", data); 
    } else { 
      printf("My God\n"); 
    } 
  } 
    
  /** 
   * 清理二叉樹(shù) 
   * 
   */ 
  void cleanBtree(btree *t) 
  { 
    if (t) { 
      cleanBtree(t->lchild); 
      cleanBtree(t->rchild); 
      free(t); 
    } 
  } 
    
    
  int main(void) 
  { 
    int n, sf, se; 
    btree *t; 
    
    scanf("%d", &n); 
    while (n --) { 
      createBtree(&t); 
      scanf("%d %d", &sf, &se); 
        
      first = (stack *)malloc(sizeof(stack)); 
      first->top = 0; 
      oneflag = 0; 
      postTraverse(t, first, sf, &oneflag); 
    
      second = (stack *)malloc(sizeof(stack)); 
      second->top = 0; 
      secflag = 0; 
      postTraverse(t, second, se, &secflag); 
    
      if (oneflag == 0 || secflag == 0 || first->top == 0 || second->top == 0) { 
        printf("My God\n"); 
        cleanBtree(t); 
        continue; 
      } else { 
        stackCommonData(first, second); 
        cleanBtree(t); 
      } 
    } 
    return 0; 
  } 
    /************************************************************** 
        Problem: 1509 
        User: wangzhengyi 
        Language: C 
        Result: Accepted 
        Time:150 ms 
        Memory:110212 kb 
    ****************************************************************/  
欄 目:C語(yǔ)言
下一篇:淺談2路插入排序算法及其簡(jiǎn)單實(shí)現(xiàn)
本文標(biāo)題:使用C語(yǔ)言求二叉樹(shù)結(jié)點(diǎn)的最低公共祖先的方法
本文地址:http://www.jygsgssxh.com/a1/Cyuyan/2878.html
您可能感興趣的文章
- 04-02c語(yǔ)言函數(shù)調(diào)用后清空內(nèi)存 c語(yǔ)言調(diào)用函數(shù)刪除字符
 - 04-02c語(yǔ)言的正則匹配函數(shù) c語(yǔ)言正則表達(dá)式函數(shù)庫(kù)
 - 04-02func函數(shù)+在C語(yǔ)言 func函數(shù)在c語(yǔ)言中
 - 04-02c語(yǔ)言中對(duì)數(shù)函數(shù)的表達(dá)式 c語(yǔ)言中對(duì)數(shù)怎么表達(dá)
 - 04-02c語(yǔ)言用函數(shù)寫(xiě)分段 用c語(yǔ)言表示分段函數(shù)
 - 04-02c語(yǔ)言編寫(xiě)函數(shù)冒泡排序 c語(yǔ)言冒泡排序法函數(shù)
 - 04-02c語(yǔ)言沒(méi)有round函數(shù) round c語(yǔ)言
 - 04-02c語(yǔ)言分段函數(shù)怎么求 用c語(yǔ)言求分段函數(shù)
 - 04-02C語(yǔ)言中怎么打出三角函數(shù) c語(yǔ)言中怎么打出三角函數(shù)的值
 - 04-02c語(yǔ)言調(diào)用函數(shù)求fibo C語(yǔ)言調(diào)用函數(shù)求階乘
 


閱讀排行
- 1C語(yǔ)言 while語(yǔ)句的用法詳解
 - 2java 實(shí)現(xiàn)簡(jiǎn)單圣誕樹(shù)的示例代碼(圣誕
 - 3利用C語(yǔ)言實(shí)現(xiàn)“百馬百擔(dān)”問(wèn)題方法
 - 4C語(yǔ)言中計(jì)算正弦的相關(guān)函數(shù)總結(jié)
 - 5c語(yǔ)言計(jì)算三角形面積代碼
 - 6什么是 WSH(腳本宿主)的詳細(xì)解釋
 - 7C++ 中隨機(jī)函數(shù)random函數(shù)的使用方法
 - 8正則表達(dá)式匹配各種特殊字符
 - 9C語(yǔ)言十進(jìn)制轉(zhuǎn)二進(jìn)制代碼實(shí)例
 - 10C語(yǔ)言查找數(shù)組里數(shù)字重復(fù)次數(shù)的方法
 
本欄相關(guān)
- 04-02c語(yǔ)言函數(shù)調(diào)用后清空內(nèi)存 c語(yǔ)言調(diào)用
 - 04-02func函數(shù)+在C語(yǔ)言 func函數(shù)在c語(yǔ)言中
 - 04-02c語(yǔ)言的正則匹配函數(shù) c語(yǔ)言正則表達(dá)
 - 04-02c語(yǔ)言用函數(shù)寫(xiě)分段 用c語(yǔ)言表示分段
 - 04-02c語(yǔ)言中對(duì)數(shù)函數(shù)的表達(dá)式 c語(yǔ)言中對(duì)
 - 04-02c語(yǔ)言編寫(xiě)函數(shù)冒泡排序 c語(yǔ)言冒泡排
 - 04-02c語(yǔ)言沒(méi)有round函數(shù) round c語(yǔ)言
 - 04-02c語(yǔ)言分段函數(shù)怎么求 用c語(yǔ)言求分段
 - 04-02C語(yǔ)言中怎么打出三角函數(shù) c語(yǔ)言中怎
 - 04-02c語(yǔ)言調(diào)用函數(shù)求fibo C語(yǔ)言調(diào)用函數(shù)求
 
隨機(jī)閱讀
- 04-02jquery與jsp,用jquery
 - 08-05dedecms(織夢(mèng))副欄目數(shù)量限制代碼修改
 - 08-05DEDE織夢(mèng)data目錄下的sessions文件夾有什
 - 08-05織夢(mèng)dedecms什么時(shí)候用欄目交叉功能?
 - 01-11Mac OSX 打開(kāi)原生自帶讀寫(xiě)NTFS功能(圖文
 - 01-10SublimeText編譯C開(kāi)發(fā)環(huán)境設(shè)置
 - 01-10C#中split用法實(shí)例總結(jié)
 - 01-11ajax實(shí)現(xiàn)頁(yè)面的局部加載
 - 01-10delphi制作wav文件的方法
 - 01-10使用C語(yǔ)言求解撲克牌的順子及n個(gè)骰子
 


