二叉樹是一種常見的數(shù)據(jù)結(jié)構(gòu),這里我們需要要注意的是,二叉樹的非遞歸的遍歷。
成都創(chuàng)新互聯(lián)公司主要從事網(wǎng)頁設計、PC網(wǎng)站建設(電腦版網(wǎng)站建設)、wap網(wǎng)站建設(手機版網(wǎng)站建設)、成都響應式網(wǎng)站建設公司、程序開發(fā)、網(wǎng)站優(yōu)化、微網(wǎng)站、微信平臺小程序開發(fā)等,憑借多年來在互聯(lián)網(wǎng)的打拼,我們在互聯(lián)網(wǎng)網(wǎng)站建設行業(yè)積累了豐富的成都網(wǎng)站制作、成都網(wǎng)站設計、網(wǎng)站設計、網(wǎng)絡營銷經(jīng)驗,集策劃、開發(fā)、設計、營銷、管理等多方位專業(yè)化運作于一體。先序遍歷,中序遍歷,后序遍歷
這三種遍歷,如果用非遞歸的方式實現(xiàn),我們則需要借助棧這個結(jié)構(gòu),首先我們需要遍歷所有左子樹的左節(jié)點。進行壓棧,完成壓棧之后,根據(jù)不同的需求,判斷是否該繼續(xù)訪問或者彈出亦或者是壓入該節(jié)點的右子樹。
層序遍歷
不同于其他的遍歷方式,層序遍歷是以根節(jié)點為開始,依次向下,每層從左到右依次訪問。
這里我們需要借助與隊列這種數(shù)據(jù)結(jié)構(gòu),層層入隊,層層出隊,完成遍歷。
代碼如下:
#pragma once #include<iostream> using namespace std; #include<queue> #include<stack> typedef char DataType; struct BinaryTreeNode//節(jié)點結(jié)構(gòu)體 { BinaryTreeNode(DataType data = (DataType)0) :_data(data) , _leftChild(NULL) , _rightChild(NULL) {} DataType _data; BinaryTreeNode* _leftChild; BinaryTreeNode* _rightChild; }; class BinaryTree { typedef BinaryTreeNode _NODE; public: BinaryTree(char* str)//通過先序的字符串構(gòu)造二插樹‘#’為空 { _root = _CreatTree(_root,str); } BinaryTree(const BinaryTree &t) { _root = _Copy(t._root); } BinaryTree operator =(BinaryTree t) { swap(_root, t._root); return *this; } ~BinaryTree() { _Destory(_root); } size_t Size()//求二叉樹的大小 { return _Size(_root); } size_t Depth()//求深度 { return _Depth(_root); } void LevelOrder()//層序遍歷二叉樹 { queue<_NODE*> NodeQueue; _NODE* cur = _root; NodeQueue.push(cur); while (!NodeQueue.empty()) { _NODE*tmp = NodeQueue.front();//取隊頭 cout << tmp->_data << " ";//訪問 NodeQueue.pop(); if (tmp->_leftChild)//左不為空入左,右不為空入右 NodeQueue.push(tmp->_leftChild); if (tmp->_rightChild) NodeQueue.push(tmp->_rightChild); } } void BackOrder_NONREC()//后續(xù)非遞歸遍歷 { stack<_NODE*> s; _NODE*prev = NULL; _NODE*cur = _root; while (!s.empty()||cur)//壓一顆樹的左子樹,直到最左 { while (cur) { s.push(cur); cur = cur->_leftChild; } _NODE* top = s.top(); if (top->_rightChild==NULL||top->_rightChild==prev)//若棧頂節(jié)點的右節(jié)點為空,或者是已經(jīng)訪問過的節(jié)點,則不彈出棧頂節(jié)點 { visitor(top); prev = top;//將最后一次訪問過得節(jié)點保存 s.pop(); } else//否則壓入以棧頂節(jié)的右節(jié)點點為根的左子樹,直到最左 { cur = top->_rightChild; } } } void InOrder_NONREC()//中序非遞歸遍歷 { stack<_NODE*> s; _NODE*cur = _root; while (!s.empty() || cur) { while (cur)//壓一棵樹的左節(jié)點直到最左,若為空則不進行壓棧 { s.push(cur); cur = cur->_leftChild; } _NODE* top = s.top(); if (!s.empty())//訪問棧頂節(jié)點,將另一顆被壓的樹,置為棧頂節(jié)點的右子樹 { visitor(top); s.pop(); cur = top->_rightChild; } } } void PrevOrder_NONREC()//先序非遞歸遍歷 { stack<_NODE*> s; _NODE* cur = NULL; s.push(_root); while (!s.empty()) { cur = s.top();//先訪問當前節(jié)點 visitor(cur); s.pop(); if (cur->_rightChild)//當前右節(jié)點不為空壓入 s.push(cur->_rightChild); if (cur->_leftChild) s.push(cur->_leftChild); } cout << endl; } protected: static void visitor(_NODE* cur)//訪問函數(shù),為了滿足測試,控制臺打印數(shù)據(jù) { cout << cur->_data << " "; } _NODE* _Copy(_NODE* root) { _NODE* newRoot = NULL; if (root == NULL) return NULL; else { newRoot = new _NODE(root->_data); newRoot->_leftChild = _Copy(root->_leftChild); newRoot->_rightChild = _Copy(root->_rightChild); } return newRoot; } size_t _Depth(_NODE* root) { size_t depth = 0; if (root == NULL) return depth; else { depth = _Depth(root->_leftChild) + 1; size_t newdepth = _Depth(root->_rightChild) + 1; depth = depth > newdepth ? depth : newdepth; } return depth; } size_t _Size(_NODE* root) { if (root==NULL) return 0; else return _Size(root->_leftChild) + _Size(root->_rightChild) + 1; } void _Destory(_NODE* &root) { if (root) { if ((root->_leftChild == NULL) &&(root->_rightChild == NULL)) { delete root; root = NULL; } else { _Destory(root->_leftChild); _Destory(root->_rightChild); _Destory(root); } } } _NODE*_CreatTree(_NODE* root,char* &str) { _NODE*cur = root; if (*str == '#' || *str == 0) { return NULL; } else { cur = new _NODE(*str); cur->_leftChild = _CreatTree(cur->_leftChild, ++str); cur->_rightChild = _CreatTree(cur->_rightChild,++str); } return cur; } protected: _NODE* _root; };
如有不足或疑問希望指正。
創(chuàng)新互聯(lián)www.cdcxhl.cn,專業(yè)提供香港、美國云服務器,動態(tài)BGP最優(yōu)骨干路由自動選擇,持續(xù)穩(wěn)定高效的網(wǎng)絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證, 機房獨有T級流量清洗系統(tǒng)配攻擊溯源,準確進行流量調(diào)度,確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟,新人活動云服務器買多久送多久。
分享標題:【代碼】C++實現(xiàn)二叉樹基本操作及測試用例-創(chuàng)新互聯(lián)
當前地址:http://bm7419.com/article46/ipihg.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián),為您提供App開發(fā)、手機網(wǎng)站建設、域名注冊、網(wǎng)站營銷、品牌網(wǎng)站制作、Google
聲明:本網(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)