C++数据结构与算法（二叉树）

绝地灬酷狼 2021-11-17 03:58 403阅读 0赞

**目录**

1、树的两种定义

2、相关概念

3、二叉树

3.1两种定义

3.2二叉树和树的根本区别

3.3二叉树的创建及遍历

3.3.1（前序、中序和后序递归）

3.3.2（前序、中序和后序非递归）

3.3.3new/delete和malloc/free的区别

3.3.4Practice

3.4二叉树的特性

3.5二叉树常用操作

3.5.1统计二叉树的叶子节点数

3.5.2返回一棵二叉树的层数

3.5.3查找Key值（节点不重复）

3.5.4复制一棵二叉树

3.5.5层次遍历二叉树

3.5.6镜像二叉树

3.5.7统计分支节点个数和单双分支节点个数

3.5.8创建一棵完全二叉树

--------------------

# **1、树的两种定义** #

> 1）树是一种数据结构，它是由n（n>=1）个有限的节点组成的一个具有层次关系的集合。
> 
> 2）树（tree）t是一个非空的有限元素的集合，其中一个元素为根（root），余下的元素（如果有的话）组成t的子树（subtree）.

# **2、相关概念** #

> 1）**节点的度**：节点拥有的孩子的数目，叶节点的度为零；
> 
> 2）**叶子**：度为零的节点；
> 
> 3）**分支节点**：度不为零的节点；
> 
> 4）**树的度**：树中节点的最大的度；
> 
> 5）**层次**：根节点的层次为1，往下依次递增；
> 
> 6）**树的高度**：树中节点的最大层次；
> 
> 7）**无序树**：如果树中节点的各子树之间的次序是不重要的，可以交换位置；
> 
> 8）**有序树**：如果树中节点的各子树之间的次序是重要的，不可以交换位置；
> 
> 9）**森林**：0或多个不相交的树组成。对森林加上一个根，森林即成为树，删除根，树即成为森林。
> 
> 10）**二叉树**是每个节点最多有两个子树的树结构；
> 
> 11）高度为h，并且由2^h-1个节点的二叉树，被称为**满二叉树**；
> 
> 12）一颗二叉树中，只有最下面两层节点的度可以小于2，并且最下一层的叶节点集中在靠左的若干位置上，这样的二叉树被称为**完全二叉树**；
> 
> 13）**二叉查找树**：又被称为二叉搜索树，左子树上的节点小于根节点的值，右子树上的节点大于根节点的值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70][]

# **3、二叉树** #

## **3.1两种定义** ##

> **节点可以包含两个子节点（也可能为空）的树，每一个子节点都区分为左子节点或右子节点。**
> 
> **二叉树（binary tree）t是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。**

![20190731102155763.png][]

> 节点的层次是从根到该节点所经过的弧的个数加1。根据该定义，根的层次是1，其非空子节点的层次是2，以此类推。如果除最后一个层次外，其他层上的所有节点都有两个子节点，那么。第一层有1=2^0个节点，第二层有2=2^1个节点，...，第i+1层有2^i个节点。满足该条件的树称为**完全二叉树**（complete binary tree）。在该树中，所有的非终端节点都有两个子节点，所有的叶节点都位于同一层次。因此，在所有的二叉树中，第i+1层最多有2^i个节点。
> 
> **满二叉树是完全二叉树的一种特例。**

## **3.2二叉树和树的根本区别** ##

> 1）二叉树可以为空，但树不能（**原因：树是图的特例，但二叉树不是树的特例，图是不能为空的**）；
> 
> 2）二叉树中每个元素都恰好有两棵子树（其中一个或两个可能为空）。而树中每个元素可有若干子树；
> 
> 3）在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。而树的子树间是无序的。

## **3.3二叉树的创建及遍历** ##

### **3.3.1（前序、中序和后序递归）** ###

