二叉树的基本操作

举报
代码不会敲 发表于 2022/05/08 11:41:35 2022/05/08
【摘要】 目录二叉树创建二叉树二叉树的遍历二叉树的层次遍历树的深度（高度）关于二叉树的结点判断完全二叉树、满二叉树完整代码如下进行测试，结果截图 二叉树二叉树是度不超过2的有序树，是另一种树形结构特点：每个结点至多只有两颗子树；二叉树的子树有左右之分，其次序不能任意颠倒性质1：在二叉树的第i层上至多有2的(i-1)次方个结点性质2：深度为k的二叉树上至多有2的(k-1)次方个结点性质3：设二叉树中有n...

目录

二叉树

创建二叉树

二叉树的遍历

二叉树的层次遍历

树的深度（高度）

关于二叉树的结点

判断完全二叉树、满二叉树

完整代码如下

进行测试，结果截图



 二叉树

二叉树是度不超过2的有序树，是另一种树形结构
特点：每个结点至多只有两颗子树；二叉树的子树有左右之分，其次序不能任意颠倒
性质1：在二叉树的第i层上至多有2的(i-1)次方个结点
性质2：深度为k的二叉树上至多有2的(k-1)次方个结点
性质3：设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个度为0的结点，则有：
n0 = n2+1
性质4.：具有n个结点的完全二叉树的深度为 k=log2(n+1)（向上取整） 或k＝ log2(n) （向下取整） +1        -----log2是以2为底的对数
性质5： 将完全二叉树自上而下，自左向右地编号，树根的编号为1。
对于编号为i的结点X有：
1. 若i＝1，则X是根；若i>1, 则X的双亲的编号为  i/2（向下取整）;
2. 若2i>n，则X无左孩子，X为叶结点；若X有左 孩子，则X左孩子的编号为2i；
3. 若2i+1>n，则X无右孩子；若X有右孩子，则X 右孩子的编号为2i＋1；
性质6：n个结点的二叉树共有n＋1个空指针

二叉树的链式存储结构----二叉链表
​​​​
​ 
typedef struct BiTNode{
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;


创建二叉树

​


这里代码是运用递归思想，先序创建二叉树，以‘#’表示空；

如创建上图二叉树，应输入：ABD#G##E##C#FH#I###

void CreateBiTree(BiTree &bt){
    char ch;
    cin >> ch;
    if (ch == '#') 
		bt=NULL;
    else
	{
        bt = new BiTNode;
        bt -> data = ch;
        CreateBiTree (bt -> lchild);
        CreateBiTree (bt -> rchild);
    }
}

二叉树的遍历

先序遍历：根----左----右

中序遍历：左----根----右

后序遍历：左----右----根

遍历二叉树的基本操作是访问结点，不论哪种次序进行遍历， 对于含有n个结点的二叉树，其时间复杂度均为O(n)。
对于非递归遍历算法所需辅助空间为遍历过程中栈的最大容量， 即树的深度，最坏情况下为n，所以其空间复杂度也为O(n)。
已知二叉树的先序遍历序列和中序遍历序列、 中序遍历序列 和后序遍历序列以及层次遍历序列和中序遍历序列，均可唯一地确定一棵二叉树；
已知二叉树的先序遍历序列和后序遍历序列不能唯一地确定一棵二叉树。

先序、中序、后序的递归遍历和非递归遍历 
//遍历递归算法 --先序
void PreOrderTraverse1(BiTree bt){
	if (bt)
	{
		cout << bt -> data << " ";   //根 
		PreOrderTraverse1(bt -> lchild);  //左 
		PreOrderTraverse1(bt -> rchild);  //右 
	}
}
//遍历非递归算法 --先序     利用栈 
void PreOrderTraverse2(BiTree bt){   
	stack <BiTree> S;
	BiTree p = bt;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push(p);
			cout << p -> data << " ";
			p = p -> lchild;
		}
		if (!S.empty())
		{
			p = S.top();
			S.pop();
			p = p -> rchild; 
		}
	}
}


