二叉树的基本操作、遍历（递归和非递归）、结点数

2024-01-12 14:46:34

若有错误，请大佬们斧正，谢谢。

如果觉得写的还可以，动动小手点个赞，关注一下呀！

目录

二叉树

创建二叉树

二叉树的遍历

二叉树的层次遍历

树的深度（高度）

关于二叉树的结点

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

完整代码如下

进行测试，结果截图

二叉树

二叉树是度不超过 2 的 有序 树，是另一种树形结 构 特点：每个结点至多只有两颗子树；二叉树的 子树有左右之分，其次序不能任意颠倒 性质1：在二叉树的第 i层上至多有 2的(i-1)次方 个结点 性质2：深度为k 的二叉树上至多有 2的(k-1)次方 个结点 性质3：设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个度为0的结点，则有： n0 = n 2+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的左子树的深度Lh i -其右子树的深度Rh i 等于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;
}

​

进行测试，结果截图

二叉树的基本操作、遍历（递归和非递归）、结点数

 

若有错误，请大佬们斧正，谢谢。

觉得写的还可以，动动小手点个赞，关注一下呀！

上一篇：数据结构--二叉树--创建,复制,计算高度,叶子结点总数,叶子总数--c++


下一篇：C语言 - 数据结构 - 二叉树的层次遍历 c语言实现