数据结构-二叉树[递归实现]（构造，析构，先序遍历，中序遍历，后续遍历，层次遍历）

心已赠人 2022-05-20 03:53 188阅读 0赞

# 数据结构-二叉树\[递归实现\] #

## 一、二叉树概念 ##

### 1.定义 ###

**二叉树（Binary Tree）**是n（**n不小于0**）个节点组成的有限集合，且满足以下条件之一

（1）**n=0**时，为**空二叉树**（无节点）

（2）**n>0**时，为**非空二叉树**，由一个根节点和两颗**互不相交**的子树（**左子树**，**右子树**）的二叉树构成

### 2.常见的二叉树 ###

#### （1）斜树 ####

所有节点**只有****左子树**或者**右子树**的二叉树

#### （2）满二叉树 ####

**深度为k**，具有**2^k-1**个节点的二叉树

![70][]

#### （3）完全二叉树 ####

具有**n个节点**，**深度为k**的二叉树，并且层次编号为i的节点与同样深度的满二叉树的编号为i的节点**位置完全相同**

![70 1][]

## 二、二叉树的链式储存（递归实现） ##

### 1.二叉链表 ###

struct Bt_Node
    {
    	T Data;//节点数据，T为数据类型
    	Bt_Node* Left_Child;//左孩子节点
    	Bt_Node* Right_Child;//右孩子节点
    };

### 2.二叉树的构造 ###

采用**先序遍历**的方法构造二叉树

int Binary_tree<T>::Create_BTree(Bt_Node<T>* &Tree)  //为了递归实现构造，将私有数据Tree作为该创建递归函数的引用参数
    {
    	T data;
    	cin >> data;
    	if (data == -1)      //-1代表空树
    		Tree = NULL;
    	else
    	{
    		Tree = new Bt_Node<T>;
    		Tree->Data = data;
    		Create_BTree(Tree->Left_Child);//创建左子树
    		Create_BTree(Tree->Right_Child);//创建右子树
    	}
    	return 0;
    }

### 3.二叉树的析构 ###

和链表一样，从上的节点开始释放节点空间，注意**保存该节点左右子树的节点地址**

int Binary_tree<T>::Distory_BTree(Bt_Node<T>* &Tree)
    {
    	if (Tree)			//该根节点非空
    	{
    		//cout << Tree->Data << endl;
    		Bt_Node<T>* Left_Tree = Tree->Left_Child;
    		Bt_Node<T>* Right_Tree = Tree->Right_Child;
    		delete Tree;
    		if (Left_Tree)			//左子树非空则释放
    			Distory_BTree(Left_Tree);
    		if (Right_Tree)			//同
    			Distory_BTree(Right_Tree);
    	}
    	return 0;
    }

## 三、二叉树的遍历 ##

![70 2][]

### 1.先序遍历 ###

**（1）访问根节点 （2）先序遍历左子树 （3）先序遍历右子树**

上图的先序遍历结果：**1 2 3 4 5 6**

#### 实现代码： ####

template<class T>
    void Binary_tree<T>::PreOrder_Op(Bt_Node<T>* &Tree)
    {
    	if (Tree)
    	{
    		cout << Tree->Data << endl;		//先访问根节点
    		PreOrder_Op(Tree->Left_Child);		//访问左子树
    		PreOrder_Op(Tree->Right_Child);	//访问右子树
    	}
    }

### 2.中序遍历 ###

**（1）中序遍历左子树 (2)访问根节点 （3）中序遍历右子树**

上图的先序遍历结果：**3 2 4 1 6 5**

#### 实现代码： ####

template<class T>
    void Binary_tree<T>::InOrder_Op(Bt_Node<T>* &Tree)
    {
    	if (Tree)
    	{
    		InOrder_Op(Tree->Left_Child);		//访问左子树
    		cout << Tree->Data << endl;		//访问根节点
    		InOrder_Op(Tree->Right_Child);		//访问右子树
    	}
    }

### 3.后序遍历 ###

**（1）后序遍历左子树 (2)后序遍历右子树 （3）访问根节点**

上图的先序遍历结果：**3 4 2 6 5 1**

#### 实现代码： ####

template<class T>
    void Binary_tree<T>::PostOrder_Op(Bt_Node<T>* &Tree)
    {
    	if (Tree)
    	{
    		PostOrder_Op(Tree->Left_Child);	//访问左子树
    		PostOrder_Op(Tree->Right_Child);	//访问右子树
    		cout << Tree->Data << endl;		//访问根节点
    	}
    }

### 4.层次遍历 ###

从上到下逐层遍历根节点

