二叉樹遍歷方式(Tree Traversals )

二叉樹

1.中序（Inorder）：Left->Root->Right。上圖遍歷順序是：4，2，5，1，3
2.前序（Preorder）:Root->Left->Right。上圖遍歷順序是：1，2，4，5，3
3.后序（Postorder）：Left->Right->Root。上圖遍歷順序是：4，5，2，3，1

復(fù)雜度

我們都知道O(n)表示時間復(fù)雜度是線性，那么什么情況下用O(log n)表示呢？
要滿足2個條件：
1.你搜索的下一個節(jié)點有可能是滿足條件的節(jié)點
2.滿足條件的節(jié)點只有一個

對樹的操作的時間復(fù)雜度如下
1.search：O(log n)
2.insert：O(n)
3.remove：O(n)

刪除（重點）

Status Delete(BiTree *&p){
  //該節(jié)點為葉子節(jié)點，直接刪除
  BiTree *q, *s;
  if (!p->rchild && !p->lchild)
  {
      delete p;
      p = NULL;  // Status Delete(BiTree *&p) 要加&才能使P指向NULL
  }
  else if(!p->rchild){  //右子樹空則只需重接它的左子樹
    q=p->lchild;
    p->data = p->lchild->data;
    p->lchild=p->lchild->lchild;
    p->rchild=p->lchild->rchild;

    delete q;
  }
  else if(!p->lchild){  //左子樹空只需重接它的右子樹
    q=p->rchild;
    p->data = p->rchild->data;
    p->lchild=p->rchild->lchild;
    p->rchild=p->rchild->rchild;

    delete q;  }
  else{ //左右子樹均不空
    q=p; 
    s=p->lchild;
    while(s->rchild){ 
      q=s; 
      s=s->rchild;
    }   //轉(zhuǎn)左，然后向右到盡頭
    p->data = s->data;  //s指向被刪結(jié)點的“前驅(qū)”
    if(q!=p)    
      q->rchild = s->lchild;    //重接*q的右子樹
    else 
      q->lchild = s->lchild;    //重接*q的左子樹
    delete s;
  }
  return true;
}