posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          LCA 最近公共祖先問題 (1)

          Posted on 2007-07-14 10:57 ZelluX 閱讀(2830) 評論(2)  編輯  收藏 所屬分類: Algorithm
          LCA (Lowest Common Ancestor)
          一篇轉(zhuǎn)載的文章,是對于二叉搜索樹的算法
          http://blog.csdn.net/AmiRural/archive/2006/06/07/777966.aspx

          [題目]:已知二元搜索樹(Binary Search Tree)上兩個結(jié)點的值,請找出它們的公共祖先。你可以假設(shè)這兩個值肯定存在。這個函數(shù)的調(diào)用接口如下所示:
                int FindLowestCommonAncestor(node *root, int value1, int value2);

              根據(jù)樹的存儲結(jié)構(gòu),我們可以立刻得到一個這樣的算法:從兩個給定的結(jié)點出發(fā)回溯,兩條回溯路線的交點就是我們要找的東西。這個算法的具體實現(xiàn)辦法是:從根 結(jié)點開始,先用這兩個結(jié)點的全體祖先分別生成兩個鏈表,再把這兩個鏈表第一次出現(xiàn)不同結(jié)點的位置找出來,則它們的前一個結(jié)點就是我們要找的東西。
              這個算法倒沒有什么不好的地方,但是它沒有利用二元搜索樹的任何特征,其他類型的樹也可以用這個算法來處理。二元搜索樹中左結(jié)點的值永遠(yuǎn)小于或者等于當(dāng)前 結(jié)點的值,而右結(jié)點的值永遠(yuǎn)大于或者等于當(dāng)前結(jié)點的值。仔細(xì)研究,4和14的最低公共祖先是8,它與4和14的其他公共祖先是有重要區(qū)別的:其他的公共祖 先或者同時大于4和4,或者同時小于4和14,只有8介于4和14之間。利用這一研究成果,我們就能得到一個更好的算法。
              從根結(jié)點出發(fā),沿著兩個給定結(jié)點的公共祖先前進(jìn)。當(dāng)這兩個結(jié)點的值同時小于當(dāng)前結(jié)點的值時,沿當(dāng)前結(jié)點的左指針前進(jìn);當(dāng)這兩個結(jié)點的值同時大于當(dāng)前結(jié)點的 值時,沿當(dāng)前結(jié)點的右指針前進(jìn);當(dāng)?shù)谝淮斡龅疆?dāng)前結(jié)點的值介于兩個給定的結(jié)點值之間的情況時,這個當(dāng)前結(jié)點就是我們要找的最的最低公共祖先了。
              這是一道與樹有關(guān)的試題,算法也有遞歸的味道,用遞歸來實現(xiàn)這一解決方案似乎是順理成章的事,可這里沒有這個必要。遞歸技術(shù)特別適合于對樹的多個層次進(jìn)行 遍歷或者需要尋找某個特殊結(jié)點的場合。這道題只是沿著樹結(jié)點逐層向下前進(jìn),用循環(huán)語句來實現(xiàn)有關(guān)的過程將更簡單明了。

               int FindLowestCommonAncestor(node *root, int value1, int value2)
               {
                node 
          *curnode = root;
                
          while(1)
                   {
                     
          if (curnode->data>value1&&curnode->data>value2)
                       curnode 
          = curnode->left;
                     
          else if(curnode->data<value1&&curnode->data<value2)
                       curnode 
          = curnode->right;
                     
          else
                       
          return curnode->data;
                    }
                }

          C語言實現(xiàn):

          /*二叉排序樹的生成及樹,任意兩結(jié)點的最低公共祖先        Amirural設(shè)計*/
          #include 
          <stdio.h>
          #define  null  0

          int counter=0;
          typedef 
          struct btreenode
          {
          int data;
           
          struct btreenode *lchild;
           
          struct btreenode *rchild;
          }bnode;

          bnode 
          *creat(int x,bnode *lbt,bnode *rbt)   //生成一棵以x為結(jié)點,以lbt和rbt為左右子樹的二叉樹
          {bnode *p;
           p
          =(bnode*)malloc(sizeof(bnode));
           p
          ->data=x;
           p
          ->lchild=lbt;
           p
          ->rchild=rbt;
           
          return(p);
          }

          bnode 
          *ins_lchild(bnode *p, int x)    //x作為左孩子插到二叉樹中
          {bnode *q;
          if(p==null)
            printf(
          "Illegal insert.");
          else
           {q
          =(bnode*)malloc(sizeof(bnode));
            q
          ->data=x;
            q
          ->lchild=null;
            q
          ->rchild=null;
            
          if(p->lchild!=null)                //若p有左孩子,則將原來的左孩子作為結(jié)點x的右孩子
               q->rchild=p->lchild;
            p
          ->lchild=q;
           }
           
          return(p);
          }

          bnode 
          *ins_rchild(bnode *p, int x)   //x作為右孩子插入到二叉樹
          {bnode *q;
           
          if(p==null)
              printf(
          "Illegal insert.");
           
          else
           {q
          =(bnode*)malloc(sizeof(bnode));
            q
          ->data=x;
            q
          ->lchild=null;
            q
          ->rchild=null;
            
          if(p->rchild!=null)                //若x有右孩子,則將原來的右孩子作為結(jié)點x的的左孩子
               q->lchild=p->rchild;
            p
          ->rchild=q;
           }
            
          return(p);
          }

          void prorder(bnode *p)
          {
          if(p==null)
             
          return;
           printf(
          "%d\t%u\t%d\t%u\t%u\n",++counter,p,p->data,p->lchild,p->rchild);
           
          if(p->lchild!=null)
             prorder(p
          ->lchild);
           
          if(p->rchild!=null)
             prorder(p
          ->rchild);
          }

          void print(bnode *p)                //嵌套括號表示二叉樹,輸出左子樹前打印左括號,
          {                                   //輸出右子樹后打印右括號。
            if(p!=null)
            {printf(
          "%d",p->data);
             
          if(p->lchild!=null||p->rchild!=null)
             {printf(
          "(");
            print(p
          ->lchild);
            
          if(p->rchild!=null)
             printf(
          ",");
            print(p
          ->rchild);
            printf(
          ")");
           }
          }
          }

          int FindLowestCommonAncestor(bnode *root, int value1, int value2)
          {
            bnode 
          *curnode = root;
            
          while(1)
            {
             
          if (curnode->data>value1&&curnode->data>value2)
                 curnode 
          = curnode->lchild;
             
          else if(curnode->data<value1&&curnode->data<value2)
                 curnode 
          = curnode->rchild;
             
          else
                 
          return curnode->data;
             }
          }

           
          main()
          {
           bnode 
          *bt,*p,*q;
           
          int x,y,v1,v2;
           printf(
          "輸入根結(jié)點:");
           scanf(
          "%d",&x);
           p
          =creat(x,null,null);
           bt
          =p;                                   //使bt p都指向根結(jié)點
           printf("輸入新的結(jié)點值:");
           scanf(
          "%d",&x);
           
          while(x!=-1)
             {p
          =bt;
              q
          =p;                    
           
          while(x!=p->data&&q!=null)              //q記錄當(dāng)前根結(jié)點
             {p=q;
              
          if(x<p->data)
              q
          =p->lchild;
              
          else
              q
          =p->rchild;
             }
            
          if(x==p->data)
            {printf(
          "元素%d已經(jīng)插入二叉樹中!\n",x);
            }
            
          else
             
          if(x<p->data)    ins_lchild(p,x);
                
          else             ins_rchild(p,x);
             scanf(
          "%d",&x);
             }
           p
          =bt;
           printf(
          "struct of the binary tree:\n");
           printf(
          "number\taddress\tdata\tlchild\trchild\n");
           prorder(p);
           printf(
          "\n");
           printf(
          "用括號形式輸出二叉樹:");
           print(p);

           printf(
          "\n請任意輸入樹中存在的兩個結(jié)點:");
           scanf(
          "%d,%d",&v1,&v2);
           y 
          = FindLowestCommonAncestor(p, v1, v2);
           printf(
          "輸出%d和%d的最低公共祖先:",v1,v2);
           printf(
          "%d\n",y);
          }

           

           運(yùn)行結(jié)果:
          輸入根結(jié)點:20
          輸入新的結(jié)點值:8 22 4 12 10 14 -1       (以-1結(jié)束結(jié)點的輸入)
          struct of the binary tree:
          number   addresss      data      lchild         rchild
          1               4391168       20        4391104   4391040
          2               4391104       8          4390976   4399072
          3               4390976      4           0                 0
          4               4399072     12          4399008  4398944
          5               4399008     10          0                0
          6               4398644     14          0                0
          7               4391040     22          0                0
          用括號形式輸出:20(8(4,12(10,14)),22)   (輸出左子樹打印左括號,輸出右子樹后打印括號)
          請任意輸入樹中存在的兩個結(jié)點:4,14
          輸出4和14的最低祖先:8




          評論

          # re: LCA 最近公共祖先問題 (1)  回復(fù)  更多評論   

          2007-10-06 17:15 by EvilGenuis
          很好,很強(qiáng)大 !

          # re: LCA 最近公共祖先問題 (1)  回復(fù)  更多評論   

          2008-11-09 22:03 by lonelycorn
          為什么不用tarjan算法?
          主站蜘蛛池模板: 定结县| 信阳市| 徐汇区| 中阳县| 马边| 彭山县| 蕉岭县| 成安县| 那坡县| 苏尼特右旗| 新源县| 昌黎县| 平湖市| 衡东县| 项城市| 深圳市| 印江| 余庆县| 定州市| 来安县| 平顺县| 玉山县| 调兵山市| 乐清市| 专栏| 黄陵县| 敦煌市| 拜城县| 邵东县| 卢龙县| 清镇市| 北宁市| 郴州市| 论坛| 玉林市| 福鼎市| 潼南县| 河北省| 建瓯市| 当雄县| 同仁县|