Data Structure--二叉树的链式结构及实现

墨蓝 2022-10-31 05:26 138阅读 0赞

### 二叉树链式结构 ###

*  二叉树链式结构的遍历
 *   *  前序遍历(NLR)
     *  中序遍历(LNR)
     *  后序遍历(LRN)
     *   *  (1)链式的具体结构
         *  (2)链式的接口声明
         *  (3)链式的接口实现
         *   *  1.通过前序遍历的数组创建二叉树
             *  2.前序遍历
             *  3.中序遍历
             *  4.后序遍历
             *  5.求节点数
             *  6.求叶子节点数
             *  7.求第K层的节点
             *  8.查找节点
             *  9.销毁二叉树
             *  10.层序遍历
             *  11.是否为完全二叉树

# 二叉树链式结构的遍历 #

这里的**N(根) L(左子树) R(右子树)**

## 前序遍历(NLR) ##

访问根结点的操作发生在遍历其左右子树之前  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

## 中序遍历(LNR) ##

访问根结点的操作发生在遍历其左右子树之中（间）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]

## 后序遍历(LRN) ##

访问根结点的操作发生在遍历其左右子树之后  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]

### (1)链式的具体结构 ###

结构挺简单的,只是有一个指向左边的节点和右边的节点

typedef char DataType;		//字符型定义
    
    typedef struct BNode{ 
    
    	DataType _data;			//数据
    	struct BNode* _left;	//左子树
    	struct BNode* _right;	//右子树
    }BNode;

### (2)链式的接口声明 ###

//1.通过前序遍历的数组创建二叉树
    BNode* creatBTree(DataType arr[], int* idx);
    //2.前序遍历
    void preOrder(BNode* root);
    //3.中序遍历
    void inOrder(BNode* root);
    //4.后序遍历
    void postOrder(BNode* root);
    //5.求节点数
    int bTreeSize(BNode* root);
    //6.求叶子节点数
    int bTreeLeafSize(BNode* root);
    //7.求第K层的节点
    int bTreeKSize(BNode* root,int k);
    //8.查找节点
    BNode* bTreeFind(BNode* root, DataType ch);
    //9.销毁二叉树
    void bTreeDestory(BNode** root);
    //10.层序遍历
    void bTreeLevelOrder(BNode* root);
    //11.是否为完全二叉树
    int isCompleteBtree(BNode* root);

### (3)链式的接口实现 ###

#### 1.通过前序遍历的数组创建二叉树 ####

也可以通过其他的,只不过对于前序遍历有顺序,比较方便.  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]

// 字符串: ABD##E#H##CF##G##
    BNode* creatBTree(DataType arr[], int* idx){ 
    	
    	if (arr[*idx] == '#'){ 		//#为空
    		
    		(*idx)++;				//循环到下一个
    		return NULL;			//返回空
    	}
    	else{ 
    		//创建以当前为根的子树
    		BNode* root = (BNode*)malloc(sizeof(BNode));		//动态开辟空间
    		root->_data = arr[*idx];							//如果找到,将这个,直接赋予 
    		++(*idx);			//循环
    		 
    		root->_left=creatBTree(arr, idx);		//左子树递归创建
    		root->_right = creatBTree(arr, idx);	//右子树递归创建
    		return root;
    	}
    }

#### 2.前序遍历 ####

void preOrder(BNode* root){ 
    	
    	if (root){ 						//在这个数据存在的时候,按照我们刚在讲过的进行前序遍历
    		//根 左子树 右子树
    		printf("%c ", root->_data);
    		preOrder(root->_left);		//左子树递归
    		preOrder(root->_right);		///右子树递归
    	}
    }

#### 3.中序遍历 ####

void inOrder(BNode* root){ 
    	if (root){ 
    		//左子树 根 右子树 //根据我们在前面讲过的方式进行
    		inOrder(root->_left);
    		printf("%c ", root->_data);
    		inOrder(root->_right);
    	}
    }

#### 4.后序遍历 ####

void postOrder(BNode* root){ 		//同上,比较简单,不过多注释
    	if (root){ 
    		//左子树 右子树 根
    		postOrder(root->_left);
    		postOrder(root->_right);
    		printf("%c ", root->_data);
    	}
    }

#### 5.求节点数 ####

int bTreeSize(BNode* root){ 
    	
    	if (root == NULL)		//判空
    		return 0;
    	//root左子树+右子树+1
    	return bTreeSize(root->_left) + bTreeSize(root->_right) + 1;
    }

#### 6.求叶子节点数 ####

