二叉樹先序遍歷;(1)先序訪問根節(jié)點 (2)先序訪問左子樹 (3)先序訪問右子樹
創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),章丘企業(yè)網(wǎng)站建設(shè),章丘品牌網(wǎng)站建設(shè),網(wǎng)站定制,章丘網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,章丘網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè),幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強企業(yè)競爭力??沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿,時刻以成就客戶成長自我,堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己,讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。
二叉樹中序遍歷;(1)中序訪問根節(jié)點 (2)中序訪問左子樹 (3)中序訪問右子樹
二叉樹后序遍歷;(1)后序訪問根節(jié)點 (2)后序訪問左子樹 (3)后序訪問右子樹
測試用例:int a[10]={'1','2','3','#','#','4','#','#','5','6'}
代碼:
#include<iostream> using namespace std; #include<queue> #include<stack> template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T _data; BinaryTreeNode(const T& d) :_left(NULL) ,_right(NULL) ,_data(d) {} }; template<class T> class BinaryTree { public: BinaryTree() :_root(NULL) {} BinaryTree(const T* a,size_t size,const T& invalid) { size_t index = 0; _root = _Create(a,size,index,invalid); } //BinaryTree(const BinaryTree<T>& d) //{ // BinaryTreeNode<T> root = NULL; //} BinaryTree<T>& operator = (const BinaryTree<T>& d) { swap(root,d._root ); } void PrevOrder() { _PrevOrder(_root); } void InOrder() { _InOrder(_root); } size_t Size() { _Size(_root); } size_t Depth() { return _Depth(_root); } size_t LeafSize() { return _LeafSize( _root); } void LevelOrder() { _LeavelOrder(); } void PrevOrder_NonR() { _PrevOrder_NonR(); } void InOrder_NonR() { _InOrer_NonR(); } void PostOrder_NonR() { _PostOrder_NonR(); } public: protected: BinaryTreeNode<T>* _Create(const T*a,size_t size,size_t& index,const T& invalid) { BinaryTreeNode<T> *root = NULL; while(index<size && a[index] != invalid) { root = new BinaryTreeNode<T> (a[index]); root->_left = _Create(a,size,++index,invalid); root->_right = _Create(a,size,++index,invalid); } return root; } void _PrevOrder(BinaryTreeNode<T>* root) { if(root == NULL) { return; } cout<<root->_data<<" " ; _PrevOrder(root->_left ); _PrevOrder(root->_right); } void _InOrder(BinaryTreeNode<T>* root) { if(root == NULL) { return; } _InOrder (root->_left ); cout<<root->_data<<" " ; _InOrder (root->_right ); } size_t _size(BinaryTreeNode<T>* root) { if(root == NULL) { return 0; } return _Size(root->_left )+_Size(root->_right )+1; } size_t _Depth(BinaryTreeNode<T>* root) { if(root == NULL) { return 0; } int left = _Depth(root->_left )+1; int right = _Depth (root->_right )+1; return (left>right?left:right); } size_t _LeafSize(BinaryTreeNode<T>* root) { if(root == NULL) { return 0; } if(root->_left == NULL && (root->_right == NULL)) { return 1; } return _LeafSize(root->_left)+_LeafSize (root->_right); } void _LeavelOrder() { queue<BinaryTreeNode<T>*>q; if(_root) { q.push(_root); } while(!q.empty()) { BinaryTreeNode<T>* front = q.front(); cout<<front._data<<" "; if(_root->_left) { q.push(_root->_left); } if(_root->_right) { q.push(_root->_right); } q.pop(); } cout<<endl; } void _PrevOrder_NonR() { stack<BinaryTreeNode<T>*>s; BinaryTreeNode<T>* cur = _root; while(cur||!s.empty()) { while(cur ) { cout<<cur->_data <<" "; s.push(cur); cur = cur->_left ; } if(!s.empty()) { BinaryTreeNode<T>* top = s.top(); cur = top->_right ; s.pop(); } } } void _InOrer_NonR() { stack<BinaryTreeNode<T>*> s; BinaryTreeNode<T>* cur = _root; while(cur||!s.empty()) { while(cur) { s.push(cur); cur = cur->_left ; } BinaryTreeNode<T>* Top = s.top(); cout<<Top->_data<<" "; cur = Top->_right ; s.pop(); } cout<<endl; } void _PostOrder_NonR() { BinaryTreeNode<T>* cur = _root; stack<BinaryTreeNode<T>*>s; BinaryTreeNode<T>* prev = NULL; while(cur||!s.empty()) { while(cur) { s.push(cur); cur = cur->_left ; } BinaryTreeNode<T>* top = s.top(); if(top->_right == NULL||top->_right == prev) { cout<<top->_data <<" "; s.pop(); prev = top; } else cur = top->_right ; //cout<<endl; } } protected: BinaryTreeNode<T>* _root; }; int main() { int a1[10] = {1,2,3,'#','#',4,'#','#',5,6}; BinaryTree<int> b1(a1,10,'#'); //b1.InOrder(); //b1.InOrder_NonR (); //b1.Depth(); //b1.PrevOrder_NonR(); b1.PostOrder_NonR(); system("pause"); return 0; }
網(wǎng)站標(biāo)題:二叉樹的創(chuàng)建以及遞歸與非遞歸遍歷
文章鏈接:http://muchs.cn/article46/ihcghg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供網(wǎng)站改版、網(wǎng)站導(dǎo)航、域名注冊、響應(yīng)式網(wǎng)站、品牌網(wǎng)站制作、靜態(tài)網(wǎng)站
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)