数据结构 — 二叉树的基本操作实现(递归算法)

时间：2022-01-18 17:32:07
我们直接切入主题相信大家都应该知道什么叫二叉树吧。二叉树里面有几个常见的操作，他们分别是构造二叉树，前序遍历，中序 遍历，后序遍历，还有 求树的叶子结点，树的深度，树中第K层的节点个数，树中结点的个数，以及在树中查找一个结点。 注意这里大部分都是用递归实现的！！ （也就是这篇文章是入门的，非递归我还会写一个博客） 好了现在开始，我们一个一个的解决他们吧。 科普： 所谓的前序遍历，中序遍历，后序遍历分别代表着什么？ 数据结构 — 二叉树的基本操作实现(递归算法) 

template<class T>
struct BinaryTreeNode
{
BinaryTreeNode<T>* _letf;
BinaryTreeNode<T>* _right;
T _data;
BinaryTreeNode(const T& x)
:_letf(NULL)
, _right(NULL)
, _data(x)
{}
};
这是我定义的一个二叉树的结点。接下来 typedef BinaryTreeNode<T> Node;也就是接下来我们看到的每一个Node表示的就是一个二叉树的结点。

构造二叉树

在这里invalid就是所谓的非法值，而index就是数组的下标。 比如:int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; 这里的invalid就是'#'. 


BinaryTree():_root(NULL){}BinaryTree(T* a, size_t n, const T& invalid){size_t index = 0;_root = CreateTree(a, n, invalid, index);}//注意这里的index 要使用引用， 若是没有使用 上一层递归里面的++index 对上一层没有任何影响.//构建二叉树表Node* CreateTree(T* a, size_t n, const T& invalid, size_t& index){Node* root = NULL;if (index < n && a[index] != invalid){root = new Node(a[index]);root->_letf = CreateTree(a, n, invalid, ++index);root->_right = CreateTree(a, n, invalid, ++index);}return root;}
在这里我用一个图来还原实现过程，因为涉及递归那么我就少说话多画图： 
 
 
数据结构 — 二叉树的基本操作实现(递归算法) 
 
 
 

这里呢，按照代码一步一步的在图中移动，相信你会理解的，毕竟我这么笨的人都理解了。
 
 




二叉树的前序遍历
 
 
 
 
 
 

//前序遍历
void _prevOrder(Node* root)
{
if (root == NULL)
{
return ;
}
cout << root->_data << " ";
_prevOrder(root->_letf);
_prevOrder(root->_right);

}
 
图解： 
 

数据结构 — 二叉树的基本操作实现(递归算法)
 

 

 

 

 

 

二叉树的中序遍历
 
 
 
 


 

 

//中序遍历
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_letf);
cout << root->_data << " ";
_InOrder(root->_right);
}
 

 
这里和前序遍历很相似，我就不画图了 
 

 

 

二叉树的后序遍历
 
 
 
 
 
 

//后序遍历
void PosOrder()
{
return _PosOrder(_root);
}
void _PosOrder(Node* root)
{
if (root == NULL)
{
return;
}
_PosOrder(root->_letf);
_PosOrder(root->_right);
cout << root->_data <<" ";
}
 

图解:
 
数据结构 — 二叉树的基本操作实现(递归算法) 

 

 


 

二叉树的层序遍历
 
 
 
 
 
 
 

void _LevelOrder(Node* root)
{
queue<Node*> q;
if (root != NULL)
{
q.push(root);
while (!q.empty())
{
Node* front = q.front();
cout << front->_data << " ";
if (front->_letf)
{
q.push(front->_letf);
}
if (front->_right)
{
q.push(front->_right);
}

q.pop();
}
}
}
这里层序遍历就是少数没办法用递归实现的函数，在这里它借助了队列-/-，具体的过程: 
 
数据结构 — 二叉树的基本操作实现(递归算法) 

 

 

二叉树叶子结点个数
 
 
 
 
 
 


在这里就要对问题进行分解： 
 
1.这里所有的叶子结点其实就是 左孩子里面的叶子结点个数+右孩子里面的叶子节点个数 
 
2.当你把每一个结点看做根节点时，一层一层的把叶子结点总数就统计出来了 
 
(这里当你为叶子节点是你只返回1就好) 
 
 

size_t _LeafSize(Node* root)
{
if (root == NULL)
{
return 0;
}
if (root->_letf == NULL &&root->_right == NULL)
{
return 1;
}
size_t i = _LeafSize(root->_letf);
size_t j = _LeafSize(root->_right);
return i + j;
}
 

 
 

二叉树深度
 
 
 
 
 
 

size_t _Depth(Node* root)
{
if (root == NULL)
{
return 0;
}
else
{
size_t i = _Depth(root->_letf);
size_t j = _Depth(root->_right);
if (i > j)
{
return i + 1;
}
else
{
return j + 1;
}
}
}
 
图解：

 
 
数据结构 — 二叉树的基本操作实现(递归算法) 
 

 

 

二叉树总结点数
 
 
 
 
 
 
 
这里也是把主问题分解成无数个子问题： 

 