//遍历递归算法 --中序 
void InOrderTraverse1(BiTree bt){
	if(bt)
	{
		InOrderTraverse1 (bt -> lchild);   //左 
		cout << bt -> data << " ";        //根 
		InOrderTraverse1 (bt -> rchild);   //右 
	}
} 
//遍历非递归算法 --中序     利用栈
void InOrderTraverse2(BiTree bt){   
	stack <BiTree> S;
	BiTree p = bt;
	while (p || !S.empty())
	{
		if (p)
		{
			S.push(p);
			p = p -> lchild;
		}
		else
		{
			p = S.top();
			S.pop();
			cout << p -> data << " ";
			p = p -> rchild; 
		}
	}
}


//遍历递归算法 --后序 
void PostOrderTraverse1(BiTree bt){
	if(bt)
	{
		PostOrderTraverse1 (bt -> lchild);   //左  
		PostOrderTraverse1 (bt -> rchild);   //右 
		cout << bt -> data << " ";  	   //根
	}
} 
//遍历非递归算法 --中序     利用栈
void PostOrderTraverse2(BiTree bt){   
	stack <BiTree> S1, S2;
	BiTree p = NULL;
	S1.push(bt);
	while (!S1.empty())
	{
		p = S1.top();
		S1.pop();
		S2.push(p);
		if (p -> lchild)
			S1.push(p -> lchild);
		if (p -> rchild)
			S1.push(p -> rchild);
	}
	while (!S2.empty())
	{
		p = S2.top();
		cout << p -> data << " ";
		S2.pop();
	}
}

二叉树的层次遍历

思想：

  1. 空树，结束。
  2. 初始化一个空队列Q，树根入队；
  3. 对头e元素出队，访问e；
  4. 如果e有左孩子，则左孩子入队；
  5. 如果e右左孩子，则右孩子入队；
  6. 如果对列不空，执行3；否则结束。
//层次遍历 --利用队列 
void LevelOrderTraverse(BiTree bt){
	queue <BiTree> Q;
	BiTNode *p = bt;
	if (bt)
	{
		Q.push (bt);
		while (!Q.empty())
		{
			p = Q.front ();    //队头元素出队列 
			cout << p -> data << " ";
			if (p -> lchild) 
				Q.push (p -> lchild);  //非空左孩子入队列 
			if (p -> rchild) 
				Q.push (p -> rchild);  //非空右孩子入队列 
			Q.pop ();
		}
	}
}

树的深度（高度）

思想：由二叉树的定义可知，若二叉树为空，则深度为0， 否则其深度为左右子树的较大者加1。

int Height(BiTree bt){
    if(bt == NULL)
        return 0;
    else
    {
        int m = Height (bt -> lchild);
        int n = Height (bt -> rchild);
        if(m > n)
			return (m + 1);
        else 
			return (n + 1);
    }
}

关于二叉树的结点

结点：遍历过的每一个，大家都懂

叶子节点：该结点无左右孩子为叶子结点

//二叉树中所有结点数
int CountTree (BiTree bt){
	if (bt == NULL) 
		return 0;
	else 
		return CountTree (bt -> lchild) + CountTree(bt -> rchild) + 1; 
} 
//叶子结点数
int CountLeaf (BiTree bt){
	if (! bt)
		return 0;
	if (! bt -> lchild && ! bt -> rchild)
		return 1;
	else 
		return CountLeaf (bt -> lchild) + CountLeaf (bt -> rchild);
} 
//判断度为1的节点数
int Count_1Node(BiTree bt){
	if (!bt)
		return 0;
	if ((!bt -> lchild) && (bt -> rchild) || (bt -> lchild) && (!bt -> rchild))
		return Count_1Node(bt -> lchild) + Count_1Node(bt -> rchild) + 1;
    else
        return Count_1Node(bt -> lchild) + Count_1Node(bt -> rchild);
}

判断完全二叉树、满二叉树

完全二叉树：将深度为k，有n个结点的二叉树自上而下，自左向 右进行编号，编号与深度为k的满二叉树中前n个结点一 致。

特点：

