您好,登錄后才能下訂單哦!
二叉樹:每個(gè)節(jié)點(diǎn)最多兩個(gè)孩子節(jié)點(diǎn)。
二叉樹的結(jié)構(gòu): struct TreeNode
{
DataType _value; //節(jié)點(diǎn)值
TreeNode* _left; //左孩子
TreeNode* _ridht; //右孩子
};
二叉樹的基礎(chǔ): 構(gòu)造、拷貝構(gòu)造、析構(gòu)、賦值運(yùn)算符的重載
二叉樹的知識(shí)點(diǎn): 高度、節(jié)點(diǎn)的個(gè)數(shù)、子節(jié)點(diǎn)的個(gè)數(shù)
二叉樹的遍歷: 前序、中序、后序遍歷(遞歸及非遞歸)
遍歷順序: 前序——根左右 中序——左根右 后序——左右根
注意: 遞歸遍歷時(shí),應(yīng)該注意不要出現(xiàn)棧溢出現(xiàn)象。
因?yàn)?+index返回對(duì)象,index++返回臨時(shí)變量,所以傳引用做參數(shù)時(shí)有++index。
#pragma once #include<queue> #include<stack> //二叉樹的結(jié)構(gòu) template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T _data; //構(gòu)造函數(shù) BinaryTreeNode(const T& x) :_left(NULL) , _right(NULL) , _data(x) {} }; template<class T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: //構(gòu)造 BinaryTree() :_root(NULL) {} // a--樹的節(jié)點(diǎn)前序遍歷的數(shù)組 size--數(shù)組中元素個(gè)數(shù) invaild--無效值即節(jié)點(diǎn)為空 BinaryTree(const T* a,size_t size,const T& invalid) { size_t index = 0; _root = _CreateTree(a, size,invalid,index); } //析構(gòu) ~BinaryTree() { _Destory(_root); _root = NULL; } //拷貝 BinaryTree(const BinaryTree<T>& t) { _root = _Copy(t._root); } //賦值重載(傳統(tǒng)) //BinaryTree<T>& operator=(const BinaryTree<T>& t) //{ // if (this != &t) // { // Node* tmp = _Copy(t._root); // _Destory(_root); // _root = tmp; // } // return *this; //} //賦值重載(現(xiàn)代) BinaryTree<T>& operator=(BinaryTree<T> t) { swap(_root, t._root); return *this; } T& operator->() { return _root; } public: void PrevOrder()//前序 { _PrevOrder(_root); cout << endl; } void InOrder()//中序 { _InOrder(_root); cout << endl; } void PostOrder()//后序 { _PostOrder(_root); cout << endl; } size_t Size() //節(jié)點(diǎn)個(gè)數(shù) { return _Size(_root); } size_t Depth() //樹的深度 { return _Depth(_root); } size_t LeafSize() //葉子節(jié)點(diǎn)個(gè)數(shù) { return _LeafSize(_root); } //層次遍歷 void LevelOrder() { queue<Node*> q; if (_root) { q.push(_root); } while (!q.empty()) { Node* front = q.front(); cout << front->_data << " "; q.pop(); if (front->_left) { q.push(front->_left); } if (front->_right) { q.push(front->_right); } } cout << endl; } public: //非遞歸的前中后序遍歷(棧) void PrevOrder_NonR() { stack<Node*> s; if (_root) s.push(_root); while (!s.empty()) { Node* top = s.top(); cout << top->_data << " "; s.pop(); //棧后進(jìn)先出 ,所以 右先進(jìn),左先出 if (top->_right) s.push(top->_right); if (top->_left) s.push(top->_left); } cout << endl; } void InOrder_NonR() { //壓左樹 //取出一個(gè)節(jié)點(diǎn)即它的左路走完了,在訪問右樹(看作子問題) stack<Node*> s; Node* cur = _root; while (cur || !s.empty()) { //壓樹的左路節(jié)點(diǎn)直至最左段節(jié)點(diǎn) while (cur) { s.push(cur); cur = cur->_left; } if (!s.empty()) { Node* top = s.top(); s.pop(); cout << top->_data << " "; cur=top->_right; } } cout << endl; } void PostOrder_NonR() { Node* prev = NULL; Node* cur = _root; stack<Node*> s; while (cur || !s.empty()) { //壓樹的左路節(jié)點(diǎn)直至最左段節(jié)點(diǎn) while (cur) { s.push(cur); cur = cur->_left; } Node* top = s.top(); if (top->_right == NULL || top->_right == prev) { cout << top->_data << " "; s.pop(); prev = top; } else { cur = top->_right; } } cout << endl; } protected: //注意 此處index要用引用傳參 Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index) { Node* root = NULL; if ((index < size) && (a[index] != invalid)) { root = new Node(a[index]); //注意下面只能用++index。此處傳的是引用 //因?yàn)?+index返回對(duì)象,index++返回臨時(shí)變量。 root->_left = _CreateTree(a, size, invalid, ++index); root->_right = _CreateTree(a, size, invalid, ++index); } return root; } void _Destory(Node* root) { if (root == NULL) return; _Destroy(root->_left); _Destroy(root->_right); delete root; } Node* _Copy(Node* root) { if (root == NULL) return NULL; NOde* newRoot = new Node(root->_data); newRoot->_left = _Copy(root->_left); newRoot->_right = _Copy(root->_right); return newRoot; } ////////////// void _PrevOrder(Node* root) { if (root == NULL) return; cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } void _InOrder(Node* root) { if (root == NULL) return; _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); } void _PostOrder(Node* root) { if (root == NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } size_t _Size(Node* root) { if (root == NULL) return 0; return (_Size(root->_left) + _Size(root->_right) + 1); } size_t _Depth(Node* root) { if (root == NULL) return 0; size_t LeftDepth = _Depth(root->_left); size_t RightDepth = _Depth(root->_right); return (LeftDepth > RightDepth) ? (LeftDepth + 1) : (RightDepth + 1); } size_t _LeafSize(Node* root) { if (root == NULL) return 0; if ((root->_left == NULL) && (root->_right == NULL)) return 1; return (_LeafSize(root->_left) + _LeafSize(root->_right)); } private: Node *_root; };
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。