上图的先序遍历结果：**1，2 5， 3 4 6**

#### 实现代码： ####

层次遍历采用的方法是**穷举加递归**，先行用i代表所要寻找的层数（从0开始），利用放回值判断该层是否存在

template<class T>
    int Binary_tree<T>::LevelOrder_Op(Bt_Node<T>* &Tree, int Level)
    {
    	if (Level < 0 || !Tree)//该层的根节点为空或者没有找到该层，返回0
    		return 0;
    	if (Level == 0)//该层根节点不空
    	{
    		cout << Tree->Data << " ";
    		return 1;	//访问该节点并返回
    	}
    	return LevelOrder_Op(Tree->Left_Child, Level - 1), LevelOrder_Op(Tree->Right_Child, Level - 1);
    	//还没有到所要访问的层次，从左子树开始往下一层开始检测节点
    }

template<class T>
    void Binary_tree<T>::LevelOrder()
    {
    	for (int i = 0;; i++)		//穷举树的度数（从0开始算）
    	{
    		if (!LevelOrder_Op(Tree, i))	//递归结果为0表示第i层不存在，即树的深度为i，树的根节点为0
    			break;
    		cout << endl;
    	}
    
    	cout << endl;
    }

### MyIdeal : ###

个人觉得递归遍历二叉树在实现上或者脑补上都是挺简单的，递归是一个从**宏逐步细化**的过程！

以中序遍历举个荔枝，每次递归都是重复：**左树，根节点，右树**。那从整棵树去看，就是**先遍历左数（3，2，4）**，**然后访问根节点（1）**，**再而是右树（5，6)**；然后细化，进入左树（3，2，4），那么从**左，中，右遍历就是 3， 2 ， 4**，左树（3，2，4）遍历完了，**回到根节点（1)**,然后右树（5，6），**访问该右树的左（6），根（5），右（空）**，至此完成整个遍历。总之递归就是一个从**宏到一个方向的细分然后再回到宏的过程**。

## 四、二叉树类实现 ##

### 1.编写类的原则和思路 ###

（1）采用**类模板**，为了增加程序数据的兼容性

（2）将创建，删除，遍历的递归操作**全部私有化**，因为递归函数传参肯定用到根节点，私有操作加接口防止树节点被类外读取。

### 2.类的定义 ###

### 3.具体代码 ###

