C++实现二叉树
#include#include using namespace std; #include #include template struct BinaryTreeNode { BinaryTreeNode * _left; BinaryTreeNode * _right; T _data; BinaryTreeNode(const T& x) :_left(NULL) ,_right(NULL) ,_data(x) {} }; template class BinaryTree { public: BinaryTree() :_root(NULL) {} BinaryTree(const T* a, size_t size, const T& invalid) { size_t index = 0; _root = _CreateTree(a, size, index, invalid); } ~BinaryTree() { _DestroyTree(_root); _root = NULL; } BinaryTree(const BinaryTree & t) { _root = _CopyTree(t._root); } //赋值运算符重载的传统写法 /*BinaryTree & operator=(const BinaryTree& t) { if (this != &t) { _DestroyTree(_root); _root = _CopyTree(t._root); } return *this; }*/ //赋值运算符重载的现代写法 BinaryTree & operator=(BinaryTree t) { swap(_root, t._root); return *this; } //递归前序遍历 void PreOrderTraverse() { _PreOrderTraverse(_root); cout< *> q; q.push(_root); while (!q.empty()) { BinaryTreeNode * front = q.front(); q.pop(); cout< _left) { q.push(front->_left); } if (front->_right) { q.push(front->_right); } } } //非递归前序遍历 void PreOrderTraverse_NonR() { if (NULL == _root) { return; } stack *> s; s.push(_root); while (!s.empty())//当栈为空时遍历完成 { //先访问根节点 BinaryTreeNode * top = s.top(); s.pop(); cout< _data<<" "; //右节点存在时先入栈,后出栈 if (top->_right) { s.push(top->_right); } //左结点存在时后入栈,先出栈 if (top->_left) { s.push(top->_left); } } cout< *> s; BinaryTreeNode * cur = _root; while (cur || !s.empty()) { //左结点全部入栈 while (cur) { s.push(cur); cur = cur->_left; } if (!s.empty()) { BinaryTreeNode * top = s.top(); cout< _data<<" "; s.pop(); cur = top->_right;//将栈顶结点的右节点看作子树的根节点 } } cout< *> s; BinaryTreeNode * cur = _root; BinaryTreeNode * pre = NULL; while (cur || !s.empty())//当前结点为空和栈为空同时满足时遍历完成 { //左结点全部入栈 while (cur) { s.push(cur); cur = cur->_left; } BinaryTreeNode * top = s.top(); if (NULL == top->_right || pre == top->_right)//若当前结点的右结点为空或者右节点已经访问过,可以访问该结点 { cout< _data<<" "; pre = top; s.pop(); } else//该结点的右节点不为空且未被访问 { cur = top->_right;//将该结点的右节点看作子树的根节点 } } cout< * _CreateTree(const T* a, size_t size, size_t& index, const T& invalid) { BinaryTreeNode * root = NULL; if (index < size && a[index] != invalid) { root = new BinaryTreeNode (a[index]); root->_left = _CreateTree(a, size, ++index, invalid); root->_right = _CreateTree(a, size, ++index, invalid); } return root; } void _DestroyTree(BinaryTreeNode * root) { if (NULL == root) { return; } if (NULL == root->_left && NULL == root->_right) { delete root; root = NULL; return; } _DestroyTree(root->_left); _DestroyTree(root->_right); delete root; } BinaryTreeNode * _CopyTree(BinaryTreeNode * root) { if (NULL == root) { return NULL; } BinaryTreeNode * newRoot = new BinaryTreeNode (root->_data); newRoot->_left = _CopyTree(root->_left); newRoot->_right = _CopyTree(root->_right); return newRoot; } void _PreOrderTraverse(BinaryTreeNode * root) { if (NULL == root) { return; } cout< _data<<" "; _PreOrderTraverse(root->_left); _PreOrderTraverse(root->_right); } void _InOrderTraverse(BinaryTreeNode * root) { if (NULL == root) { return; } _InOrderTraverse(root->_left); cout< _data<<" "; _InOrderTraverse(root->_right); } void _PostOrderTraverse(BinaryTreeNode * root) { if (NULL == root) { return; } _PostOrderTraverse(root->_left); _PostOrderTraverse(root->_right); cout< _data<<" "; } //_Size方法1: /*size_t _Size(BinaryTreeNode * root) { if (NULL == root) { return; } return _Size(root->left) + _Size(root->_right) + 1; }*/ //_Size方法2:(存在线程安全问题) /*size_t _Size(BinaryTreeNode * root) { static size_t size = 0; if (NULL == root) { return 0; } else { ++size; } _Size(root->_left); _Size(root->_right); return size; }*/ //_Size方法3: void _Size(BinaryTreeNode * root, size_t& size) { if (NULL == root) { return; } else { ++size; } _Size(root->_left, size); _Size(root->_right, size); } size_t _Depth(BinaryTreeNode * root) { if (NULL == root) { return 0; } size_t leftDepth = _Depth(root->_left); size_t rightDepth = _Depth(root->_right); return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1; } void _LeafSize(BinaryTreeNode * root, size_t& leafSize) { if (NULL == root) { return; } if (NULL == root->_left && NULL == root->_right) { ++leafSize; return; } _LeafSize(root->_left, leafSize); _LeafSize(root->_right, leafSize); } size_t _GetKLevel(BinaryTreeNode * root, const size_t& k) { assert(k > 0); if (NULL == root) { return 0; } if (k == 1) { return 1; } return _GetKLevel(root->_left, k-1) + _GetKLevel(root->_right, k-1); } protected: BinaryTreeNode * _root; }; void BinaryTreeTest() { int a[] = {1, 2, 3, '#', '#', 4, '#', '#', 5, 6}; BinaryTree t(a, sizeof(a)/sizeof(a[0]), '#'); cout<<"递归前序遍历:"; t.PreOrderTraverse(); cout<<"递归中序遍历:"; t.InOrderTraverse(); cout<<"递归后序遍历:"; t.PostOrderTraverse(); cout<<"非递归前序遍历:"; t.PreOrderTraverse_NonR(); cout<<"非递归中序遍历:"; t.InOrderTraverse_NonR(); cout<<"非递归后序遍历:"; t.PostOrderTraverse_NonR(); cout<<"Size:"< t2(t); cout<<"t2:"; t2.PreOrderTraverse(); BinaryTree t3; t3 = t2; cout<<"t3:"; t3.PreOrderTraverse(); } int main() { BinaryTreeTest(); return 0; }
生成的二叉树如下图:
为天坛街道等地区用户提供了全套网页设计制作服务,及天坛街道网站建设行业解决方案。主营业务为成都网站建设、做网站、天坛街道网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
测试结果:
文章题目:C++实现二叉树
标题路径:http://pwwzsj.com/article/ihojpo.html