/*
    创建二叉树，并且进行输出（前序、中序、后序递归）
    */
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct Node{
    	int data;                    //数据域
    	struct Node *left, *right;   //指针域
    }BTNode;
    
    //创建二叉树
    BTNode *CreateBTtree(int a[], int n)
    {
    	BTNode *root, *c, *pa=NULL, *p;
    	int i;
    	//root = (BTNode *)malloc(sizeof(BTNode));
    	root = new BTNode;
    	root->data = a[0];
    	root->left = root->right = NULL;
    	for (i = 1; i<n; i++)
    	{
    		//p = (BTNode *)malloc(sizeof(BTNode));
    		p = new BTNode;
    		p->left = p->right = NULL;
    		p->data = a[i];
    		c = root;
    		while (c)
    		{
    			pa = c;
    			if (c->data < p->data) //根节点小于待插入节点
    				c = c->right;      //往右遍历
    			else                  //根节点大于待插入节点 
    				c = c->left;      //往左遍历
    		}
    		if (pa->data < p->data)
    			pa->right = p;        //右放
    		else
    			pa->left = p;         //左放
    	}
    	return root;    //返回根节点
    }
    
    //前序遍历
    void Forder(BTNode *root)
    {
    	if (root)
    	{
    		//printf("%5d", root->data);
    		cout << setw(5) << root->data;
    		Forder(root->left);
    		Forder(root->right);
    	}
    }
    
    //中序遍历
    void Inorder(BTNode *root)
    {
    	if (root)
    	{
    		Inorder(root->left);
    		//printf("%5d", root->data);
    		cout << setw(5) << root->data;
    		Inorder(root->right);
    	}
    }
    
    //后序遍历
    void Porder(BTNode *root)
    {
    	if (root)
    	{
    		Porder(root->left);
    		Porder(root->right);
    		//printf("%5d", root->data);
    		cout << setw(5) << root->data;
    	}
    }
    
    int main()
    {
    	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    	BTNode *root;
    	root = CreateBTtree(a, 8);
    	//前序遍历
    	printf("前序遍历为:");
    	Forder(root);
    	cout << endl;
    	//中序遍历
    	printf("中序遍历为:");
    	Inorder(root);
    	cout << endl;
    	//后序遍历
    	printf("后序遍历为:");
    	Porder(root);
    	cout << endl;
    	system("pause");
    	return 0;
    }

常用的三种遍历方法的遍历顺序：

> 前序遍历：根 > 左 > 右
> 
> 中序遍历：左 > 根 > 右
> 
> 后序遍历：左 > 右 > 根

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1][]

**结果**：

![20190730160951602.png][]

### **3.3.2（前序、中序和后序非递归）** ###

/*
    创建二叉树并输出（前序、中序和后序非递归遍历）
    */
    #include<iostream>
    #include<iomanip>
    using namespace std;
    #define N 9
    
    typedef struct Node{
    	int data;
    	struct Node *left, *right;
    }BTNode;
    
    //创建二叉树
    BTNode *CreateBTtree(int a[])
    {
    	BTNode *root, *c, *pa = NULL, *p;
    	int i;
    	root = (BTNode *)malloc(sizeof(BTNode));
    	root->data = a[0];
    	root->left = root->right = NULL;
    	for (i = 1; i<N; i++)
    	{
    		p = (BTNode *)malloc(sizeof(BTNode));
    		p->left = p->right = NULL;
    		p->data = a[i];
    		c = root;
    		while (c)
    		{
    			pa = c;
    			if (c->data < p->data)
    				c = c->right;
    			else
    				c = c->left;
    		}
    		if (pa->data < p->data)
    			pa->right = p;
    		else
    			pa->left = p;
    	}
    	return root;
    }
    
    //前序遍历
    void priorder(BTNode *root)
    {
    	int top;
    	BTNode **s;
    	BTNode *p;
    	//声明栈
    	s = (BTNode **)malloc(N*sizeof(BTNode *));
    	top = -1;
    	s[++top] = root;
    	while (top != -1)
    	{
    		p = s[top--];
    		//printf("%5d", p->data);
    		cout << setw(5) << p->data;
    		if (p->right)
    			s[++top] = p->right;
    		if (p->left)
    			s[++top] = p->left;
    	}
    }
    
    //中序遍历
    void Inorder(BTNode *root)
    {
    	int top;
    	BTNode **s;
    	BTNode *p;
    	//声明栈
    	s = (BTNode **)malloc(N*sizeof(BTNode *));
    	p = root;
    	top = -1;
    	while (p)
    	{
    		s[++top] = p;
    		p = p->left;
    	}
    	while (top != -1)
    	{
    		p = s[top--];
    		//printf("%5d", p->data);
    		cout << setw(5) << p->data;
    		if (p->right)
    		{
    			p = p->right;
    			while (p)
    			{
    				s[++top] = p;
    				p = p->left;
    			}
    		}
    	}
    	free(s);
    }
    
    //后序遍历
    void  PostorderTraverse(BTNode  *root)
    {
    	BTNode *S1[N], *p = root;
    	int S2[N], top = 0, flag = 1;
    	if (root == NULL)
    		printf("Binary Tree is Empty!\n");
    	else
    	{
    		do
    		{
    			while (p != NULL)
    			{
    				S1[++top] = p;
    				S2[top] = 0;
    				p = p->left;
    			}
    			if (top == 0)
    				flag = 0;
    			else if (S2[top] == 0)
    			{
    				p = S1[top]->right;
    				S2[top] = 1;
    			}
    			else
    			{
    				p = S1[top];
    				top--;
    				//printf("%5d", p->data);
    				cout << setw(5) << p->data;
    				p = NULL;                 /*  使循环继续进行而不至于死循环 */
    			}
    		} while (flag != 0);
    	}
    }
    
    
    int main()
    {
    	int a[N] = { 6, 2, 8, 1, 4, 10, 3, 5, 9 };
    	BTNode *root;
    	//创建二叉树
    	root = CreateBTtree(a);
    
    	cout << "前序遍历：";
    	//按前序遍历
    	priorder(root);
    	cout << endl;
    
    	cout << "中序遍历：";
    	//按中序遍历
    	Inorder(root);
    	cout << endl;
    
    	cout << "后序遍历：";
    	//按后序遍历
    	PostorderTraverse(root);
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

结果：

![20190730173632860.png][]

### **3.3****.3new/delete和malloc/free的区别** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2][]

详见：[https://www.cnblogs.com/QG-whz/p/5140930.html][https_www.cnblogs.com_QG-whz_p_5140930.html]

### **3.3.4Practice** ###

> **1）根据前序遍历和中序遍历画出树的结构**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3][]

> **2）数学表达式树**
> 
>  **当对一棵数学表达式树进行中序，前序和后序遍历时，就分别得到表达式的中缀、前缀和后缀形式。中缀（infix）形式即为平时所书写的数学表达式。在后缀（postfix）表达式中，每个操作符跟在操作数后面，操作数从左到右的顺序出现。在前缀（prefix）表达式中，操作符位于操作数之前。**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4][]

