首先二叉树的节点定义如下: struct BinaryNode { BinaryNode *_left; BinaryNode *_right; T _data; BinaryNode( T data ) :_data(data), _left( NULL), _right(NULL ) {}; }; 二叉树的结构以及接口如下 template<class T> class BinaryTree { typedef BinaryNode <T> Node; public: BinaryTree() :_head( NULL) {}; BinaryTree( const T * a, size_t size, const T & valiue) ~BinaryTree() BinaryTree( BinaryTree &b ) void PrevOder() void InOder() void PostOder() private: public: void LevalOder() size_t depth() size_t size() size_t learsize() void _LevalOder(BinaryNode <T> *root); size_t _depth(BinaryNode <T> *root); void _size(BinaryNode <T> *root, int *p); void _leafsize(BinaryNode <T> *root, size_t *p); int Leafsize(BinaryNode <T> *root); void PrevOder_Nor(); void InOder_Nor(); void PostOder_Nor(); void Distory(Node *_root) Node* _Copy(Node *cur); private: BinaryNode<T > *_root; }; 二叉树的建立(构造函数) BinaryTree( const T * a, size_t size, const T & valiue) { size_t index = 0; _root = _CreatTree( a, size , index, valiue); } BinaryNode<T >* _CreatTree(const T* a, size_t size, size_t &index, const T &valiue) { BinaryNode<T > *root = NULL; if (index < size&& a[index ] != valiue) { root = new BinaryNode <T>(a[index]); root->_left = _CreatTree(a, size , ++index, valiue); root->_right = _CreatTree(a, size , ++index, valiue); } return root; } 二叉树的销毁(析构函数) ~BinaryTree() { Distory(_root); cout << " ~BinaryTree()" << endl; } void Distory(Node *_root) { if (_root == NULL) return; Distory( _root->_left); Distory( _root->_right); if (_root ) delete _root ; _root == NULL ; } 二叉树的拷贝(拷贝构造) BinaryTree( BinaryTree &b ) { _root = _Copy( b._root); } BinaryNode<T >* BinaryTree< T>::_Copy(Node *cur) { if (cur == NULL) return NULL ; Node *tmp = new Node(cur->_data); tmp->_left=_Copy( cur->_left); tmp->_right=_Copy( cur->_right); return tmp; } 求叶子节点个数(两种方法) 一: int BinaryTree <T>::Leafsize( BinaryNode<T > *root) { int count; if (root == NULL) count = 0; else if (root->_left == NULL&&root ->_right == NULL) { count = 1; } else count = Leafsize(root ->_left) + Leafsize(root->_right); return count; } 二: void BinaryTree <T>::_leafsize( BinaryNode<T > *root, size_t * p) { if (root != NULL) { _leafsize( root->_left,p ); _leafsize( root->_right,p ); if (root ->_left == NULL&& root->_right == NULL ) { ++ *p; } } } 二叉树前序遍历递归 void _PrevOder(BinaryNode <T> * root) { if (root == NULL) return; cout << root->_data << " " ; _PrevOder( root->_left); _PrevOder( root->_right); } 二叉树前序遍历非递归 void BinaryTree <T>::PrevOder_Nor() { BinaryNode<T > *cur = _root; stack<BinaryNode <T>*> s; if (cur == NULL ) return; s.push(cur); while (!s.empty()) { BinaryNode<T > *tmp = s.top(); cout << tmp->_data << " "; s.pop(); if (tmp->_right) { s.push(tmp->_right); } if (tmp->_left) { s.push(tmp->_left); } } cout << endl; } 二叉树层序遍历(队列实现) void BinaryTree <T>::_LevalOder( BinaryNode<T > *root) { deque<BinaryNode <T>*> q; q.push_back( root); while (q.size()) { BinaryNode<T > *pNode = q.front(); q.pop_front(); cout << pNode->_data << " "; if (pNode->_left) { q.push_back(pNode->_left); } if (pNode->_right) { q.push_back(pNode->_right); } } } 二叉树中序遍历递归 void _InOder(BinaryNode <T> * root) { if (root == NULL) return; _InOder( root->_left); cout << root->_data << " " ; _InOder( root->_right); } 二叉树中序遍历非递归 void BinaryTree <T>::InOder_Nor() { if (_root == NULL ) return; Node *cur = _root; stack<Node *> s; while (cur||!s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node *tmp = s.top(); cout << tmp->_data << " "; s.pop(); cur = tmp->_right; } cout << endl; } 二叉树后序遍历递归 void _PostOder(BinaryNode <T> * root) { if (root == NULL) return; _PostOder( root->_left); _PostOder( root->_right); cout << root->_data << " " ; } 二叉树后序遍历非递归 void BinaryTree <T>::PostOder_Nor() { if (_root == NULL ) return; Node *cur = _root; stack<Node *> s; Node *prev = NULL ; while (cur||!s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node *tmp = s.top(); if (tmp->_right == NULL || tmp->_right == prev) { cout << tmp->_data << " " ; s.pop(); prev = tmp; } else { cur = tmp->_right; } } cout << endl; } 二叉树的深度 size_t BinaryTree <T>::_depth( BinaryNode<T > *root) { int hleft; int hright; int max; if (root ) { hleft = _depth( root->_left); hright = _depth( root->_right); max = hleft > hright ? hleft : hright; return max + 1; } else { return 0; } } 二叉树的大小 size_t size() { int count = 0; _size(_root,&count); return count; } void BinaryTree <T>::_size( BinaryNode<T > *root,int *p) { if (root ) { ++(* p); _size( root->_left, p ); _size( root->_right, p ); } return ; }
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
当前题目:数据结构之二叉树(构造拷贝构造以及前序中序后续三种遍历方法)-创新互联
标题链接:https://www.cdcxhl.com/article34/dpgsse.html
成都网站建设公司_创新互联,为您提供响应式网站、品牌网站制作、网站设计、自适应网站、关键词优化、品牌网站设计
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联