二叉树及其相关操作

ゞ浴缸里的玫瑰 2022-01-21 07:39 338阅读 0赞

### 二叉树及其相关操作 ###

*  概念
 *   *  什么是树
     *  二叉树
     *   *  各部分的名称
         *  二叉树的特性
         *  满二叉树
         *  完全二叉树
     *  结构体的表示方式
 *  利用递归方法对二叉树进行操作
 *   *  递归方法核心思想
     *  销毁
     *  获取深度
     *  查找节点
     *  获取全部叶子节点

# 概念 #

## 什么是树 ##

用离散数学中的定义来说，树就是没有简单回路的连通无向图。

如果说链表是一个连一个，入度和出度都为1，  
那么则树就是一个连多个，入度为1，出度可以大于1。

就像下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]

## 二叉树 ##

当一个节点的出度为2，就是指向了两个另外的节点的时候，这样的树就被称为二叉树。

### 各部分的名称 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 1]

### 二叉树的特性 ###

### 满二叉树 ###

满足每一排都是满的的二叉树就是满二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 2]

### 完全二叉树 ###

通俗地来讲，就是排序一定要按照满二叉树来的，也就是按照第一排1个，第二排2个，第三排4个，从左到右慢慢补上的顺序来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 3]

## 结构体的表示方式 ##

和链表相比，又多了个指针而已：

typedef struct BTNode
    {
        
    	ElemType data;
    	struct BTNode* lchild;
    	struct BTNode* rchild;
    } BTNode;

# 利用递归方法对二叉树进行操作 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 4]  
在创建了二叉树之后，只需要知道根节点的指针b，就可以遍历获取整个二叉树了。  
怎么创建先不管，先看怎么操作。

## 递归方法核心思想 ##

一言难尽，先看代码再看图：

void Traversal(BTNode* &b)
    {
        
    	if(b!=NULL)
    	{
        
    		Traversal(b->lchild);
    		Traversal(b->rchild);
    		Do something......			
    	}
    	return ;	
    }

Ps.形参列表里`(BTNode* &b)`那个`&`是引用标志，就是让形参和实参地址相同，操作这个`b`也就是对主函数里的`b`实际进行操作了。  
例如以前写交换函数，用指针：Swap(int\* a, int\* b)；  
现在可以这样写：Swap(int &a, int& b)；

这里只显示了一边的执行过程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 5]  
理解了上面的过程，以下几种操作都变得很简单了。

## 销毁 ##

void DestroyBT(BTNode* &b)
    {
        
    	if(b!=NULL)
    	{
        
    		DestroyBT(b->lchild);     
    		DestroyBT(b->rchild);
    		//删了
    		free(b);
    		b = NULL;
    	}
    }

## 获取深度 ##

int GetDepth(BTNode* b)
    {
        
    	int leftDepth,rightDepth;
    	
    	if(b!=NULL)
    	{
        
    		leftDepth = GetDepth(b->lchild);
    		rightDepth = GetDepth(b->rchild);		
    		
    		//取更深的那层,数值增加1即可
    		return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); 
    	}
    	//如果是叶子节点，就返回0
    	return 0;
    }

获取深度的基本原理也就是递归到底，然后向上走，每走一层，深度加一。  
不过需要注意的是，对于非满二叉树，会存在左右两边深度不一样的情况，需要对比，取大的那个。

## 查找节点 ##

BTNode* FindNode(BTNode* b, ElemType x)
    {
        
    		
    	if(b!=NULL)
    	{
        
    		//如果是当前节点，就返回 
    		if(b->data == x)	return b;
    		//不然的话就向子节点寻找 
    		else	//其实这个else都可以不写的 
    		{
        
    			//先在左子树里找 
    			b=FindNode(b->lchild,x);
    			//如果找到就返回 
    			if(b!=NULL)
    			{
        
    				return b;          //到左右节点里去找 
    			}
    			//不然再去右边找 
    			else
    			{
        
    				return FindNode(b->rchild,x);
    			}
    		}
    	}
    	
    	return NULL;
    }

为了减少运算，我们是从上到下逐个寻找的，所以这里是先"执行操作"，如果没用再"查找子节点"。

## 获取全部叶子节点 ##

void GetLeaf(BTNode* b, int* counter) 
    {
        
    	if(b)
    	{
        
    		if(!(b->lchild) && !(b->rchild)) 
    		{
        
    			(*counter)++;//注意优先级 一定要打括号！！！ 
    		}
    		GetLeaf(b->lchild, counter);
    		GetLeaf(b->rchild, counter);	
    	}	
    }

这个思路也差不多，找到没有左右孩子的节点时候，就让计数器加1即可。这里的if操作卸载GetLeaf方法的前面或者后面都可以。

关于创建我在另外一篇博客专门介绍了。[这里！][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]: /images/20220121/5e214d3274c2480bbc6c20be6eb972f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 1]: /images/20220121/fcd4ed524d3947f18cf037a4be436350.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 2]: /images/20220121/42c342d2f59242d9a577a2de9a2fb404.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 3]: /images/20220121/c0cb917eb73948a29da87a41e84c50d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 4]: /images/20220121/481c25cf915f4346b19a0af1ffa4ed64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70 5]: /images/20220121/04b28703010443149236d87b67b9885f.png
[Link 1]: https://blog.csdn.net/qq_43948583/article/details/92834046