## **3.4二叉树的特性** ##

> 特性1 包含n（n>0）个元素的二叉树边数为n-1.
> 
> 特性2 若二叉树的高度为h，h>=0，则该二叉树最少有h个元素，最多有2^h-1个元素。
> 
> 特性3 包含n个元素的二叉树的高度最大为n，最小为![20190730165550210.png][].
> 
> 特性4 设完全二叉树中一元素的序号为i，![20190730170039830.png][]，则有以下关系成立：
> 
> 1）当i=1时，该元素为二叉树的根。若i>1，则该元素父节点的编号为i/2；
> 
> 2）当2i>n时，该元素无左孩子。否则，其左孩子的编号为2i；
> 
> 3）当2i+1>n时，该元素无右孩子。否则，其右孩子编号为2i+1.

## 3.5二叉树常用操作 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5][]

### 3.5.1统计二叉树的叶子节点数 ###

/*返回二叉树的叶子节点的数目*/
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    //节点结构体
    typedef struct Node{
    	int data;
    	struct Node *left, *right;
    }BTNode;
    
    //创建二叉树
    BTNode *CreateBTtree(int a[], int n)
    {
    	BTNode *root, *c, *pa = NULL, *p;
    	int i;
    	//root = (BTNode *)malloc(sizeof(BTNode));
    	root = new BTNode;
    	root->data = a[0];
    	root->left = root->right = NULL;
    	for (i = 1; i<n; i++)
    	{
    		//p = (BTNode *)malloc(sizeof(BTNode));
    		p = new BTNode;
    		p->left = p->right = NULL;
    		p->data = a[i];
    		c = root;
    		while (c)
    		{
    			pa = c;
    			if (c->data<p->data)
    				c = c->right;
    			else
    				c = c->left;
    		}
    		if (pa->data<p->data)
    			pa->right = p;
    		else
    			pa->left = p;
    	}
    	return root;
    }
    
    
    //前序遍历
    void Forder(BTNode *root)
    {
    	if (root)
    	{
    		cout << setw(5) << root->data;
    		Forder(root->left);
    		Forder(root->right);
    	}
    }
    
    //中序遍历
    void Inorder(BTNode *root)
    {
    	if (root)
    	{
    		Inorder(root->left);
    		cout << setw(5) << root->data;
    		Inorder(root->right);
    	}
    }
    
    //后序遍历
    void Porder(BTNode *root)
    {
    	if (root)
    	{
    		Porder(root->left);
    		Porder(root->right);
    		cout << setw(5) << root->data;
    	}
    }
    
    
    //计算二叉树叶子节点数
    int CountLeafNode(BTNode *root)
    {
    	int l1, l2, l;
    	if (root == NULL)
    		return 0;
    	else
    	{
    		l1 = CountLeafNode(root->left);
    		l2 = CountLeafNode(root->right);
    		l = l1 + l2;
    		if ((!root->left) && (!root->right))
    			l++;
    		return l;
    	}
    }
    
    int main()
    {
    	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    	int x;
    	BTNode *root;
    	root = CreateBTtree(a, 8);
    	
    	//前序遍历
    	printf("前序遍历为:");
    	Forder(root);
    	cout << endl;
    	//中序遍历
    	printf("中序遍历为:");
    	Inorder(root);
    	cout << endl;
    	//后序遍历
    	printf("后序遍历为:");
    	Porder(root);
    	cout << endl;
    	x = CountLeafNode(root);
    	cout << "该二叉树的叶子结点数为：" << x << endl;
    	system("pause");
    	return 0;
    }

