（2）loser tree的其它建树（实现）方法

（3）bbst（最佳bst）的建树方法

imho:大题。。。。。

void Thread(ThreadNode *root)
{
    ThreadNode *pre=NULL;
    StackNode *e=new StackNode;
    e.pointer=root;
    using std::stack;
    stack<StackNode> s;
    while(!s.empty()||e.pointer)
    {
         if(e.pointer)
         {
               ThreadVisit(e.pointer,pre);   //pre
               e.tag=left;
               s.push(e);
               e.pointer=e.pointer->lc;
          }
         else
         {
               e=s.top;   s.pop();
               if(e.tag==left)
               {
                      ThreadVisit(e.pointer,pre);   //In
                      e.tag=right;
                      s.push(e);
                      e.pointer=e.pointer->rc;
               }
               else
               {
                       ThreadVisit(e.pointer,pre);   //Post
                       e.pointer=NULL;
               }
         }
     }
}

void ThreadVisit(ThreadNode *e.pointer,ThreadNode *pre)
{
     visit(e.pointer->value());
     if(pre!=NULL&&pre->rc==NULL)
     {
           pre->rt=1;
           pre->rc=e.pointer;
     }
     if(pre!=NULL&&e.pointer->lc==NULL)
     {
           e.pointer->lt=1;
           e.pointer->lc=pre;
     }
     pre=e.pointer;
}

我总结的穿线树性质：
（1）中序：可找中序前驱，中序后继，前序后继，后序前驱；
（2）后序：可找后序前驱；
（3）前序：可找前序后继；
欢迎大家补充！

所以算法是很简单的：
Node* Build_OBST(int **r,int n)
{
      for(int i=0;i+2<=n;i++)
      {
            if(r[i][i+2]==i+1)
               SetParent(i+1,i+2);  //将i+1作为i+2的父亲
           else   SetParent(i+2,i+1);
      }
      Node *root=Address(r[0][n]); //r[0][n]是归并n个节点后的根
     return root;
}

提示：从下到上，用等价类合并；从上到下，用回溯。

              s.push(e);
          }
         else
         {
               e=s.top;

               s.pop();
               ThreadVisit(e.pointer,pre);
               e.pointer=e.pointer->rc;
         }
     }

其他和Supremgoooo 相同，请各位指教

这个算法我想了很长时间了，感觉是只可意会不可言传的算法。实际写出来太难了。。。

Answers：不行！因为构造穿线树时候，事实上是对树的一种遍历，而树本身就是非线性的！可是穿线树结果是让其具有线性特征！将非线性转化为线性，必须要有种“暂时的存储器”用来过渡，这就是栈存在的意义！即用此结构来调节、缓冲数据的顺序！