1.对于根节点来说它的总节点个数，就是左孩子和右孩子结点的个数加上自己的总和 也就是  左孩子总结点数 + 1 + 右孩 子总结点2.当你使用递归时也就是每一个结点都可以看成根节点，所以就是每个结点的左孩子+1+右孩子总结点个数.
size_t _Size(Node* root)
{
if (root == NULL)
{
return 0;
}
size_t i = _Size(root->_letf);
size_t j = _Size(root->_right);
return i + j + 1;
}


 

二叉树第K层节点个数
 
 
 


 

size_t _GetKLevel(Node* root, size_t k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}

return _GetKLevel(root->_letf, k - 1) + _GetKLevel(root->_right, k - 1);
}
 

 

二叉树查找节点
 
 
 
 
 
 

Node* _find(Node* root,const T& x)
{
if (root == NULL)
{
return NULL;
}
if (root->_data == x)
{
return root;
}
Node* ret = _find(root->_letf, x);
if (ret)
{
return ret;
}
return _find(root->_right, x);
}
 
 
实现代码： 
 

#include<iostream>
#include<Windows.h>
#include<queue>
using namespace std;

template<class T>
struct BinaryTreeNode
{
BinaryTreeNode<T>* _letf;
BinaryTreeNode<T>* _right;
T _data;
BinaryTreeNode(const T& x)
:_letf(NULL)
, _right(NULL)
, _data(x)
{}
};


template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(T* a, size_t n, const T& invalid)
{
size_t index = 0;
_root = CreateTree(a, n, invalid, index);
}
BinaryTree(const BinaryTree<T>& t);
BinaryTree<T>& operator = (const BinaryTree<T>& t);

//前序遍历
void  PrevOrder()
{
return _prevOrder(_root);
}
//中序遍历
void InOrder()
{
return _InOrder(_root);
}

//后序遍历
void PosOrder()
{
return _PosOrder(_root);
}

//层序遍历
void LevelOrder()
{
return _LevelOrder(_root);
}

//尺寸大小
size_t Size()
{
return _Size(_root);
}

//叶子结点
size_t LeafSize()
{
return _LeafSize(_root);
}

//第K个结点的节点个数
size_t GetKLevel(size_t k)
{
return _GetKLevel(_root, k);
}

//树深度

size_t Depth()
{
return _Depth(_root);
}

//查找

Node* find(const T& x)
{
return _find(_root,x);
}

protected:

//第K层的节点数

size_t _GetKLevel(Node* root, size_t k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}

return _GetKLevel(root->_letf, k - 1) + _GetKLevel(root->_right, k - 1);
}

//查找

Node* _find(Node* root,const T& x)
{
if (root == NULL)
{
return NULL;
}
if (root->_data == x)
{
return root;
}
Node* ret = _find(root->_letf, x);
if (ret)
{
return ret;
}
return _find(root->_right, x);
}

//深度

size_t _Depth(Node* root)
{
if (root == NULL)
{
return 0;
}
else
{
size_t i = _Depth(root->_letf);
size_t j = _Depth(root->_right);
if (i > j)
{
return i + 1;
}
else
{
return j + 1;
}
}
}

//叶子结点求解

size_t _LeafSize(Node* root)
{
if (root == NULL)
{
return 0;
}
if (root->_letf == NULL &&root->_right == NULL)
{
return 1;
}
size_t i = _LeafSize(root->_letf);
size_t j = _LeafSize(root->_right);
return i + j;
}

//层序遍历

void _LevelOrder(Node* root)
{
queue<Node*> q;
if (root != NULL)
{
q.push(root);
while (!q.empty())
{
Node* front = q.front();
cout << front->_data << " ";
if (front->_letf)
{
q.push(front->_letf);
}
if (front->_right)
{
q.push(front->_right);
}

q.pop();
}
}
}

//总成员数

size_t _Size(Node* root)
{
if (root == NULL)
{
return 0;
}
size_t i = _Size(root->_letf);
size_t j = _Size(root->_right);
return i + j + 1;
}

//后序遍历
void _PosOrder(Node* root)
{
if (root == NULL)
{
return;
}
_PosOrder(root->_letf);
_PosOrder(root->_right);
cout << root->_data <<" ";
}

//中序遍历
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_letf);
cout << root->_data << " ";
_InOrder(root->_right);
}

//前序遍历
void _prevOrder(Node* root)
{
if (root == NULL)
{
return ;
}
cout << root->_data << " ";
_prevOrder(root->_letf);
_prevOrder(root->_right);

}

//注意这里的index 要使用引用， 若是没有使用 上一层递归里面的++index 对上一层没有任何影响.

Node* CreateTree(T* a, size_t n, const T& invalid, size_t& index)
{
Node* root = NULL;
if (index < n && a[index] != invalid)
{
root = new Node(a[index]);
root->_letf = CreateTree(a, n, invalid, ++index);
root->_right = CreateTree(a, n, invalid, ++index);
}
return root;
}
protected:

Node* _root;
size_t index;
size_t invalid;
};

void Test1()
{
int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTree<int> t1(array, sizeof(array) / sizeof(array[0]), '#');
t1.PrevOrder();
//t1.InOrder();
//t1.PosOrder();
//cout<<t1.Size()<<" ";
//t1.LevelOrder();
//cout<<t1.LeafSize();
//cout<<t1.Depth();
//cout<<(t1.find(3));
//cout<<t1.GetKLevel(3);
}


标签：
相关文章