### ![20190730203625684.png][] ###

### 3.5.2返回一棵二叉树的层数 ###

#include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct Node{
    	int data;
    	struct Node *left, *right;
    }BTNode;
    
    //创建二叉树
    BTNode *CreateBTtree(int a[], int n)
    {
    	BTNode *root, *c, *pa = NULL, *p;
    	int i;
    	root = new BTNode;
    	root->data = a[0];
    	root->left = root->right = NULL;
    	for (i = 1; i<n; i++)
    	{
    		p = new BTNode;
    		p->left = p->right = NULL;
    		p->data = a[i];
    		c = root;
    		while (c)
    		{
    			pa = c;
    			if (c->data<p->data)
    				c = c->right;
    			else
    				c = c->left;
    		}
    		if (pa->data<p->data)
    			pa->right = p;
    		else
    			pa->left = p;
    	}
    	return root;
    }
    
    //前序遍历
    void Forder(BTNode *root)
    {
    	if (root)
    	{
    		cout << setw(5) << root->data;
    		Forder(root->left);
    		Forder(root->right);
    	}
    }
    
    //中序遍历
    void Inorder(BTNode *root)
    {
    	if (root)
    	{
    		Inorder(root->left);
    		cout << setw(5) << root->data;
    		Inorder(root->right);
    	}
    }
    
    //后序遍历
    void Porder(BTNode *root)
    {
    	if (root)
    	{
    		Porder(root->left);
    		Porder(root->right);
    		cout << setw(5) << root->data;
    	}
    }
    
    //返回二叉树的层数
    int BTtree(BTNode *root)
    {
    	int c1, c2, c;
    	if (!root)
    		return 0;
    	else
    	{
    		c1 = BTtree(root->left);
    		c2 = BTtree(root->right);
    		c = c1>c2 ? c1 : c2;
    		return c + 1;
    	}
    }
    int main()
    {
    	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    	BTNode *root;
    	int x;
    	root = CreateBTtree(a, 8);
    	//前序遍历
    	printf("前序遍历为:");
    	Forder(root);
    	cout << endl;
    	//中序遍历
    	printf("中序遍历为:");
    	Inorder(root);
    	cout << endl;
    	//后序遍历
    	printf("后序遍历为:");
    	Porder(root);
    	cout << endl;
    	//计算层数
    	x = BTtree(root);
    	cout << "该二叉树层数为：" << x << endl;
    	system("pause");
    	return 0;
    }

### ![20190730202512371.png][] ###

### 3.5.3查找Key值（节点不重复） ###