#include<iostream>
    using namespace std;
    template<class T>
    struct Bt_Node
    {
    	T Data;
    	Bt_Node* Left_Child;
    	Bt_Node* Right_Child;
    };
    template<class T>
    class Binary_tree
    {
    private:
    	Bt_Node<T> *Tree;
    	/*内部实现函数*/
    	int Create_BTree(Bt_Node<T>* &Tree);			//创建二叉树（构造内调用）
    
    	int Distory_BTree(Bt_Node<T>* &Tree);			//析构二叉树的递归子函数（在析构内调用）
    
    
    	int LevelOrder_Op(Bt_Node<T>* &Tree,int Level);		//层次遍历的递归子函数
    
    	void PreOrder_Op(Bt_Node<T>* &Tree);				//先序遍历(递归实现函数）
    
    	void InOrder_Op(Bt_Node<T>* &Tree);					//中序遍历（递归实现函数）
    
    	void PostOrder_Op(Bt_Node<T>* &Tree);				//后序遍历（递归实现函数）
    public:
    	/*接口函数*/
    	Binary_tree();							//类构造
    	~Binary_tree();							//析构
    	void PreOrder();					//先序遍历
    	void InOrder();						//中序遍历
    	void PostOrder();
    	void LevelOrder();						//层次遍历
    
    };
    
    /******************* * * * * * * * * * * * * * * * * * * ********************/
               /*
    				二叉树创建，遍历，删除的内部递归函数
    				后缀为   _Op
                                                      */
    //										/**********/
    			/*
    				1.Create_Btree :先序遍历构造二叉树
    				2.Distory_BTree :二叉树的析构
    												 */
    template<class T>
    int Binary_tree<T>::Create_BTree(Bt_Node<T>* &Tree)  //为了递归实现构造，将私有数据Tree作为该创建递归函数的引用参数
    {
    	T data;
    	cin >> data;
    	if (data == -1)      //"#"代表空树
    		Tree = NULL;
    	else
    	{
    		Tree = new Bt_Node<T>;
    		Tree->Data = data;
    		Create_BTree(Tree->Left_Child);//创建左子树
    		Create_BTree(Tree->Right_Child);//创建右子树
    	}
    	return 0;
    }
    
    template<class T>
    int Binary_tree<T>::Distory_BTree(Bt_Node<T>* &Tree)
    {
    	if (Tree)			//该根节点非空
    	{
    		//cout << Tree->Data << endl;
    		Bt_Node<T>* Left_Tree = Tree->Left_Child;
    		Bt_Node<T>* Right_Tree = Tree->Right_Child;
    		delete Tree;
    		if (Left_Tree)			//左子树非空则释放
    			Distory_BTree(Left_Tree);
    		if (Right_Tree)			//同
    			Distory_BTree(Right_Tree);
    	}
    	return 0;
    }
    /*
    				***********End******
    */
    //			/*		    	遍历实现				 */
    			/*
    					1.PreOrder_Op  : 先序遍历
    					2.InOrder_Op   ：中序遍历
    					3.PostOrder_Op ：后序遍历
    					4.LevelOrder_Op：层次遍历
    												 */
    template<class T>
    void Binary_tree<T>::PreOrder_Op(Bt_Node<T>* &Tree)
    {
    	if (Tree)
    	{
    		cout << Tree->Data << endl;		//先访问根节点
    		PreOrder_Op(Tree->Left_Child);		//访问左子树
    		PreOrder_Op(Tree->Right_Child);	//访问右子树
    	}
    }
    
    template<class T>
    void Binary_tree<T>::InOrder_Op(Bt_Node<T>* &Tree)
    {
    	if (Tree)
    	{
    		InOrder_Op(Tree->Left_Child);		//访问左子树
    		cout << Tree->Data << endl;		//访问根节点
    		InOrder_Op(Tree->Right_Child);		//访问右子树
    	}
    }
    
    template<class T>
    void Binary_tree<T>::PostOrder_Op(Bt_Node<T>* &Tree)
    {
    	if (Tree)
    	{
    		PostOrder_Op(Tree->Left_Child);	//访问左子树
    		PostOrder_Op(Tree->Right_Child);	//访问右子树
    		cout << Tree->Data << endl;		//访问根节点
    	}
    }
    
    template<class T>
    int Binary_tree<T>::LevelOrder_Op(Bt_Node<T>* &Tree, int Level)
    {
    	if (Level < 0 || !Tree)//该层的根节点为空或者没有找到该层，返回0
    		return 0;
    	if (Level == 0)//该层根节点不空
    	{
    		cout << Tree->Data << " ";
    		return 1;	//访问该节点并返回
    	}
    	return LevelOrder_Op(Tree->Left_Child, Level - 1), LevelOrder_Op(Tree->Right_Child, Level - 1);
    	//还没有到所要访问的层次，从左子树开始往下一层开始检测节点
    }
    /*End*/
    /******************* * * * * * * * * * * * * * * * * * * ********************/
    
    /******************* * * * * * * * * * * * * * * * * * * ********************/
    						   /*外部接口函数*/
    //		
    //构造
    template<class T>
    Binary_tree<T>::Binary_tree()
    {
    	Create_BTree(Tree);
    }
    //析构
    template<class T>
    Binary_tree<T>::~Binary_tree()
    {
    	Distory_BTree(Tree);
    }
    			//End
    			/*
    					1.PreOrder  : 先序遍历
    					2.InOrder   ：中序遍历
    					3.PostOrder ：后序遍历
    					4.LevelOrder：层次遍历
    													*/
    template<class T>
    void Binary_tree<T>::PreOrder()
    {
    	PreOrder_Op(Tree);
    }
    
    template<class T>
    void Binary_tree<T>::InOrder()
    {
    	InOrder_Op(Tree);
    }
    
    template<class T>
    void Binary_tree<T>::PostOrder()
    {
    	PostOrder_Op(Tree);
    }
    
    template<class T>
    void Binary_tree<T>::LevelOrder()
    {
    	for (int i = 0;; i++)		//穷举树的度数（从0开始算）
    	{
    		if (!LevelOrder_Op(Tree, i))	//递归结果为0表示第i层不存在，即树的深度为i，树的根节点为0
    			break;
    		cout << endl;
    	}
    
    	cout << endl;
    }
    
    /******************* * * * * * * * * * * * * * * * * * * ********************/
    
    //                     /*     类结束      */            //

日常BB：四十几天没有更文，也是自己有点懒，放假了后面我尽量多出文吧~

**预告：二叉树非递归实现**

**传送门：待续~**

[70]: /images/20220520/a65bd68dea3a49bbaa2bdb025e74efe0.png
[70 1]: /images/20220520/b6a6d188ae824b9f9b3cfe2b33fe5363.png
[70 2]: /images/20220520/9d02e34ab9674cefae76242faf45f30d.png