int bTreeLeafSize(BNode* root){ 
    	
    	if (root == NULL)		//判空
    		return 0;
    	else if (root->_left == NULL&&root->_right == NULL)	//如果其中一个为空,则为1
    		return 1;
    	//左右子树的叶子和
    	return bTreeLeafSize(root->_left) + bTreeLeafSize(root->_right);	//左右分别递归
    }

#### 7.求第K层的节点 ####

int bTreeKSize(BNode* root,int k){ 
    	
    	if (root == NULL)	
    		return 0;
    	if (k == 1)		//如果问第一层,则为1
    		return 1;
    	//左右子树第K-1层节点和
    	return bTreeKSize(root->_left, k - 1) + bTreeKSize(root->_right, k - 1);	//递归分别循环
    }

#### 8.查找节点 ####

BNode* bTreeFind(BNode* root, DataType ch){ 
    	
    	BNode* node;	
    	if (root == NULL)	
    		return NULL;
    		
    	if (root->_data == ch)		//如果头是要找的直接输出
    		return root;
    		
    	//左子树
    	node= bTreeFind(root->_left, ch);	//左子树寻找
    	if (node)	//看是否在
    		return node;
    	//右子树
    	return bTreeFind(root->_right, ch);		//右子树直接输出 
    }

#### 9.销毁二叉树 ####

void bTreeDestory(BNode** root){ 
    	
    	bTreeDestory(&(*root)->_left);	//左子树递归 
    	bTreeDestory(&(*root)->_right);	//右子树递归
    	free(*root);	//释放空间
    	*root == NULL;	//头指针转为空
    }

#### 10.层序遍历 ####

这里借用了队列的代码来进行实现

void bTreeLevelOrder(BNode* root){ 
    
    	//借助队列保存节点
    	Queue q;
    	queueInit(&q);		//初始化队列
    	//根节点存入队列
    	if (root)
    		queuePush(&q, root);	//存入队列
    	//便利队列中获得每一个节点
    	while (!queueEmpty(&q)){ 	//判空及存在
    		
    		//获取队头元素
    		BNode* front = queueFront(&q);
    		//出队
    		queuePop(&q);
    
    		printf("%d ",front->_data);	//打印元素
    
    		//保存对头元素的左右孩子节点
    		if (front->_left)
    			queuePush(&q, front->_left);		//先对左边进行插入,再对右边进行插入
    		if (front->_right)
    			queuePush(&q, front->_right);
    	}
    	printf("\n");
    }

#### 11.是否为完全二叉树 ####

是否为完全二叉树:可以将二叉树存储于队列中,在出现NULL的时候出队停止,在剩下的元素中如果有非空的,就判定不是完全二叉树,如果都为空,则判定为完全二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 6]  
上面已经解释清楚了,直接上代码:

int isCompleteBtree(BNode* root){ 
    	
    	Queue q;
    	queueInit(&q);	//调用了队列
    	
    	if (root)
    		queuePush(&q, root);	//存在就入队
    	while (!queueEmpty(&q)){ 
    		
    		//获取队头元素
    		BNode* front = queueFront(&q);		//先获取队头
    		queuePop(&q);		//在出队
    		//左右孩子入队
    		if (front){ 		//注意,左右依次进入
    
    			queuePush(&q, front->_data);
    			queuePush(&q, front->_right);
    		}
    		else
    			break;
    	}
    	//查看剩余元素中是否有非空节点
    	while (!queueEmpty(&q)){ 		//重点,看是否有非空的节点
    		
    		BNode* front = queueFront(&q);
    		if (front)
    			//如果剩余元素中存在非空节点,则比连续
    			return 0;
    	}
    	//所有的都连续
    	return 1;
    }

解释的很清楚了,对于最后两个接口引用了队列,我就不详细说明了,不清楚的朋友可以链接: [点击这里][Link 1]进行回顾一下,多敲代码,一起加油!!!

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221024/66e00e5f01db43c1a490980feb713227.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221024/7002ee81de344d3b8f1efb3cda462542.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221024/f33b98e5976c46aa881de656a57a6a2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]: /images/20221024/42170767f7274323adcd0b1541fa1537.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 4]: /images/20221024/20a7b22e7f20406bbaabd5ecfb802937.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 5]: /images/20221024/f830dac9dd92472f9d9c9226b5707ab7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 6]: /images/20221024/78209b9381064842aa1f4f0e40dfa179.png
[Link 1]: https://blog.csdn.net/weixin_46554582/article/details/113874587