/*查找Key值的地址*/
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct Node{
    	int data;
    	struct Node *left, *right;
    }BTNode;
    
    //创建二叉树
    BTNode *CreateBTtree(int a[], int n)
    {
    	BTNode *root, *c, *pa = NULL, *p;
    	int i;
    	root = (BTNode *)malloc(sizeof(BTNode));
    	root->data = a[0];
    	root->left = root->right = NULL;
    	for (i = 1; i<n; i++)
    	{
    		p = (BTNode *)malloc(sizeof(BTNode));
    		p->left = p->right = NULL;
    		p->data = a[i];
    		c = root;
    		while (c)
    		{
    			pa = c;
    			if (c->data<p->data)
    				c = c->right;
    			else
    				c = c->left;
    		}
    		if (pa->data<p->data)
    			pa->right = p;
    		else
    			pa->left = p;
    	}
    	return root;
    }
    
    //前序遍历
    void Forder(BTNode *root)
    {
    	if (root)
    	{
    		cout << setw(5) << root->data;
    		Forder(root->left);
    		Forder(root->right);
    	}
    }
    
    //中序遍历
    void Inorder(BTNode *root)
    {
    	if (root)
    	{
    		Inorder(root->left);
    		cout << setw(5) << root->data;
    		Inorder(root->right);
    	}
    }
    
    //后序遍历
    void Porder(BTNode *root)
    {
    	if (root)
    	{
    		Porder(root->left);
    		Porder(root->right);
    		cout << setw(5) << root->data;
    	}
    }
    
    BTNode *FindNode(BTNode *root, int key)
    {
    	if (!root)
    		return NULL;
    	else if (root->data == key)
    		return root;
    	else if (key<root->data)
    		return FindNode(root->left, key);
    	else
    		return FindNode(root->right, key);
    }
    
    int main()
    {
    	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    	BTNode *root, *p;
    	int key;
    	printf("任意键入一个key值：");
    	cin>>key;
    
    	root = CreateBTtree(a, 8);
    	//前序遍历
    	printf("前序遍历为:");
    	Forder(root);
    	cout << endl;
    	//中序遍历
    	printf("中序遍历为:");
    	Inorder(root);
    	cout << endl;
    	//后序遍历
    	printf("后序遍历为:");
    	Porder(root);
    	cout << endl;
    	p = FindNode(root, key);
    	//输出Key值的地址
    	cout << "key值地址为："<< p << endl;
    	system("pause");
    	return 0;
    }

### ![20190730203323962.png][] ###

### 3.5.4复制一棵二叉树 ###

#include<iostream>
    #include<iomanip>
    using namespace std;
    
    typedef struct Node{
    	int data;
    	struct Node *left, *right;
    }BTNode;
    
    //创建二叉树
    BTNode *CreateBTtree(int a[], int n)
    {
    	BTNode *root, *c, *pa = NULL, *p;
    	int i;
    	root = new BTNode;
    	root->data = a[0];
    	root->left = root->right = NULL;
    	for (i = 1; i<n; i++)
    	{
    		p = new BTNode;
    		p->left = p->right = NULL;
    		p->data = a[i];
    		c = root;
    		while (c)
    		{
    			pa = c;
    			if (c->data<p->data)
    				c = c->right;
    			else
    				c = c->left;
    		}
    		if (pa->data<p->data)
    			pa->right = p;
    		else
    			pa->left = p;
    	}
    	return root;
    }
    
    //复制一棵二叉树
    BTNode *BTcopy(BTNode *root)
    {
    	BTNode * p = NULL;
    	if (root)
    	{
    		p = (BTNode *)malloc(sizeof(BTNode));
    		p->data = root->data;
    		p->left = p->right = NULL;
    		if (root->left)
    			p->left = BTcopy(root->left);
    		if (root->right)
    			p->right = BTcopy(root->right);
    	}
    	return p;
    }
    
    //前序遍历
    void Forder(BTNode *root)
    {
    	if (root)
    	{
    		cout << setw(5) << root->data;
    		Forder(root->left);
    		Forder(root->right);
    	}
    }
    
    //中序遍历
    void Inorder(BTNode *root)
    {
    	if (root)
    	{
    		Inorder(root->left);
    		cout << setw(5) << root->data;
    		Inorder(root->right);
    	}
    }
    
    //后序遍历
    void Porder(BTNode *root)
    {
    	if (root)
    	{
    		Porder(root->left);
    		Porder(root->right);
    		cout << setw(5) << root->data;
    	}
    }
    
    
    
    
    int main()
    {
    	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    	BTNode *root, *p;
    	root = CreateBTtree(a, 8);
    
    	//前序遍历
    	cout << "前序遍历为:";
    	Forder(root);
    	cout << endl;
    	//中序遍历
    	cout << "中序遍历为:";
    	Inorder(root);
    	cout << endl;
    	//后序遍历
    	cout<<"后序遍历为:";
    	Porder(root);
    	cout << endl;
    	
    	
    	p = BTcopy(root);
    	cout<<"复制后的前序遍历为:";
    	Forder(p);
    	cout << endl;
    	system("pause");
    	return 0;
    }

