这篇文章主要为大家详细介绍了C++实现二叉树基本操作，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
树是一种重要的非线性数据结构，二叉树是树型结构的一种重要类型。本学年论文介绍了二叉树的定义，二叉树的存储结构，二叉树的相关术语，以此引入二叉树这一概念，为展开二叉树的基本操作做好理论铺垫。二叉树的基本操作主要包含以下几个模块：二叉树的遍历方法，计算二叉树的结点个数，计算二叉树的叶子结点个数，二叉树深度的求解等内容。
前序遍历（递归&非递归）
- 访问根节点
- 前序访问左子树
- 前序访问右子树
//前序非递归 void PrevOrder() { stack s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { cout <_data <_left; } //此时当前节点的左子树已遍历完毕 Node *tmp = s.top(); s.pop(); cur = tmp->_right; } cout << endl; } //前序递归 void <strong style="color:transparent">来源gaodai#ma#com搞@@代~&码网</strong>PrevOrderR() { _PrevOrder(_root); cout << endl; } void _PrevOrder(Node *root) { if (root == NULL) //必须有递归出口！！！ return; cout <_data <_left); _PrevOrder(root->_right); }
中序遍历（递归&非递归）
- 中序访问左子树
- 访问根节点
- 中序访问右子树
//中序非递归 void InOrder() { stack s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } //此时当前节点的左子树已遍历完毕 Node *tmp = s.top(); cout <_data <_right; } cout << endl; } //中序递归 void InOrderR() { _InOrder(_root); cout <_left); cout <_data <_right); }
后序遍历（递归&非递归）
//后序非递归 //后序遍历可能会出现死循环，所以要记录下前一个访问的节点 void PostOrder() { stack 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 << endl; } //后序递归 void PostOrderR() { _PostOrder(_root); cout <_left); _PostOrder(root->_right); cout <_data << " "; }
层序遍历
从根节点开始，依次访问每层结点。
利用队列先进先出的特性，把每层结点从左至右依次放入队列。
void LevelOrder() //利用队列！！！ { queue q; Node *front = NULL; //1.push根节点 if (_root) { q.push(_root); } //2.遍历当前节点，push当前节点的左右孩子，pop当前节点 //3.遍历当前节点的左孩子，再遍历右孩子，循环直至队列为空 while (!q.empty()) { front = q.front(); cout <_data <_left) q.push(front->_left); if (front->_right) q.push(front->_right); q.pop(); } cout << endl; }
求二叉树的高度
size_t Depth() { return _Depth(_root); } size_t _Depth(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else { size_t leftDepth = _Depth(root->_left) + 1; size_t rightDepth = _Depth(root->_right) + 1; return leftDepth > rightDepth ? leftDepth : rightDepth; } }
求叶子节点的个数
size_t LeafSize() { return _LeafSize(_root); } size_t _LeafSize(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else return _LeafSize(root->_left) + _LeafSize(root->_right); }
求二叉树第k层的节点个数
size_t GetKLevel(int k) { return _GetKLevel(_root, k); } size_t _GetKLevel(Node *root, int k) { if (root == NULL) return 0; else if (k == 1) return 1; else return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1); }
完整代码如下：
template struct BinaryTreeNode { T _data; BinaryTreeNode *_left; BinaryTreeNode *_right; BinaryTreeNode(const T& d) :_data(d) , _left(NULL) , _right(NULL) {} }; template class BinaryTree { public: typedef BinaryTreeNode Node; BinaryTree() :_root(NULL) {} BinaryTree(T *arr, size_t n, const T& invalid) { size_t index = 0; _root = _CreateBinaryTree(arr, n, invalid, index); } BinaryTree(const BinaryTree& t) :_root(NULL) { _root = _CopyTree(t._root); } BinaryTree& operator=(const BinaryTree& t) { if (this != t) { Node *tmp = new Node(t._root); if (tmp != NULL) { delete _root; _root = tmp; } } return *this; } ~BinaryTree() { _DestroyTree(_root); cout << endl; } //前序非递归 void PrevOrder() { stack s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { cout <_data <_left; } //此时当前节点的左子树已遍历完毕 Node *tmp = s.top(); s.pop(); cur = tmp->_right; } cout << endl; } //前序递归 void PrevOrderR() { _PrevOrder(_root); cout << endl; } //中序非递归 void InOrder() { stack s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } //此时当前节点的左子树已遍历完毕 Node *tmp = s.top(); cout <_data <_right; } cout << endl; } //中序递归 void InOrderR() { _InOrder(_root); cout << endl; } //后序非递归 //后序遍历可能会出现死循环，所以要记录下前一个访问的节点 void PostOrder() { stack 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 << endl; } //后序递归 void PostOrderR() { _PostOrder(_root); cout << endl; } void LevelOrder() //利用队列！！！ { queue q; Node *front = NULL; //1.push根节点 if (_root) { q.push(_root); } //2.遍历当前节点，push当前节点的左右孩子，pop当前节点 //3.遍历当前节点的左孩子，再遍历右孩子，循环直至队列为空 while (!q.empty()) { front = q.front(); cout <_data <_left) q.push(front->_left); if (front->_right) q.push(front->_right); q.pop(); } cout << endl; } size_t Size() { return _Size(_root); } size_t LeafSize() { return _LeafSize(_root); } size_t GetKLevel(int k) { return _GetKLevel(_root, k); } size_t Depth() { return _Depth(_root); } Node* Find(const T& d) { return _Find(_root, d); } protected: Node* _CreateBinaryTree(T *arr, size_t n, const T& invalid, size_t& index) { Node *root = NULL; if (index _left = _CreateBinaryTree(arr, n, invalid, index); index++; root->_right = _CreateBinaryTree(arr, n, invalid, index); } return root; } Node* _CopyTree(Node *root) { Node *newRoot = NULL; if (root) { newRoot = new Node(root->_data); newRoot->_left = _CopyTree(root->_left); newRoot->_right = _CopyTree(root->_right); } return newRoot; } void _DestroyTree(Node *root) { if (root) { _Destroy(root->_left); _Destroy(root->_right); delete root; } } void _PrevOrder(Node *root) { if (root == NULL) //必须有递归出口！！！ return; cout <_data <_left); _PrevOrder(root->_right); } void _InOrder(Node *root) { if (root == NULL) return; _InOrder(root->_left); cout <_data <_right); } void _PostOrder(Node *root) { if (root == NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout <_data <_left) + _Size(root->_right) + 1; } size_t _LeafSize(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else return _LeafSize(root->_left) + _LeafSize(root->_right); } size_t _GetKLevel(Node *root, int k) { if (root == NULL) return 0; else if (k == 1) return 1; else return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1); } size_t _Depth(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else { size_t leftDepth = _Depth(root->_left) + 1; size_t rightDepth = _Depth(root->_right) + 1; return leftDepth > rightDepth ? leftDepth : rightDepth; } } Node* _Find(Node *root, const T& d) { if (root == NULL) return NULL; else if (root->_data == d) return root; else if (Node *ret = _Find(root->_left, d)) return ret; else _Find(root->_right, d); } protected: Node *_root; };
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持gaodaima搞代码网。
以上就是C++实现二叉树基本操作详解的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C++实现二叉树基本操作详解
转载请注明原文链接：C++实现二叉树基本操作详解
