二叉树的创建以及递归与非递归遍历
二叉树先序遍历;(1)先序访问根节点 (2)先序访问左子树 (3)先序访问右子树
创新互联是一家集网站建设,章丘企业网站建设,章丘品牌网站建设,网站定制,章丘网站建设报价,网络营销,网络优化,章丘网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。
二叉树中序遍历;(1)中序访问根节点 (2)中序访问左子树 (3)中序访问右子树
二叉树后序遍历;(1)后序访问根节点 (2)后序访问左子树 (3)后序访问右子树
测试用例:int a[10]={'1','2','3','#','#','4','#','#','5','6'}
代码:
#includeusing namespace std; #include #include template struct BinaryTreeNode { BinaryTreeNode * _left; BinaryTreeNode * _right; T _data; BinaryTreeNode(const T& d) :_left(NULL) ,_right(NULL) ,_data(d) {} }; template class BinaryTree { public: BinaryTree() :_root(NULL) {} BinaryTree(const T* a,size_t size,const T& invalid) { size_t index = 0; _root = _Create(a,size,index,invalid); } //BinaryTree(const BinaryTree & d) //{ // BinaryTreeNode root = NULL; //} BinaryTree & operator = (const BinaryTree & d) { swap(root,d._root ); } void PrevOrder() { _PrevOrder(_root); } void InOrder() { _InOrder(_root); } size_t Size() { _Size(_root); } size_t Depth() { return _Depth(_root); } size_t LeafSize() { return _LeafSize( _root); } void LevelOrder() { _LeavelOrder(); } void PrevOrder_NonR() { _PrevOrder_NonR(); } void InOrder_NonR() { _InOrer_NonR(); } void PostOrder_NonR() { _PostOrder_NonR(); } public: protected: BinaryTreeNode * _Create(const T*a,size_t size,size_t& index,const T& invalid) { BinaryTreeNode *root = NULL; while(index (a[index]); root->_left = _Create(a,size,++index,invalid); root->_right = _Create(a,size,++index,invalid); } return root; } void _PrevOrder(BinaryTreeNode * root) { if(root == NULL) { return; } cout< _data<<" " ; _PrevOrder(root->_left ); _PrevOrder(root->_right); } void _InOrder(BinaryTreeNode * root) { if(root == NULL) { return; } _InOrder (root->_left ); cout< _data<<" " ; _InOrder (root->_right ); } size_t _size(BinaryTreeNode * root) { if(root == NULL) { return 0; } return _Size(root->_left )+_Size(root->_right )+1; } size_t _Depth(BinaryTreeNode * root) { if(root == NULL) { return 0; } int left = _Depth(root->_left )+1; int right = _Depth (root->_right )+1; return (left>right?left:right); } size_t _LeafSize(BinaryTreeNode * root) { if(root == NULL) { return 0; } if(root->_left == NULL && (root->_right == NULL)) { return 1; } return _LeafSize(root->_left)+_LeafSize (root->_right); } void _LeavelOrder() { queue *>q; if(_root) { q.push(_root); } while(!q.empty()) { BinaryTreeNode * front = q.front(); cout< _left) { q.push(_root->_left); } if(_root->_right) { q.push(_root->_right); } q.pop(); } cout< *>s; BinaryTreeNode * cur = _root; while(cur||!s.empty()) { while(cur ) { cout< _data <<" "; s.push(cur); cur = cur->_left ; } if(!s.empty()) { BinaryTreeNode * top = s.top(); cur = top->_right ; s.pop(); } } } void _InOrer_NonR() { stack *> s; BinaryTreeNode * cur = _root; while(cur||!s.empty()) { while(cur) { s.push(cur); cur = cur->_left ; } BinaryTreeNode * Top = s.top(); cout< _data<<" "; cur = Top->_right ; s.pop(); } cout< * cur = _root; stack *>s; BinaryTreeNode * prev = NULL; while(cur||!s.empty()) { while(cur) { s.push(cur); cur = cur->_left ; } BinaryTreeNode * top = s.top(); if(top->_right == NULL||top->_right == prev) { cout< _data <<" "; s.pop(); prev = top; } else cur = top->_right ; //cout< * _root; }; int main() { int a1[10] = {1,2,3,'#','#',4,'#','#',5,6}; BinaryTree b1(a1,10,'#'); //b1.InOrder(); //b1.InOrder_NonR (); //b1.Depth(); //b1.PrevOrder_NonR(); b1.PostOrder_NonR(); system("pause"); return 0; }
文章标题:二叉树的创建以及递归与非递归遍历
本文链接:http://myzitong.com/article/ihcghg.html