![20190730204202291.png][]

### 3.5.5层次遍历二叉树 ###

#include<iostream>
    #include<iomanip>
    using namespace std;
    #define N 8
    
    typedef struct Node{
    	int data;
    	struct Node *left, *right;
    }BTNode;
    
    //创建完全二叉树
    BTNode *CreateBTtree(int a[])
    {
    	BTNode *root, *pa, *p;
    	BTNode **Q;
    	int i;
    	int front, rear;
    	front = rear = 0;
    	//创建队列
    	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode*));
    	//创建根结点
    	pa = root = (BTNode *)malloc(sizeof(BTNode));
    	root->data = a[0];
    	root->left = root->right = NULL;
    	for (i = 1; i<N; i++)
    	{
    		p = (BTNode *)malloc(sizeof(BTNode));
    		p->data = a[i];
    		p->left = p->right = NULL;
    		Q[++rear] = p;
    		if (pa->left == NULL)
    			pa->left = p;
    		else
    		{
    			pa->right = p;
    			pa = Q[++front];
    		}
    	}
    	free(Q);
    	return root;
    }
    
    //按层遍历
    void levelorder(BTNode *root)
    {
    	int front, rear;
    	BTNode ** Q;
    	BTNode * p;
    	//声明队列
    	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode *));
    	//初始化队列
    	front = rear = 0;
    	Q[++rear] = root;
    	//按层输出
    	while (front - rear)
    	{
    		p = Q[++front];  //出队
    		cout << setw(5) << p->data;
    		if (p->left)
    			Q[++rear] = p->left;
    		if (p->right)
    			Q[++rear] = p->right;
    	}
    	free(Q);
    }
    
    
    int main()
    {
    	int a[N] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    	BTNode *root;
    	root = CreateBTtree(a);
    	//按层遍历
    	cout << "按层遍历结果为：" << endl;
    	levelorder(root);
    	cout << endl;
    	system("pause");
    	return 0;
    }

![20190730204803889.png][]

### 3.5.6镜像二叉树 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 6][]

#include<iostream>
    #include<iomanip>
    using namespace std;
    #define N 8
    #define null 0
    
    typedef struct node{
    	int data;
    	struct node *left;
    	struct node *right;
    }BTNode;
    
    //创建二叉树
    BTNode *GreatBtree(int[], int);
    //生成一棵二叉树的镜像树
    void MirrorTree(BTNode *);
    
    //按层遍历
    void levelorder(BTNode *root)
    {
    	int front, rear;
    	BTNode ** Q;
    	BTNode * p;
    	//声明队列
    	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode *));
    	//初始化队列
    	front = rear = 0;
    	Q[++rear] = root;
    	//按层输出
    	while (front - rear)
    	{
    		p = Q[++front];  //出队
    		cout << setw(5) << p->data;
    		if (p->left)
    			Q[++rear] = p->left;
    		if (p->right)
    			Q[++rear] = p->right;
    	}
    	free(Q);
    }
    
    
    int main()
    {
    	int a[N] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    	BTNode *root;
    	root = GreatBtree(a, N);
    	cout << "按层遍历（镜像前）：" << endl;
    	levelorder(root);
    	cout << endl;
    
    	MirrorTree(root);
    	cout << "按层遍历（镜像后）：" << endl;
    	levelorder(root);
    	cout << endl;
    	system("pause");
    	return 0;
    }
    BTNode *GreatBtree(int a[], int n)
    {
    	BTNode *root = null, *p, *c, *q = NULL;
    	int i;
    	for (i = 0; i<n; i++){
    		//创建一个结点
    		p = (BTNode *)malloc(sizeof(BTNode));
    		p->left = p->right = null;
    		p->data = a[i];
    		if (root){
    			c = root;
    			while (c){
    				q = c;
    				if (p->data <= c->data){
    					c = c->left;
    				}
    				else{
    					c = c->right;
    				}
    			}
    			if (p->data <= q->data){
    				q->left = p;
    			}
    			else{
    				q->right = p;
    			}
    		}
    		else{
    			root = p;
    		}
    	}
    	return root;
    }
    
    
    //镜像树即只有根结点不变
    //其余所有左子女与右子女对调位置
    //缺点:直接改变了原二叉树
    //改进方法先拷贝后镜像即可
    void MirrorTree(BTNode *root)
    {
    	BTNode *middle;
    	if (!root){
    		return;
    	}
    	else{
    		MirrorTree(root->left);
    		MirrorTree(root->right);
    		middle = root->left;
    		root->left = root->right;
    		root->right = middle;
    	}
    }
    
    //拷贝二叉树
    BTNode *CopyBT(BTNode *root)
    {
    	BTNode *p = null;
    	if (root){
    		p = (BTNode *)malloc(sizeof(BTNode));
    		p->data = root->data;
    		p->left = CopyBT(root->left);
    		p->right = CopyBT(root->right);
    	}
    	return p;
    }

