C++实现二叉树基本操作详解
树是一种重要的非线性数据结构,二叉树是树型结构的一种重要类型。本学年论文介绍了二叉树的定义,二叉树的存储结构,二叉树的相关术语,以此引入二叉树这一概念,为展开二叉树的基本操作做好理论铺垫。二叉树的基本操作主要包含以下几个模块:二叉树的遍历方法,计算二叉树的结点个数,计算二叉树的叶子结点个数,二叉树深度的求解等内容。
前序遍历(递归&非递归)
- 访问根节点
- 前序访问左子树
- 前序访问右子树
//前序非递归 voidPrevOrder() { stacks; Node*cur=_root; while(cur||!s.empty()) { while(cur) { cout< _data<<""; s.push(cur); cur=cur->_left; } //此时当前节点的左子树已遍历完毕 Node*tmp=s.top(); s.pop(); cur=tmp->_right; } cout< _data<<""; _PrevOrder(root->_left); _PrevOrder(root->_right); }
中序遍历(递归&非递归)
- 中序访问左子树
- 访问根节点
- 中序访问右子树
//中序非递归 voidInOrder() { stacks; Node*cur=_root; while(cur||!s.empty()) { while(cur) { s.push(cur); cur=cur->_left; } //此时当前节点的左子树已遍历完毕 Node*tmp=s.top(); cout< _data<<""; s.pop(); cur=tmp->_right; } cout< _left); cout< _data<<""; _InOrder(root->_right); }
后序遍历(递归&非递归)
//后序非递归 //后序遍历可能会出现死循环,所以要记录下前一个访问的节点 voidPostOrder() { stacks; Node*cur=_root; Node*prev=NULL; while(cur||!s.empty()) { while(cur) { s.push(cur); cur=cur->_left; } Node*tmp=s.top(); if(tmp->_right&&tmp->_right!=prev) { cur=tmp->_right; } else { cout< _data<<""; prev=tmp; s.pop(); } } cout< _left); _PostOrder(root->_right); cout< _data<<""; }
层序遍历
从根节点开始,依次访问每层结点。
利用队列先进先出的特性,把每层结点从左至右依次放入队列。
voidLevelOrder()//利用队列!!! { queueq; Node*front=NULL; //1.push根节点 if(_root) { q.push(_root); } //2.遍历当前节点,push当前节点的左右孩子,pop当前节点 //3.遍历当前节点的左孩子,再遍历右孩子,循环直至队列为空 while(!q.empty()) { front=q.front(); cout< _data<<""; if(front->_left) q.push(front->_left); if(front->_right) q.push(front->_right); q.pop(); } cout< 求二叉树的高度
size_tDepth() { return_Depth(_root); } size_t_Depth(Node*root) { if(root==NULL) return0; elseif(root->_left==NULL&&root->_right==NULL) return1; else { size_tleftDepth=_Depth(root->_left)+1; size_trightDepth=_Depth(root->_right)+1; returnleftDepth>rightDepth?leftDepth:rightDepth; } }求叶子节点的个数
size_tLeafSize() { return_LeafSize(_root); } size_t_LeafSize(Node*root) { if(root==NULL) return0; elseif(root->_left==NULL&&root->_right==NULL) return1; else return_LeafSize(root->_left)+_LeafSize(root->_right); }求二叉树第k层的节点个数
size_tGetKLevel(intk) { return_GetKLevel(_root,k); } size_t_GetKLevel(Node*root,intk) { if(root==NULL) return0; elseif(k==1) return1; else return_GetKLevel(root->_left,k-1)+_GetKLevel(root->_right,k-1); }完整代码如下:
templatestructBinaryTreeNode { T_data; BinaryTreeNode*_left; BinaryTreeNode*_right; BinaryTreeNode(constT&d) :_data(d) ,_left(NULL) ,_right(NULL) {} }; template classBinaryTree { public: typedefBinaryTreeNode Node; BinaryTree() :_root(NULL) {} BinaryTree(T*arr,size_tn,constT&invalid) { size_tindex=0; _root=_CreateBinaryTree(arr,n,invalid,index); } BinaryTree(constBinaryTree &t) :_root(NULL) { _root=_CopyTree(t._root); } BinaryTree &operator=(constBinaryTree &t) { if(this!=t) { Node*tmp=newNode(t._root); if(tmp!=NULL) { delete_root; _root=tmp; } } return*this; } ~BinaryTree() { _DestroyTree(_root); cout< s; Node*cur=_root; while(cur||!s.empty()) { while(cur) { cout< _data<<""; s.push(cur); cur=cur->_left; } //此时当前节点的左子树已遍历完毕 Node*tmp=s.top(); s.pop(); cur=tmp->_right; } cout< s; Node*cur=_root; while(cur||!s.empty()) { while(cur) { s.push(cur); cur=cur->_left; } //此时当前节点的左子树已遍历完毕 Node*tmp=s.top(); cout< _data<<""; s.pop(); cur=tmp->_right; } cout< s; Node*cur=_root; Node*prev=NULL; while(cur||!s.empty()) { while(cur) { s.push(cur); cur=cur->_left; } Node*tmp=s.top(); if(tmp->_right&&tmp->_right!=prev) { cur=tmp->_right; } else { cout< _data<<""; prev=tmp; s.pop(); } } cout< q; Node*front=NULL; //1.push根节点 if(_root) { q.push(_root); } //2.遍历当前节点,push当前节点的左右孩子,pop当前节点 //3.遍历当前节点的左孩子,再遍历右孩子,循环直至队列为空 while(!q.empty()) { front=q.front(); cout< _data<<""; if(front->_left) q.push(front->_left); if(front->_right) q.push(front->_right); q.pop(); } cout< _left=_CreateBinaryTree(arr,n,invalid,index); index++; root->_right=_CreateBinaryTree(arr,n,invalid,index); } returnroot; } Node*_CopyTree(Node*root) { Node*newRoot=NULL; if(root) { newRoot=newNode(root->_data); newRoot->_left=_CopyTree(root->_left); newRoot->_right=_CopyTree(root->_right); } returnnewRoot; } void_DestroyTree(Node*root) { if(root) { _Destroy(root->_left); _Destroy(root->_right); deleteroot; } } void_PrevOrder(Node*root) { if(root==NULL)//必须有递归出口!!! return; cout< _data<<""; _PrevOrder(root->_left); _PrevOrder(root->_right); } void_InOrder(Node*root) { if(root==NULL) return; _InOrder(root->_left); cout< _data<<""; _InOrder(root->_right); } void_PostOrder(Node*root) { if(root==NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout< _data<<""; } size_t_Size(Node*root) { if(root==NULL) return0; else return_Size(root->_left)+_Size(root->_right)+1; } size_t_LeafSize(Node*root) { if(root==NULL) return0; elseif(root->_left==NULL&&root->_right==NULL) return1; else return_LeafSize(root->_left)+_LeafSize(root->_right); } size_t_GetKLevel(Node*root,intk) { if(root==NULL) return0; elseif(k==1) return1; else return_GetKLevel(root->_left,k-1)+_GetKLevel(root->_right,k-1); } size_t_Depth(Node*root) { if(root==NULL) return0; elseif(root->_left==NULL&&root->_right==NULL) return1; else { size_tleftDepth=_Depth(root->_left)+1; size_trightDepth=_Depth(root->_right)+1; returnleftDepth>rightDepth?leftDepth:rightDepth; } } Node*_Find(Node*root,constT&d) { if(root==NULL) returnNULL; elseif(root->_data==d) returnroot; elseif(Node*ret=_Find(root->_left,d)) returnret; else _Find(root->_right,d); } protected: Node*_root; }; 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。