=0)個有限個數(shù)據(jù)的元素集合,形狀像一顆倒過來的樹。而二叉樹就是樹的一種特殊結(jié)構(gòu):完全二叉樹的數(shù)組表示鏈表存儲表示下面..."/>
您好,登錄后才能下訂單哦!
首先先來看一下樹的結(jié)構(gòu):
樹是n(n>=0)個有限個數(shù)據(jù)的元素集合,形狀像一顆倒過來的樹。
而二叉樹就是樹的一種特殊結(jié)構(gòu):
完全二叉樹的數(shù)組表示
鏈表存儲表示
下面我就實現(xiàn)一下二叉鏈的這種結(jié)構(gòu):
首先是它的節(jié)點的結(jié)構(gòu):
template <typename T> struct BinaryTreeNode { public: BinaryTreeNode(const T &data)//構(gòu)造函數(shù) :_left(NULL) ,_right(NULL) ,_data(data) {} public: BinaryTreeNode<T> * _left;//左子樹 BinaryTreeNode<T> * _right;//右子樹 T _data;//數(shù)據(jù)項 };
然后是它的基本成員函數(shù):
template <typename T> class BinaryTree { typedef BinaryTreeNode<T> Node;//重命名struct結(jié)構(gòu) public: BinaryTree()//無參的構(gòu)造函數(shù) :_root(NULL) {} BinaryTree(const T* a, size_t size, const T& invalid)//有參構(gòu)造函數(shù) :_root(NULL) { size_t index = 0; _root = _CreatBinaryTree(a, size, invalid, index); } BinaryTree(const BinaryTree<T> & t)//拷貝構(gòu)造 :_root(NULL) { _root = _Copy(t._root); } BinaryTree<T>& operator=(BinaryTree<T> t)//賦值運算符的重載 { if (this != &t)//防止自賦值 { swap(_root, t._root); } return *this; } ~BinaryTree()//析構(gòu)函數(shù) { if (_root) { _Delete(_root); } } void PrevOrder()//前序遍歷 { _PrevOrder(_root); cout << "over"<<endl; } void InOrder()//中序遍歷 { _InOrder(_root); cout << "over" << endl; } void PostOrder()//后序遍歷 { _PostOrder(_root); cout << "over" << endl; } void LevelOredr()//層次遍歷 { _LevelOrder(_root); cout << "over" << endl; } size_t Size()//節(jié)點數(shù) { return _Size(_root); } size_t Depth()//深度 { return _Depth(_root); } size_t LeafSize()//葉子節(jié)點數(shù) { return _LeafSize(_root); } protected: //創(chuàng)建二叉樹 Node* _CreatBinaryTree(const T *a, size_t size, const T& invalid,size_t& index) { Node * cur = NULL; if (index < size&&a[index] != invalid)//不能越界 { cur = new Node(a[index]);//開辟節(jié)點 cur->_left = _CreatBinaryTree(a, size, invalid, ++index);//遞歸創(chuàng)建左子樹 cur->_right = _CreatBinaryTree(a, size, invalid, ++index);//遞歸創(chuàng)建右子樹 } return cur; } //復制二叉樹 Node* _Copy(Node * root) { Node * cur = NULL; if (root == NULL) { return NULL; } cur = new Node(root->_data);//創(chuàng)建該節(jié)點 cur->_left = _Copy(root->_left); cur->_right = _Copy(root->_right); return cur; } //刪除 void _Delete(Node * &root) { if (root == NULL) { return; } if (root->_left == NULL && root->_right == NULL)//該節(jié)點沒有左右孩子 { delete root;//釋放該節(jié)點 root = NULL; return; } _Delete(root->_left); _Delete(root->_right); } //前序遍歷:根節(jié)點--左子樹--右子樹 void _PrevOrder(Node * root) { if (root == NULL) { return; } cout << root->_data << "->"; _PrevOrder(root->_left); _PrevOrder(root->_right); } //中序遍歷:左子樹--根節(jié)點--右子樹 void _InOrder(Node * root) { if (root == NULL) { return; } _PrevOrder(root->_left); cout << root->_data << "->"; _PrevOrder(root->_right); } //后序遍歷:左子樹--右子樹--根節(jié)點 void _PostOrder(Node * root) { if (root == NULL) { return; } _PrevOrder(root->_left); _PrevOrder(root->_right); cout << root->_data << "->"; } //層次遍歷 void _LevelOrder(Node* root) { queue<Node*> q; if (root == NULL) { return; } q.push(root); while (!q.empty()) { if (q.front()->_left != NULL) { q.push(q.front()->_left); } if (q.front()->_right != NULL) { q.push(q.front()->_right); } cout << q.front()->_data << "->"; q.pop(); } } //節(jié)點個數(shù) size_t _Size(Node * root) { if (root == NULL) { return 0; } return _Size(root->_left) + _Size(root->_right) + 1;//當左子樹或者右子樹不為空時,該節(jié)點有數(shù)據(jù) } //二叉樹的深度 size_t _Depth(Node * root) { if (root==NULL) { return 0; } size_t leftDepth = _Depth(root->_left); size_t rightDepth = _Depth(root->_right); /*if (leftDepth >= rightDepth) { return leftDepth + 1; } else return rightDepth + 1;*/ return leftDepth > rightDepth?leftDepth + 1 : rightDepth+1; } //葉子節(jié)點個數(shù) size_t _LeafSize(Node * root) { size_t size = 0; if (root == NULL) { return size; } if (root->_left == NULL&&root->_right == NULL) { size++; return size; } return _LeafSize(root->_left)+_LeafSize(root->_right); } private: Node * _root;//根節(jié)點 };
測試用例以及結(jié)果如下:
void Test() { int array1[10] = { 1, 2, 3, '#', '#', 4, '#' , '#', 5, 6 }; BinaryTree<int> b1(array1, 10, '#'); cout << "前序遍歷:"; b1.PrevOrder(); cout << "中序遍歷:"; b1.InOrder(); cout << "后序遍歷:"; b1.PostOrder(); cout << "層次遍歷:"; b1.LevelOredr(); cout << endl; cout << "節(jié)點數(shù):" << b1.Size() << endl; cout << "深度:" << b1.Depth() << endl; cout << "葉子節(jié)點數(shù):" << b1.LeafSize() << endl; cout << endl; BinaryTree<int> b2(b1); cout << "前序遍歷:"; b2.PrevOrder(); cout << "中序遍歷:"; b2.InOrder(); cout << "后序遍歷:"; b2.PostOrder(); cout << "層次遍歷:"; b2.LevelOredr(); cout << endl; cout << "節(jié)點數(shù):" << b2.Size() << endl; cout << "深度:" << b2.Depth() << endl; cout << "葉子節(jié)點數(shù):" << b2.LeafSize() << endl; cout << endl; BinaryTree<int> b3; b3 = b1; cout << "前序遍歷:"; b3.PrevOrder(); cout << "中序遍歷:"; b3.InOrder(); cout << "后序遍歷:"; b3.PostOrder(); cout << "層次遍歷:"; b3.LevelOredr(); cout << endl; cout << "節(jié)點數(shù):" << b3.Size() << endl; cout << "深度:" << b3.Depth() << endl; cout << "葉子節(jié)點數(shù):" << b3.LeafSize() << endl; }
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。