C++基於遞歸和非遞歸算法求二叉樹鏡像的方法。本站提示廣大學習愛好者:(C++基於遞歸和非遞歸算法求二叉樹鏡像的方法)文章只能為提供參考,不一定能成為您想要的結果。以下是C++基於遞歸和非遞歸算法求二叉樹鏡像的方法正文
作者:難免有錯_
這篇文章主要介紹了C++基於遞歸和非遞歸算法求二叉樹鏡像的方法,針對二叉樹遍歷結合實例形式分析了遞歸與非遞歸算法的實現與使用技巧,需要的朋友可以參考下本文實例講述了C++基於遞歸和非遞歸算法求二叉樹鏡像的方法。分享給大家供大家參考,具體如下:
/*求二叉樹鏡像 -- 采用遞歸和非遞歸方法 經調試可運行源碼及分析如下: ***/ #include <stdlib.h> #include <iostream> #include <queue> using std::cout; using std::cin; using std::endl; using std::queue; /*二叉樹結點定義*/ typedef struct BTreeNode { char elem; struct BTreeNode *pleft; struct BTreeNode *pright; }BTreeNode; /* 求二叉樹鏡像 遞歸方式步驟: 如果proot為NULL,則為空樹,返回; 如果proot不為NULL,交換proot左右結點,然後分別求左右子樹的鏡像; */ /*遞歸求二叉樹鏡像*/ void get_bitree_mirror(BTreeNode* proot) { if (proot == NULL) return ; BTreeNode* temp_node = proot->pleft; proot->pleft = proot->pright; proot->pright = temp_node; get_bitree_mirror(proot->pleft); get_bitree_mirror(proot->pright); return ; } /* 非遞歸方式步驟如下: 借助隊列 首先,將根節點proot入隊; 第一步:當隊列非空時,獲取當前層次的節點總數,即當前隊列的長度;執行第二步; 第二步:按照當前層的節點總數,出隊進行遍歷節點,在遍歷時, 交換左右節點,如果左右節點存在,則入隊; 當遍歷完當前層所有節點時,遍歷下一層,執行第一步。 */ void get_bitree_mirror_leveltraverse(BTreeNode* proot) { if(proot == NULL) return ; queue <BTreeNode*> que; que.push(proot); int level_nodes_number = 0; while (!que.empty())//層次遍歷 { level_nodes_number = que.size(); int level_count = 0; while (level_count < level_nodes_number) { ++level_count; proot = que.front(); que.pop(); //交換左右子節點 BTreeNode* temp_node = proot->pleft; proot->pleft = proot->pright; proot->pright = temp_node; if(proot->pleft != NULL) que.push(proot->pleft); if(proot->pright != NULL) que.push(proot->pright); } } return ; } /*初始化二叉樹根節點*/ BTreeNode* btree_init(BTreeNode* &bt) { bt = NULL; return bt; } /*先序創建二叉樹*/ void pre_crt_tree(BTreeNode* &bt) { char ch; cin >> ch; if (ch == '#') { bt = NULL; } else { bt = new BTreeNode; bt->elem = ch; pre_crt_tree(bt->pleft); pre_crt_tree(bt->pright); } } /*先序遍歷*/ void pre_order_traverse(BTreeNode* proot) { if(proot == NULL) return; cout<< proot->elem << " "; pre_order_traverse(proot->pleft); pre_order_traverse(proot->pright); return; } int main() { int tree_node_number = 0; BTreeNode *bt; btree_init(bt);//初始化根節點 pre_crt_tree(bt);//創建二叉樹 cout << "先序遍歷輸出如下:" << endl; cout << "調用鏡像函數前:" << endl; pre_order_traverse(bt); cout << endl; get_bitree_mirror(bt); cout << "遞歸調用鏡像函數後:" << endl; pre_order_traverse(bt); cout << endl; cout << "非遞歸調用鏡像函數後:" << endl; get_bitree_mirror_leveltraverse(bt); pre_order_traverse(bt); cout << endl; system("pause"); return 0; }
/* 運行結果: a b c # # # d e # # # ------以上為輸入----------- ------以下為輸出----------- 先序遍歷輸出如下: 調用鏡像函數前: a b c d e 遞歸調用鏡像函數後: a d e b c 非遞歸調用鏡像函數後: a b c d e 請按任意鍵繼續. . . --------------------------------- 本例創建的二叉樹形狀: a b d c e 調用遞歸求二叉樹鏡像形狀: a d b e c 再次調用非遞歸求二叉樹鏡像形狀(即鏡像的鏡像): a b d c e */
希望本文所述對大家C++程序設計有所幫助。