1）每个结点i的左子树的深度Lhi-其右子树的深度Rhi 等于0或1，即叶结点只可能出现在层次最大或次最大的两层上。
2）完全二叉树结点数n满足2的(k-1)次方 < n < 2的k次方 -1
3）满二叉树一定是完全二叉树，反之不成立。

4）n个结点的完全二叉树中：

度为1的结点数为(n+1)%2

度为0的结点数为 (n+1)/2(向下取整)

度为2的结点数为(n+1)/2(向上取整) -1

5）前k－1层是满的，第k层可以不满，但第k层结点集中在左侧

​

满二叉树：深度为k，结点总数 n = 2的k次方 -1

特点：

1）每一层结点数都达到最大

2）只有度为0和度为2的结点，度为一的结点数 n1 = 0

​

 满二叉树的判断可根据：结点总数 n = 2的k次方 -1  和  度为一的结点数 n1 = 0 进行判断

//判断是否为完全二叉树 
bool Is_Comp(BiTree bt)
{
	bool res = true;
	if (!bt) 
		return res;
	std:: queue <BiTree> Q;
	Q.push(bt);
	while (!Q.empty())
	{
		bt = Q.front();
		Q.pop();
		if (!bt)
			break;
		Q.push (bt -> lchild);
		Q.push (bt -> rchild);
	}
	while (!Q.empty())
	{
		bt = Q.front();
		Q.pop();
		if (bt)
		{
			res = false;
			break;
		}
	}
	return res;
}

完整代码如下

​
#include<bits/stdc++.h>
using namespace std;
//节点结构 
typedef struct BiTNode{
	char data;
	struct BiTNode *lchild, *rchild;  //左右孩子指针 
}BiTNode, *BiTree; 

//先序创建二叉树
void CreateBiTree(BiTree &bt){
    char ch;
    cin >> ch;
    if (ch == '#') 
		bt=NULL;
    else
	{
        bt = new BiTNode;    //  bt = (BiTNode*) malloc (sizeof(BiTNode)) // 
        bt -> data = ch;
        CreateBiTree (bt -> lchild);
        CreateBiTree (bt -> rchild);
    }
}

//遍历递归算法 --先序
void PreOrderTraverse1(BiTree bt){
	if (bt)
	{
		cout << bt -> data << " ";   //根 
		PreOrderTraverse1 (bt -> lchild);  //左 
		PreOrderTraverse1 (bt -> rchild);  //右 
	}
}

//遍历非递归算法 --先序     利用栈 
void PreOrderTraverse2(BiTree bt){   
	stack <BiTree> S;
	BiTree p = bt;
	while (p || !S.empty())
	{
		while (p)
		{
			S.push (p);
			cout << p -> data << " ";
			p = p -> lchild;
		}
		if (!S.empty ())
		{
			p = S.top ();
			S.pop ();
			p = p -> rchild; 
		}
	}
}

//遍历递归算法 --中序 
void InOrderTraverse1(BiTree bt){
	if (bt)
	{
		InOrderTraverse1 (bt -> lchild);   //左 
		cout << bt -> data << " ";        //根 
		InOrderTraverse1 (bt -> rchild);   //右 
	}
} 

//遍历非递归算法 --中序     利用栈
void InOrderTraverse2(BiTree bt){   
	stack <BiTree> S;
	BiTree p = bt;
	while (p || !S.empty())
	{
		if (p)
		{
			S.push (p);
			p = p -> lchild;
		}
		else
		{
			p = S.top ();
			S.pop ();
			cout << p -> data << " ";
			p = p -> rchild; 
		}
	}
}

//遍历递归算法 --后序 
void PostOrderTraverse1(BiTree bt){
	if (bt)
	{
		PostOrderTraverse1 (bt -> lchild);   //左  
		PostOrderTraverse1 (bt -> rchild);   //右 
		cout << bt -> data << " ";  	   //根
	}
} 
//遍历非递归算法 --中序     利用栈
void PostOrderTraverse2(BiTree bt){   
	stack <BiTree> S1, S2;
	BiTree p = NULL;
	S1.push (bt);
	while (!S1.empty ())
	{
		p = S1.top ();
		S1.pop ();
		S2.push (p);
		if (p -> lchild)
			S1.push (p -> lchild);
		if (p -> rchild)
			S1.push (p -> rchild);
	}
	while (!S2.empty ())
	{
		p = S2.top ();
		cout << p -> data << " ";
		S2.pop ();
	}
}



