【代码】C++实现二叉树基本操作及测试用例-创新互联
二叉树是一种常见的数据结构,这里我们需要要注意的是,二叉树的非递归的遍历。
成都创新互联公司主要从事网页设计、PC网站建设(电脑版网站建设)、wap网站建设(手机版网站建设)、成都响应式网站建设公司、程序开发、网站优化、微网站、微信平台小程序开发等,凭借多年来在互联网的打拼,我们在互联网网站建设行业积累了丰富的成都网站制作、成都网站设计、网站设计、网络营销经验,集策划、开发、设计、营销、管理等多方位专业化运作于一体。先序遍历,中序遍历,后序遍历
这三种遍历,如果用非递归的方式实现,我们则需要借助栈这个结构,首先我们需要遍历所有左子树的左节点。进行压栈,完成压栈之后,根据不同的需求,判断是否该继续访问或者弹出亦或者是压入该节点的右子树。
层序遍历
不同于其他的遍历方式,层序遍历是以根节点为开始,依次向下,每层从左到右依次访问。
这里我们需要借助与队列这种数据结构,层层入队,层层出队,完成遍历。
代码如下:
#pragma once #includeusing namespace std; #include #include typedef char DataType; struct BinaryTreeNode//节点结构体 { BinaryTreeNode(DataType data = (DataType)0) :_data(data) , _leftChild(NULL) , _rightChild(NULL) {} DataType _data; BinaryTreeNode* _leftChild; BinaryTreeNode* _rightChild; }; class BinaryTree { typedef BinaryTreeNode _NODE; public: BinaryTree(char* str)//通过先序的字符串构造二插树‘#’为空 { _root = _CreatTree(_root,str); } BinaryTree(const BinaryTree &t) { _root = _Copy(t._root); } BinaryTree operator =(BinaryTree t) { swap(_root, t._root); return *this; } ~BinaryTree() { _Destory(_root); } size_t Size()//求二叉树的大小 { return _Size(_root); } size_t Depth()//求深度 { return _Depth(_root); } void LevelOrder()//层序遍历二叉树 { queue<_NODE*> NodeQueue; _NODE* cur = _root; NodeQueue.push(cur); while (!NodeQueue.empty()) { _NODE*tmp = NodeQueue.front();//取队头 cout << tmp->_data << " ";//访问 NodeQueue.pop(); if (tmp->_leftChild)//左不为空入左,右不为空入右 NodeQueue.push(tmp->_leftChild); if (tmp->_rightChild) NodeQueue.push(tmp->_rightChild); } } void BackOrder_NONREC()//后续非递归遍历 { stack<_NODE*> s; _NODE*prev = NULL; _NODE*cur = _root; while (!s.empty()||cur)//压一颗树的左子树,直到最左 { while (cur) { s.push(cur); cur = cur->_leftChild; } _NODE* top = s.top(); if (top->_rightChild==NULL||top->_rightChild==prev)//若栈顶节点的右节点为空,或者是已经访问过的节点,则不弹出栈顶节点 { visitor(top); prev = top;//将最后一次访问过得节点保存 s.pop(); } else//否则压入以栈顶节的右节点点为根的左子树,直到最左 { cur = top->_rightChild; } } } void InOrder_NONREC()//中序非递归遍历 { stack<_NODE*> s; _NODE*cur = _root; while (!s.empty() || cur) { while (cur)//压一棵树的左节点直到最左,若为空则不进行压栈 { s.push(cur); cur = cur->_leftChild; } _NODE* top = s.top(); if (!s.empty())//访问栈顶节点,将另一颗被压的树,置为栈顶节点的右子树 { visitor(top); s.pop(); cur = top->_rightChild; } } } void PrevOrder_NONREC()//先序非递归遍历 { stack<_NODE*> s; _NODE* cur = NULL; s.push(_root); while (!s.empty()) { cur = s.top();//先访问当前节点 visitor(cur); s.pop(); if (cur->_rightChild)//当前右节点不为空压入 s.push(cur->_rightChild); if (cur->_leftChild) s.push(cur->_leftChild); } cout << endl; } protected: static void visitor(_NODE* cur)//访问函数,为了满足测试,控制台打印数据 { cout << cur->_data << " "; } _NODE* _Copy(_NODE* root) { _NODE* newRoot = NULL; if (root == NULL) return NULL; else { newRoot = new _NODE(root->_data); newRoot->_leftChild = _Copy(root->_leftChild); newRoot->_rightChild = _Copy(root->_rightChild); } return newRoot; } size_t _Depth(_NODE* root) { size_t depth = 0; if (root == NULL) return depth; else { depth = _Depth(root->_leftChild) + 1; size_t newdepth = _Depth(root->_rightChild) + 1; depth = depth > newdepth ? depth : newdepth; } return depth; } size_t _Size(_NODE* root) { if (root==NULL) return 0; else return _Size(root->_leftChild) + _Size(root->_rightChild) + 1; } void _Destory(_NODE* &root) { if (root) { if ((root->_leftChild == NULL) &&(root->_rightChild == NULL)) { delete root; root = NULL; } else { _Destory(root->_leftChild); _Destory(root->_rightChild); _Destory(root); } } } _NODE*_CreatTree(_NODE* root,char* &str) { _NODE*cur = root; if (*str == '#' || *str == 0) { return NULL; } else { cur = new _NODE(*str); cur->_leftChild = _CreatTree(cur->_leftChild, ++str); cur->_rightChild = _CreatTree(cur->_rightChild,++str); } return cur; } protected: _NODE* _root; };
如有不足或疑问希望指正。
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
本文标题:【代码】C++实现二叉树基本操作及测试用例-创新互联
网页URL:http://myzitong.com/article/ipihg.html