二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分。
二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个节点。
二叉排序树的定义:
一棵空树,或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
——百度百科
二叉树的操作是数据结构课程的一大重点,其小点很多,我大概整理了一些我想到的,如有遗漏,还请指出。
在本文中,我以二叉排序树为例进行演示,也差不多。
目录
声明
添加
建立与销毁
查找
删除
打印树
遍历
先序遍历
递归
非递归
中序遍历
递归
非递归
后序遍历
递归
非递归
层次遍历
层数查找
存在该元素
不存在该元素
树的高度
元素个数
判断是否是满二叉树
判断是否是完全二叉树
源代码
声明
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
typedef struct node {
int data;
node* left;
node* right;
}node;
class BST {
public:
node* root;
BST();//构建二叉树
~BST();//析构函数
node* DestroyBiTree(node* p);//销毁二叉树
void app(int x, node*& p);//添加元素
bool search(int x, node* p);//寻找元素
bool del(int x, node*& p);//删除元素
void PreOrder(node* p);//递归先序遍历
void InOrder(node* p);//递归中序遍历
void PostOrder(node* p);//递归后序遍历
void LevelOrder();//层次遍历
void PreOrder2();//非递归先序遍历
void InOrder2();//非递归中序遍历
void PostOrder2();//非递归后序遍历
void print(node* r, int layer);//打印树
void getlelve(node* p, int x, int l, int& xp, int& lp);//树内不存在,寻找最相似值的层数
int getlelve(node* p, int x, int l);//树内存在寻找层数
bool IsComplete();//判断是否是完全二叉树
int height(node* p);//计算树的高度
void count(node* p,int &sum);//统计节点数量
bool IsFull();//判断是否是满二叉树
};
添加
二叉排序树的元素添加就是根据数据大小选择合适位置。
void BST::app(int x, node*&p)
{
if (p == NULL)//添加到空节点
{
p = new node;
p->data = x;
p->left = p->right = NULL;
cout << "添加成功" << endl;
}
else//根据元素大小选择合适位置
{
if (x > p->data)
app(x, p->right);
else
app(x, p->left);
}
}
建立与销毁
建立就是多个添加元素,销毁就是空间释放
BST::BST()
{
root = NULL;
fstream file("text.txt", ios::in);
if (file.fail())
{
cout << "文件打开失败" << endl;
exit(0);
}
int n;
file >> n;
while (n--)
{
int x;
file >> x;
app(x, root);
}
}
node* BST::DestroyBiTree(node* p)
{
if (p != NULL)
{
p->left = DestroyBiTree(p->left); // 销毁左子树
p->right = DestroyBiTree(p->right); // 销毁右子树
free(p); // 销毁根结点
return NULL;
} // end if ( T )
return NULL;
}
查找
查找元素也是根据大小选择查找分支
bool BST::search(int x,node*p)
{
if (p == NULL)
{
return false;
}
if (p->data == x)
return true;
if (x > p->data)
search(x, p->right);
else
search(x, p->left);
}
叶节点删除
与查找基本相同,就是多了一步删除节点,释放空间,还有对父节点孩子指针的更改,所以我们需要有一个返回值用来标记是否是删除的点,非叶节点的删除还需要对子树进行判断,有四种情况,稍微有点复杂,还没来得及写,回头补上。
bool BST::del(int x, node*& p)
{
if (p == NULL)
{
cout << "该数不存在" << endl;
return false;
}
if (p->data == x)
{
if(p->left!=NULL||p->right!=NULL)
{
cout<<"非叶节点"<<endl;
return false;
}
cout << "删除成功" << endl;
return true;
}
if (x > p->data)
{
if (del(x, p->right))
{
free(p->right);
p->right = NULL;
return false;
}
}
else
{
if (del(x, p->left))
{
free(p->left);
p->left = NULL;
return false;
}
}
return false;
}
打印树
横向打印树,递归,根据递归层数在前方留出相应的层数,然后打印数据,横向的话最上方是纵向的最右边,所以先进右节点,后进左节点。
void BST::print(node* r, int layer)
{
if (r->right != NULL)
{
print(r->right, layer + 1);
}
for (int i = 0; i < layer; i++)//根据递归层数留出空间
cout << " |";
cout << setw(4) << r->data << '|' << endl;
if (r->left != NULL)
{
print(r->left, layer + 1);
}
}
效果如图
遍历
先序、中序、后序遍历的递归算法很简单,不过多介绍,仅提供代码。
而非递归算法基本思路就是用栈模拟递归。
先序遍历
先输出本身节点数据,然后输出左孩子数据,最后输出右孩子数据
递归
void BST::PreOrder(node* p)
{
if (p == NULL)
return;
else
{
cout << p->data<<' ';
PreOrder(p->left);
PreOrder(p->right);
}
}
非递归
先序遍历是将左子树全部访问完之后才访问右子树,我们访问完当前节点后,先将右孩子压栈,再压左孩子,就可以实现先访问左子树的目的,这个思路还是比较简单的。
1.先将根节点入栈
2.将栈顶节点的右孩子和左孩子压栈,跳出栈顶结点
3.重复2,直至栈空
void BST::PreOrder2()
{
if (root == NULL)
return;
stack<node*>s;//栈,先进的后出来
s.push(root);
while (!s.empty())
{
node* p = s.top();
//cout << s.top()->data << endl;
cout << s.top()->data << ' ';
s.pop();
if (p->right != NULL)//所以先压右节点
s.push(p->right);
if (p->left != NULL)
s.push(p->left);
}
}
中序遍历
先输出左孩子数据,再输出本身节点数据,最后输出右孩子数据
递归
void BST::InOrder(node* p)
{
if (p == NULL)
return;
else
{
InOrder(p->left);
cout << p->data<<' ';
InOrder(p->right);
}
}
非递归
我们需要先访问左孩子,依次递推,我们可以得到访问顺序:最先访问的点是最左边的点,然后访问其父节点,然后访问其父节点的右子树,访问顺序与之前的相同。代码思路如下:
1.遍历左子树,向左走到头,期间访问到的所有结点压栈
2.栈顶元素出栈输出,然后按照步骤一访问其右子树
3.重复1,2直至栈空,且遍历指针p为NULL(如果栈空直接退出的话,根节点的右子树访问不了)
void BST::InOrder2()
{
if (root == NULL)
return;
stack<node*>s;
node* p = root;
while (p != NULL || !s.empty())
{
while (p != NULL) // 遍历左子树,向左走到头
{
s.push(p);
//cout << s.top()->data << endl;
p = p->left;
}
if (!s.empty())
{
p = s.top();
s.pop(); // 回退到双亲结点
cout << p->data << ' '; // 访问结点
p = p->right; // 进入当前结点的右子树
}
}
}
后序遍历
先输出左孩子数据,在输出右孩子数据,最后输出本身节点数据
递归
void BST::PostOrder(node* p)
{
if (p == NULL)
return;
else
{
PostOrder(p->left);
PostOrder(p->right);
cout << p->data<<' ';
}
}
非递归
每一个节点都必须在其两个孩子节点都输出完成后才能输出,但是我们访问其子节点势必要先访问该节点,所以我们需要做一个标记用来标记其子节点是否输出完成。
1.遍历左子树,向左走到头,期间访问到的所有结点压栈,标记栈都押入0表示子节点未输出完成
2.判断标记栈顶元素是否为1,若是,两个栈都弹栈,并输出数据栈弹出节点的数据
3.访问数据栈栈顶节点的右子树,并将标记栈栈顶改为1
4.重复1,2,3直至栈空
void BST::PostOrder2()
{
if (root == NULL)
return;
stack<node*>s;
stack<int>x;//建立标记栈x,用以记录对应节点的孩子节点是否遍历完成
node* p = root->left;
s.push(root);
x.push(0);
while (!s.empty())
{
//访问不等同于输出!!!表示入栈
while (p != NULL) // 遍历左子树,向左走到头
{
s.push(p);
//cout << s.top()->data << endl;
x.push(0);//0代表未访问右子树
p = p->left;
}
while (!s.empty() && x.top() == 1)
{
p = s.top();
s.pop();
x.pop();
cout << p->data << ' '; //访问结点,此时 x为 1,表示右子树访问完毕,故访问根结点
}
if (!s.empty())
{
p = s.top()->right;
x.pop();
x.push(1);//将栈顶的点记为右子树访问完成
}
}
}
层次遍历
一层一层的输出,由左向右,从根节点开始访问,然后访问其子节点,先访问到的先输出,很容易想的队列。
1.根节点入队
2.压入队首节点的子节点
3.出队输出
4.重复2、3直至队空
void BST::LevelOrder()
{
if (root == NULL)
return;
queue<node*>q;
q.push(root);
while (!q.empty())
{
node* p = q.front();
if (p->left != NULL)
q.push(p->left);
if (p->right != NULL)
q.push(p->right);
cout << p->data << ' ';
q.pop();
}
}
层数查找
对于任意正整数x,在二叉排序树中查找,若存在,输出“x存在”和所在的层数;若不存在,输出“x不存在”,同时输出二叉排序树中最接近x的整数值和该数所在的层数。
提前进行判断是否存在,然后用两个函数分别实现两个目的。
存在该元素
直接按照二叉排序树的查找就可以了,加一个表示层数的变量就可以了
int BST::getlelve(node* p, int x, int l)
{
if (p->data == x)
{
cout << x << "存在,在第" << l << "层" << endl;
return l;//有相同的返回其层数
}
if (x > p->data)
return getlelve(p->right, x, l + 1);
else
return getlelve(p->left, x, l + 1);
}
不存在该元素
(x > xp ? x - xp : xp - x) > (x > p->data ? x - p->data : p->data - x)
//当前节点数据比xp与x更相近
void BST::getlelve(node* p, int x, int l, int& xp, int& lp)
{
if (p == NULL)
return;
if ((x > xp ? x - xp : xp - x) > (x > p->data ? x - p->data : p->data - x))
{
lp = l;
xp = p->data;//判断更新最相似的值及其层数
}
getlelve(p->left, x, l + 1, xp, lp);
getlelve(p->right, x, l + 1, xp, lp);
}
树的高度
return height(p->left) > height(p->right) ? height(p->left) + 1 : height(p->right) + 1;
//返回左右子树中更高的高度
int BST::height(node*p)
{
if (p == NULL)
return 0;
return height(p->left) > height(p->right) ? height(p->left) + 1 : height(p->right) + 1;
}
元素个数
遍历统计
void BST::count(node* p,int &sum)
{
if (p == NULL)
return;
else
sum++;
count(p->left, sum);
count(p->right, sum);
}
判断是否是满二叉树
国内教程定义:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的深度为K,且结点总数是(2^k) -1 ,则它就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点,要么它有两个子结点,但是反过来不成立,因为完全二叉树也满足这个要求,但不是满二叉树)
国外(国际)定义:a binary tree T is full if each node is either a leaf or possesses exactly two childnodes.
大意为:如果一棵二叉树的结点要么是叶子结点,要么它有两个子结点,这样的树就是满二叉树。
——百度百科文章来源:https://www.toymoban.com/news/detail-759237.html
满二叉树很好判断,因为我们很轻易就可以得到一个结论,满二叉树的节点个数n与其高度h存在如下公式:n=2^h-1,我们根据这个进行判断就可以了。
bool BST::IsFull()
{
if (root == NULL) return 1;
int sum = 0;
int h = height(root);
count(root, sum);
return sum == pow(2, h) - 1;
}
判断是否是完全二叉树
一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。
——百度百科
完全二叉树的判断稍微麻烦一点,我的思路就是层次遍历时,判断出现空缺的地方前面是否还有空缺,很好理解,根据层次遍历代码进行改动也算简单。文章来源地址https://www.toymoban.com/news/detail-759237.html
bool BST::IsComplete()
{
bool f = 1;//标记,f==0代表出现空缺,f==1代表未出现空缺
queue<node*>q;
q.push(root);
while (!q.empty())//层次遍历,判断每一个节点前面是否出现空缺
{
node* p = q.front();
q.pop();
if (p->left != NULL)
{
q.push(p->left);
if (f == 0)//前面节点右孩子空缺,现节点存在左孩子,非完全二叉树,换层也是一样的
return 0;
}
else
{
//cout << p->data << endl;
f = 0;//左孩子出现空缺
}
if (p->right != NULL)
{
if (f == 0)//现节点左孩子空缺,(前面也可能存在节点出现孩子空缺),现节点存在右孩子,非完全二叉树
return 0;
q.push(p->right);
}
else
{
//cout << p->data << endl;
f = 0;//右孩子出现空缺
}
}
return 1;
}
源代码
#include<iostream>
#include<fstream>
#include<iomanip>
#include<queue>
#include<stack>
using namespace std;
typedef struct node {
int data;
node* left;
node* right;
}node;
class BST {
public:
node* root;
BST();
~BST();
node* DestroyBiTree(node* p);
void app(int x, node*& p);
bool search(int x, node* p);
bool del(int x, node*& p);
void PreOrder(node* p);
void InOrder(node* p);
void PostOrder(node* p);
void LevelOrder();
void PreOrder2();
void InOrder2();
void PostOrder2();
void print(node* r, int layer);
void getlelve(node* p, int x, int l, int& xp, int& lp);//树内不存在,寻找最相似值的层数
int getlelve(node* p, int x, int l);//树内存在寻找层数
bool IsComplete();
int height(node* p);
void count(node* p,int &sum);
bool IsFull();
};
int main()
{
BST t;
t.del(98, t.root);
t.app(98, t.root);
t.print(t.root, 0);
cout << "二叉树高为" << t.height(t.root) << endl;
int sum = 0;
t.count(t.root, sum);
cout << "二叉树结点个数为" << sum << endl;
cout << "中序遍历:"; t.InOrder(t.root); cout << endl;
cout << "中序遍历:"; t.InOrder2(); cout << endl;
cout << "先序遍历:"; t.PreOrder(t.root); cout << endl;
cout << "先序遍历:"; t.PreOrder2(); cout << endl;
cout << "后序遍历:"; t.PostOrder(t.root); cout << endl;
cout << "后序遍历:"; t.PostOrder2(); cout << endl;
cout << "层次遍历:"; t.LevelOrder(); cout << endl;
int x = 16;
if (t.search(x, t.root))
t.getlelve(t.root, x, 1);
else
{
int xp = -999;
int lp = 1;
t.getlelve(t.root, x, 1, xp, lp);
cout << x << "不存在,最接近" << x << "的数为" << xp << "在第" << lp << "层" << endl;
}
if (t.IsComplete())
cout << "完全二叉树" << endl;
else
cout << "非完全二叉树" << endl;
if (t.IsFull())
cout << "满二叉树" << endl;
else
cout << "非满二叉树" << endl;
}
BST::BST()
{
root = NULL;
fstream file("text.txt", ios::in);
if (file.fail())
{
cout << "文件打开失败" << endl;
exit(0);
}
int n;
file >> n;
while (n--)
{
int x;
file >> x;
app(x, root);
}
}
BST::~BST()
{
DestroyBiTree(root);
}
node* BST::DestroyBiTree(node* p)
{
if (p != NULL)
{
p->left = DestroyBiTree(p->left); // 销毁左子树
p->right = DestroyBiTree(p->right); // 销毁右子树
free(p); // 销毁根结点
return NULL;
} // end if ( T )
return NULL;
}
void BST::app(int x, node*&p)
{
if (p == NULL)
{
p = new node;
p->data = x;
p->left = p->right = NULL;
cout << "添加成功" << endl;
}
else
{
if (x > p->data)
app(x, p->right);
else
app(x, p->left);
}
}
bool BST::search(int x,node*p)
{
if (p == NULL)
{
return false;
}
if (p->data == x)
return true;
if (x > p->data)
search(x, p->right);
else
search(x, p->left);
}
bool BST::del(int x, node*& p)
{
if (p == NULL)
{
cout << "该数不存在" << endl;
return false;
}
if (p->data == x)
{
if(p->left!=NULL||p->right!=NULL)
{
cout<<"非叶节点"<<endl;
return false;
}
cout << "删除成功" << endl;
return true;
}
if (x > p->data)
{
if (del(x, p->right))
{
free(p->right);
p->right = NULL;
return false;
}
}
else
{
if (del(x, p->left))
{
free(p->left);
p->left = NULL;
return false;
}
}
return false;
}
void BST::PreOrder(node* p)
{
if (p == NULL)
return;
else
{
cout << p->data<<' ';
PreOrder(p->left);
PreOrder(p->right);
}
}
void BST::InOrder(node* p)
{
if (p == NULL)
return;
else
{
InOrder(p->left);
cout << p->data<<' ';
InOrder(p->right);
}
}
void BST::PostOrder(node* p)
{
if (p == NULL)
return;
else
{
PostOrder(p->left);
PostOrder(p->right);
cout << p->data<<' ';
}
}
void BST::LevelOrder()
{
if (root == NULL)
return;
queue<node*>q;
q.push(root);
while (!q.empty())
{
node* p = q.front();
if (p->left != NULL)
q.push(p->left);
if (p->right != NULL)
q.push(p->right);
cout << p->data << ' ';
q.pop();
}
}
void BST::PreOrder2()
{
if (root == NULL)
return;
stack<node*>s;//栈,先进的后出来
s.push(root);
while (!s.empty())
{
node* p = s.top();
cout << s.top()->data << ' ';
s.pop();
if (p->right != NULL)//所以先压右节点
s.push(p->right);
if (p->left != NULL)
s.push(p->left);
}
}
void BST::InOrder2()
{
if (root == NULL)
return;
stack<node*>s;
node* p = root;
while (p != NULL || !s.empty())
{
while (p != NULL) // 遍历左子树,向左走到头
{
s.push(p);
p = p->left;
}
if (!s.empty())
{
p = s.top();
s.pop(); // 回退到双亲结点
cout << p->data << ' '; // 访问结点
p = p->right; // 进入当前结点的右子树
}
}
}
void BST::PostOrder2()
{
if (root == NULL)
return;
stack<node*>s;
stack<int>x;//建立标记栈x,用以记录对应节点的孩子节点是否遍历完成
node* p = root->left;
s.push(root);
x.push(0);
while (!s.empty())
{
//访问不等同于输出!!!表示入栈
while (p != NULL) // 遍历左子树,向左走到头
{
s.push(p);
//cout << s.top()->data << endl;
x.push(0);//0代表未访问右子树
p = p->left;
}
while (!s.empty() && x.top() == 1)
{
p = s.top();
s.pop();
x.pop();
cout << p->data << ' '; //访问结点,此时 x为 1,表示右子树访问完毕,故访问根结点
}
if (!s.empty())
{
p = s.top()->right;
x.pop();
x.push(1);//将栈顶的点记为右子树访问完成
}
}
}
void BST::print(node* r, int layer)
{
if (r->right != NULL)
{
print(r->right, layer + 1);
}
for (int i = 0; i < layer; i++)
cout << " |";
cout << setw(4) << r->data << '|' << endl;
if (r->left != NULL)
{
print(r->left, layer + 1);
}
}
void BST::getlelve(node* p, int x, int l, int& xp, int& lp)
{
if (p == NULL)
return;
if ((x > xp ? x - xp : xp - x) > (x > p->data ? x - p->data : p->data - x))
{
lp = l;
xp = p->data;//判断更新最相似的值及其层数
}
getlelve(p->left, x, l + 1, xp, lp);
getlelve(p->right, x, l + 1, xp, lp);
}
int BST::getlelve(node* p, int x, int l)
{
if (p->data == x)
{
cout << x << "存在,在第" << l << "层" << endl;
return l;//有相同的返回其层数
}
if (x > p->data)
return getlelve(p->right, x, l + 1);
else
return getlelve(p->left, x, l + 1);
}
bool BST::IsComplete()
{
bool f = 1;//标记,f==0代表出现空缺,f==1代表未出现空缺
queue<node*>q;
q.push(root);
while (!q.empty())//层次遍历,判断每一个节点前面是否出现空缺
{
node* p = q.front();
q.pop();
if (p->left != NULL)
{
q.push(p->left);
if (f == 0)//前面节点右孩子空缺,现节点存在左孩子,非完全二叉树,换层也是一样的
return 0;
}
else
{
//cout << p->data << endl;
f = 0;//左孩子出现空缺
}
if (p->right != NULL)
{
if (f == 0)//现节点左孩子空缺,(前面也可能存在节点出现孩子空缺),现节点存在右孩子,非完全二叉树
return 0;
q.push(p->right);
}
else
{
//cout << p->data << endl;
f = 0;//右孩子出现空缺
}
}
return 1;
}
int BST::height(node*p)
{
if (p == NULL)
return 0;
return height(p->left) > height(p->right) ? height(p->left) + 1 : height(p->right) + 1;
}
void BST::count(node* p,int &sum)
{
if (p == NULL)
return;
else
sum++;
count(p->left, sum);
count(p->right, sum);
}
bool BST::IsFull()
{
if (root == NULL) return 1;
int sum = 0;
int h = height(root);
count(root, sum);
return sum == pow(2, h) - 1;
}
到了这里,关于二叉树基本操作的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!