### ![20190730210517394.png][] ###

### 3.5.7统计分支节点个数和单双分支节点个数 ###

分支节点：度不为零的节点

双分支节点：拥有两个孩子的节点（度为2的节点）

单分支节点：拥有一个孩子的节点（度为1的节点）

#include<iostream>
    #include<iomanip>
    using namespace std;
    #define N 8
    #define null 0
    
    typedef struct node{
    	int data;
    	struct node *left;
    	struct node *right;
    }BTNode;
    
    //创建二叉树
    BTNode *GreatBtree(int[], int);
    //统计二叉树双分支结点个数
    int CountDoubleNode(BTNode *);
    //统计二叉树单双分支结点总数
    int CountSingleAndDoubleNode(BTNode *);
    
    int main()
    {
    	int a[N] = { 5, 3, 7, 2, 4, 6, 8, 9 };
    	BTNode *root;
    	root = GreatBtree(a, N);
    	cout << "Double's Node number:" << CountDoubleNode(root) << endl;
    	cout << "Double's and single's Node number:" << CountSingleAndDoubleNode(root) << endl;
    	system("pause");
    	return 0;
    }
    BTNode *GreatBtree(int a[], int n)
    {
    	BTNode *root = null, *p, *c, *q = NULL;
    	int i;
    	for (i = 0; i<n; i++){
    		//创建一个结点
    		p = (BTNode *)malloc(sizeof(BTNode));
    		p->left = p->right = null;
    		p->data = a[i];
    		if (root){
    			c = root;
    			while (c){
    				q = c;
    				if (p->data <= c->data){
    					c = c->left;
    				}
    				else{
    					c = c->right;
    				}
    			}
    			if (p->data <= q->data){
    				q->left = p;
    			}
    			else{
    				q->right = p;
    			}
    		}
    		else{
    			root = p;
    		}
    	}//for
    	return root;
    }
    int CountLeafNode(BTNode *root)
    {
    	if (!root){
    		return 0;
    	}
    	else{
    		return CountLeafNode(root->left) + CountLeafNode(root->right) + !(root->left || root->right);
    	}
    }
    //双分支结点满足有左子女和右子女
    int CountDoubleNode(BTNode *root)
    {
    	if (!root){
    		return 0;
    	}
    	else{
    		return CountDoubleNode(root->left) + CountDoubleNode(root->right) + (root->left&&root->right);//此处&&优先级最低
    	}
    }
    int CountSingleAndDoubleNode(BTNode *root)
    {
    	if (!root){
    		return 0;
    	}
    	else{
    		return CountSingleAndDoubleNode(root->left) + CountSingleAndDoubleNode(root->right) + (root->left || root->right);
    	}
    }

![2019073021213531.png][]

### 3.5.8创建一棵完全二叉树 ###