//层次遍历 --利用队列 
void LevelOrderTraverse(BiTree bt){
	queue <BiTree> Q;
	BiTNode *p = bt;
	if (bt)
	{
		Q.push (bt);
		while (!Q.empty ())
		{
			p = Q.front ();    //队头元素出队列 
			cout << p -> data << " ";
			if (p -> lchild) 
				Q.push (p -> lchild);  //非空左孩子入队列 
			if (p -> rchild) 
				Q.push (p -> rchild);  //非空右孩子入队列 
			Q.pop ();
		}
	}
}

//树的高度
int Height(BiTree bt){
    if (bt == NULL)
        return 0;
    else
    {
        int m = Height (bt -> lchild);
        int n = Height (bt -> rchild);
        if(m > n)
			return (m + 1);
        else 
			return (n + 1);
    }
}

//二叉树中所有结点数  
int CountTree (BiTree bt){
	if (bt == NULL) 
		return 0;
	else 
		return CountTree (bt -> lchild) + CountTree (bt -> rchild) + 1; 
} 

//叶子结点数  --遍历 若该节点无左右孩子则为叶子节点 --2
int CountLeaf (BiTree bt){
	if (!bt)
		return 0;
	if (!bt -> lchild && ! bt -> rchild)
		return 1;
	else 
		return CountLeaf (bt -> lchild) + CountLeaf (bt -> rchild);
} 

//判断度为1的节点数
int Count_1Node(BiTree bt){
	if (!bt)
		return 0;
	if ((!bt -> lchild) && (bt -> rchild) || (bt -> lchild) && (!bt -> rchild))
		return Count_1Node (bt -> lchild) + Count_1Node (bt -> rchild) + 1;
    else
        return Count_1Node (bt -> lchild) + Count_1Node (bt -> rchild);
}

//判断是否为完全二叉树 
bool Is_Comp(BiTree bt)
{
	bool res = true;
	if (!bt) 
		return res;
	std:: queue <BiTree> Q;
	Q.push (bt);
	while (!Q.empty())
	{
		bt = Q.front ();
		Q.pop();
		if (!bt)
			break;
		Q.push (bt -> lchild);
		Q.push (bt -> rchild);
	}
	while (!Q.empty ())
	{
		bt = Q.front ();
		Q.pop ();
		if (bt)
		{
			res = false;
			break;
		}
	}
	return res;
}

int main(){
	BiTNode *bt;
	int leaves;
	printf("创建二叉树：");
	CreateBiTree (bt);
	printf("(递归  )先序遍历：");
	PreOrderTraverse1 (bt);
	printf("\n(非递归)先序遍历：");
	PreOrderTraverse2 (bt); 
	printf("\n(递归  )中序遍历：");
	InOrderTraverse1 (bt);
	printf("\n(非递归)中序遍历：");
	InOrderTraverse2 (bt);
	printf("\n(递归  )后序遍历：");
	PostOrderTraverse1 (bt);
	printf("\n(非递归)后序遍历：");
	PostOrderTraverse2(bt);
	printf("\n层次遍历：");
	LevelOrderTraverse (bt);
	printf("\n树的高度为：");
	cout << Height (bt);
	printf("\n所有结点个数为：");
	cout << CountTree (bt);
	printf("\n叶结点个数为：");
	cout << CountLeaf (bt); 
	printf("\n(是:1;否:0)满二叉树：");
	if (Count_1Node (bt) == 0 && CountTree (bt) == pow (2, (float)Height (bt)) - 1) 
		printf("1");
	else
		printf("0");
	printf("\n(是:1;否:0)完全二叉树：");
	cout << Is_Comp(bt);
	
	return 0;
}

​

进行测试，结果截图

​

在此页面也可查看

​https://blog.csdn.net/weixin_57780057/article/details/121232843?spm=1001.2014.3001.5502

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
二叉树 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入