二叉樹(shù)遍歷方式(Tree Traversals )
二叉樹(shù)
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)表示時(shí)間復(fù)雜度是線性，那么什么情況下用O(log n)表示呢顿天？
要滿足2個(gè)條件：
1.你搜索的下一個(gè)節(jié)點(diǎn)有可能是滿足條件的節(jié)點(diǎn)
2.滿足條件的節(jié)點(diǎn)只有一個(gè)
對(duì)樹(shù)的操作的時(shí)間復(fù)雜度如下
1.search：O(log n)
2.insert：O(n)
3.remove：O(n)
刪除（重點(diǎn)）
Status Delete(BiTree *&p){
//該節(jié)點(diǎn)為葉子節(jié)點(diǎn)堂氯，直接刪除
BiTree *q, *s;
if (!p->rchild && !p->lchild)
{
delete p;
p = NULL; // Status Delete(BiTree *&p) 要加&才能使P指向NULL
}
else if(!p->rchild){ //右子樹(shù)空則只需重接它的左子樹(shù)
q=p->lchild;
p->data = p->lchild->data;
p->lchild=p->lchild->lchild;
p->rchild=p->lchild->rchild;
delete q;
}
else if(!p->lchild){ //左子樹(shù)空只需重接它的右子樹(shù)
q=p->rchild;
p->data = p->rchild->data;
p->lchild=p->rchild->lchild;
p->rchild=p->rchild->rchild;
delete q; }
else{ //左右子樹(shù)均不空
q=p;
s=p->lchild;
while(s->rchild){
q=s;
s=s->rchild;
} //轉(zhuǎn)左，然后向右到盡頭
p->data = s->data; //s指向被刪結(jié)點(diǎn)的“前驅(qū)”
if(q!=p)
q->rchild = s->lchild; //重接*q的右子樹(shù)
else
q->lchild = s->lchild; //重接*q的左子樹(shù)
delete s;
}
return true;
}