#include<iostream>
    #include<iomanip>
    using namespace std;
    #define N 14
    
    typedef struct Node{
    	int data;
    	struct Node *left, *right;
    }BTNode;
    
    //创建一棵完全二叉树
    BTNode *CreateBTtree(int a[])
    {
    	BTNode *root, *pa, *p;
    	BTNode **Q;
    	int i;
    	int front, rear;
    	front = rear = 0;
    	//创建队列
    	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode*));
    	//创建根结点
    	pa = root = (BTNode *)malloc(sizeof(BTNode));
    	root->data = a[0];
    	root->left = root->right = NULL;
    	for (i = 1; i<N; i++)
    	{
    		p = (BTNode *)malloc(sizeof(BTNode));
    		p->data = a[i];
    		p->left = p->right = NULL;
    		Q[++rear] = p;
    		if (pa->left == NULL)
    			pa->left = p;
    		else
    		{
    			pa->right = p;
    			pa = Q[++front];
    		}
    	}
    	free(Q);
    	return root;
    }
    
    //按层遍历
    void levelorder(BTNode *root)
    {
    	int front, rear;
    	BTNode ** Q;
    	BTNode * p;
    	//声明队列
    	Q = (BTNode **)malloc((N + 1)*sizeof(BTNode *));
    	//初始化队列
    	front = rear = 0;
    	Q[++rear] = root;
    	//按层输出
    	while (front - rear)
    	{
    		p = Q[++front];  //出队
    		cout << setw(5) << p->data;
    		if (p->left)
    			Q[++rear] = p->left;
    		if (p->right)
    			Q[++rear] = p->right;
    	}
    	free(Q);
    }
    
    //前序遍历
    void Forder(BTNode *root)
    {
    	if (root)
    	{
    		cout << setw(5) << root->data;
    		Forder(root->left);
    		Forder(root->right);
    	}
    }
    
    //中序遍历
    void Inorder(BTNode *root)
    {
    	if (root)
    	{
    		Inorder(root->left);
    		cout << setw(5) << root->data;
    		Inorder(root->right);
    	}
    }
    
    //后序遍历
    void Porder(BTNode *root)
    {
    	if (root)
    	{
    		Porder(root->left);
    		Porder(root->right);
    		cout << setw(5) << root->data;
    	}
    }
    
    
    int main()
    {
    	//int a[N]={3,2,13,8,12,7,9,1,6,11,4,5};
    	int a[N] = { 14, 23, 24, 32, 42, 51, 58, 62, 65, 73, 80, 99, 120, 3942 };
    	BTNode *root;
    	root = CreateBTtree(a);
    
    	//按层遍历
    	cout << "按层遍历：";
    	levelorder(root);
    	cout << endl;
    
    	//前序遍历
    	cout << "前序遍历：";
    	Forder(root);
    	cout << endl;
    
    	//中序遍历
    	cout << "中序遍历：";
    	Inorder(root);
    	cout << endl;
    
    	//后序遍历
    	cout << "后序遍历：";
    	Porder(root);
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

结果：

![20190731094252290.png][]

由此可绘制出这棵完全二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 7][]

![20190730173809106.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70]: /images/20211116/ef0c081a35d542bc93c91a2f1a53c59b.png
[20190731102155763.png]: /images/20211116/b6b71d98d0714fe899dd216b3b525fde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 1]: /images/20211116/e9fbb749521149d1b2fc8cf3111a1bf6.png
[20190730160951602.png]: /images/20211116/e173451fd58d40ed8393a7b4157ae482.png
[20190730173632860.png]: /images/20211116/091f36a92ee34f24abd1cadc436a97c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 2]: /images/20211116/b12ba095150a4af79331d859c3aa28bf.png
[https_www.cnblogs.com_QG-whz_p_5140930.html]: https://www.cnblogs.com/QG-whz/p/5140930.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 3]: /images/20211116/f1bab6ab673b446da4bef54ece354524.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 4]: /images/20211116/8a32e955909943c7a139c47a89ece8bb.png
[20190730165550210.png]: /images/20211116/b6cf0bc0130f48dab86b1eb5fccf86d2.png
[20190730170039830.png]: /images/20211116/159c851b848345c28d2061fcce96069a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 5]: /images/20211116/e2581e220fc44837bac3d4826f35f43f.png
[20190730203625684.png]: /images/20211116/b54d9154b64f41e6ab09364d379a26b2.png
[20190730202512371.png]: /images/20211116/bd1e6da1b8e6410ab6e81068da46cff7.png
[20190730203323962.png]: /images/20211116/1d3db9561d9d499bacb275dbdaf09da8.png
[20190730204202291.png]: /images/20211116/7df037c70c1542258a92ace943a75d2c.png
[20190730204803889.png]: /images/20211116/7fb8489c1c154333b4842f497bd822ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 6]: /images/20211116/de7438bd60e448aa9aa8641203f6d65c.png
[20190730210517394.png]: /images/20211116/487a47f29ab7461086e9c75c3f94fdf7.png
[2019073021213531.png]: /images/20211116/510f0580023c41218594691a60b06c0b.png
[20190731094252290.png]: /images/20211116/cee25dc5c0b849dca7f5e19486fe8df3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzc1MzIxNQ_size_16_color_FFFFFF_t_70 7]: /images/20211116/59c398961e1548f08ecbb5f53673767c.png
[20190730173809106.png]: /images/20211116/bea1be2098634ef79c1ef2a9b1a974ae.png