輸入一棵二進制查找樹, 将該樹轉換為它的鏡像

要求使用遞歸和循環兩種方法.

二叉樹節點定義:

typedef struct BSTreeNode{

int m_nValue;

struct BSTreeNode * m_pLeft;

struct BSTreeNode * m_pRight;

}BSTreeNode;

一.遞歸

void reverseBTree(BSTreeNode * bstree)

{

BSTreeNode * pnode;

if(bstree)

{

reverseBTree(bstree->m_pLeft);

reverseBTree(bstree->m_pRight);

pnode = bstree->m_pLeft;

bstree->m_pLeft = bstree->m_pRight;

bstree->m_pRight = pnode;

}

}

二. 循環

循環的實作中需要使用棧或者隊列來周遊二叉樹, 棧/隊列中元素為樹節點的指針

void reverseBTree_cycle(BSTreeNode * bstree)

{

Stack st;

BSTreeNode * current;

BSTreeNode * temp;

if(!bstree)

return;

initStack(&st);

push(&st, bstree);

while(!isEmpty(&st))

{

pop(&st, &current);

temp = current->m_pRight;

current->m_pRight = current->m_pLeft;

current->m_pLeft = temp;

if(current->m_pLeft)

push(&st, current->m_pLeft);

if(current->m_pRight)

push(&st, current->m_pRight);

}

}