面試100 -11二叉樹鏡像

求二叉樹的鏡像

1 該問題實質上是將二叉樹的左右兩子樹，進行交換。
   求查找樹的映像
   即是將原來標準的二叉樹，翻轉180度。
   實現方法：
方法(1)
   首先前序遍歷，標準二茶樹，然后將每一個節點，按照逆查找樹，插入到鏡像中
方法(2)
   前序遍歷，交換左右子樹,遞歸遍歷
方法(3)
   使用非遞歸的方法，遍歷左右子樹

2 代碼如下：

#include <iostream>

#include <stack>

using namespace std ;

template <class T>

struct BinaryTree{

T data ;

BinaryTree * lc ;

BinaryTree * rc ;

} ;

BinaryTree <int> * root ;

BinaryTree <int> * image ;

const int N = 7 ;

template <class T>

void switchs( BinaryTree <T> * p ,stack <BinaryTree<T>*> st)

{

while(!st.empty()) //當st不為空的時候

{

BinaryTree <T> * top = st.top() ;

st.pop() ;

while(top) //前序遍歷，右節點依次插入堆棧，左節點依次進行操作

{ //此處也可以，左節點和右節點都入棧

BinaryTree <T> * temp = top->lc ; //交換

top->lc = top->rc ;

top->rc = temp ;

if(top->rc) //右節點依次壓棧

st.push(top->rc) ;

top = top->lc ;

}

template <class T>

void buildTree(T x) //正規的二叉查找樹

{

if(root == 0)

{

root = (BinaryTree <T> *) malloc(sizeof(BinaryTree <T>)) ;

root->lc = 0 ;

root->rc = 0 ;

root->data = x ;

return ;

}

BinaryTree <T> * p = root ;

BinaryTree <T> * q = root ;

while(p)

{

q = p ;

if(p->data <= x)

p = p->rc ;

else

p = p->lc ;

}

p = (BinaryTree <T> *) malloc(sizeof(BinaryTree <T>)) ;

p->data = x ;

p->lc = 0 ;

p->rc = 0 ;

if(q->data > x)

q->lc = p ;

else

q->rc = p ;

}

template <class T>

void buildImageTree(T x) //正規的二叉查找樹

{

if(image == 0)

{

image = (BinaryTree <T> *) malloc(sizeof(BinaryTree <T>)) ;

image->lc = 0 ;

image->rc = 0 ;

image->data = x ;

return ;

}

BinaryTree <T> * p = image ;

BinaryTree <T> * q = image ;

while(p)

{

q = p ;

if(p->data <= x)

p = p->lc ;

else

p = p->rc ;

}

p = (BinaryTree <T> *) malloc(sizeof(BinaryTree <T>)) ;

p->data = x ;

p->lc = 0 ;

p->rc = 0 ;

if(q->data <= x)

q->lc = p ;

else

q->rc = p ;

}

template <class T>

void postOrder(BinaryTree <T> * p)

{

if(p)

{

postOrder(p->lc) ;

cout<<p->data<<" " ;

postOrder(p->rc) ;

}

template <class T>

void preOrder(BinaryTree <T> * p )

{

if(p)

{

buildImageTree(p->data) ;

preOrder(p->lc) ;

preOrder(p->rc) ;

}

template <class T> //可以看做交換左右兩個節點

void switcLR(BinaryTree <T> * p)

{

if(p)

{

BinaryTree <T> * temp = p->lc ;

p->lc = p->rc ;

p->rc = temp ;

switcLR(p->lc) ;

switcLR(p->rc) ;

}

int main()

{

int i ;

int a[] = {8 ,6 ,10 , 5 ,7, 9 , 11} ;

for(i = 0 ; i < N ; i++)

buildTree(a[i]) ;

postOrder(root) ;

cout<<endl ;

stack <BinaryTree <int> *> st ;

st.push(root) ; //首先把根傳進去

switchs(root , st) ;

postOrder(root) ;

system("pause");

return 0 ;

}

posted on 2011-05-17 09:02 kahn 閱讀(822) 評論(0) 編輯收藏引用所屬分類: 算法相關

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 9-24MTK一面二面微軟筆試總結 2011-09-07xx移動創業公司筆試題編程之美2.7 最大公約數 O(n)實現刪除兩個數組中的共同元素編程之美1.9(二) 高效率地安排會面分組背包問題（六）二維背包問題（五）多重背包（三）完全背包問題 <二>

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

jake1036

My Links

Blog Stats

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

面試100 -11二叉樹鏡像

求二叉樹的鏡像