C++实现二叉树基本操作详解 - C/C++编程 - 软件开发资源站

首页 > 软件编程 > C/C++编程 > C++实现二叉树基本操作详解

C++实现二叉树基本操作详解
类别：C/C++编程作者：码皇来源：互联网点击：

这篇文章主要为大家详细介绍了C++实现二叉树基本操作，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

树是一种重要的非线性数据结构，二叉树是树型结构的一种重要类型。本学年论文介绍了二叉树的定义，二叉树的存储结构，二叉树的相关术语，以此引入二叉树这一概念，为展开二叉树的基本操作做好理论铺垫。二叉树的基本操作主要包含以下几个模块：二叉树的遍历方法，计算二叉树的结点个数，计算二叉树的叶子结点个数，二叉树深度的求解等内容。

前序遍历（递归&非递归）

访问根节点
前序访问左子树
前序访问右子树

//前序非递归 void PrevOrder() {
stack<Node*> s;
Node *cur = _root;
while (cur || !s.empty()) {
while (cur) {
cout << cur->_data << " ";
s.push(cur);
cur = cur->_left;
}
//此时当前节点的左子树已遍历完毕 Node *tmp = s.top();
s.pop();
cur = tmp->_right;
}
cout << endl;
}
//前序递归 void PrevOrderR() {
_PrevOrder(_root);
cout << endl;
}
void _PrevOrder(Node *root) {
if (root == NULL) //必须有递归出口！！！ return;
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}

中序遍历（递归&非递归）

中序访问左子树
访问根节点
中序访问右子树

//中序非递归 void InOrder() {
stack<Node*> s;
Node *cur = _root;
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 InOrderR() {
_InOrder(_root);
cout << endl;
}
void _InOrder(Node *root) {
if (root == NULL) return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}

后序遍历（递归&非递归）

//后序非递归 //后序遍历可能会出现死循环，所以要记录下前一个访问的节点 void PostOrder() {
stack<Node*> 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 << tmp->_data << " ";
prev = tmp;
s.pop();
}
}
cout << endl;
}
//后序递归 void PostOrderR() {
_PostOrder(_root);
cout << endl;
}
void _PostOrder(Node *root) {
if (root == NULL) return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}

层序遍历

从根节点开始，依次访问每层结点。
利用队列先进先出的特性，把每层结点从左至右依次放入队列。

void LevelOrder() //利用队列！！！ {
queue<Node*> q;
Node *front = NULL;
//1.push根节点 if (_root) {
q.push(_root);
}
//2.遍历当前节点，push当前节点的左右孩子，pop当前节点 //3.遍历当前节点的左孩子，再遍历右孩子，循环直至队列为空 while (!q.empty()) {
front = q.front();
cout << front->_data << " ";
if (front->_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<class T>struct BinaryTreeNode{
T _data;
BinaryTreeNode *_left;
BinaryTreeNode *_right;
BinaryTreeNode(const T& d) :_data(d) , _left(NULL) , _right(NULL) {
}
}
;
template<class T>class BinaryTree{
public: typedef BinaryTreeNode<T> 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>& t) :_root(NULL) {
_root = _CopyTree(t._root);
}
BinaryTree<T>& operator=(const BinaryTree<T>& 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<Node*> s;
Node *cur = _root;
while (cur || !s.empty()) {
while (cur) {
cout << cur->_data << " ";
s.push(cur);
cur = cur->_left;
}
//此时当前节点的左子树已遍历完毕 Node *tmp = s.top();
s.pop();
cur = tmp->_right;
}
cout << endl;
}
//前序递归 void PrevOrderR() {
_PrevOrder(_root);
cout << endl;
}
//中序非递归 void InOrder() {
stack<Node*> s;
Node *cur = _root;
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 InOrderR() {
_InOrder(_root);
cout << endl;
}
//后序非递归 //后序遍历可能会出现死循环，所以要记录下前一个访问的节点 void PostOrder() {
stack<Node*> 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 << tmp->_data << " ";
prev = tmp;
s.pop();
}
}
cout << endl;
}
//后序递归 void PostOrderR() {
_PostOrder(_root);
cout << endl;
}
void LevelOrder() //利用队列！！！ {
queue<Node*> q;
Node *front = NULL;
//1.push根节点 if (_root) {
q.push(_root);
}
//2.遍历当前节点，push当前节点的左右孩子，pop当前节点 //3.遍历当前节点的左孩子，再遍历右孩子，循环直至队列为空 while (!q.empty()) {
front = q.front();
cout << front->_data << " ";
if (front->_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 < n && arr[index] != invalid) {
root = new Node(arr[index]);
index++;
root->_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 << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
void _InOrder(Node *root) {
if (root == NULL) return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
void _PostOrder(Node *root) {
if (root == NULL) return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
size_t _Size(Node *root) {
if (root == NULL) return 0;
else return _Size(root->_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;
}
;

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。

您可能感兴趣的文章:

C++二叉树结构的建立与基本操作
c++二叉树的几种遍历算法
二叉树遍历非递归 C++实现代码
探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)
C++实现二叉树遍历序列的求解方法
C++非递归建立二叉树实例
C++实现二叉树非递归遍历方法实例总结
C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法
C++实现查找二叉树中和为某一值的所有路径的示例
C++非递归队列实现二叉树的广度优先遍历

相关热词搜索： C++ 二叉树

上一篇：C++二叉树实现词频分析功能
下一篇：C++选择排序算法实例详解

C++实现二叉树基本操作详解 类别：C/C++编程 作者：码皇 来源：互联网 点击：

您可能感兴趣的文章:

C++实现二叉树基本操作详解
类别：C/C++编程作者：码皇来源：互联网点击：