• 广义表由线性表进一步推广，n（n≥0)由数据元素组成的序列。线性表中的数据元素只能是单个元素，它是不可分割的，而广义表中的数据元素可以是单个元素或广义表，通过圆括号()括起来，通过逗号,分离表中的数据元素，广义表可以递归，广义表也可以是自己的子表，广义表中的第一个元素称为广义表头，由剩余数据元素组成的表称为广义表表尾。

例如B=(a,b,c)，A=(B,d,e），即A=((a,b,c),d,e），广义表A的表头是(a,b,c)，表尾是(d,e)； 例如C=(a,b,c,d,e,f,g)，广义表的表头是(a)，表尾是(b,c,d,e,f,g)； 例如D=((a,b),((c,d,e),(f,g,h)))，广义表的表头是(a,b)，表尾是((c,d,e),(f,g,h))。

(一)树的概念

• 树是一种非线性结构，它是树形结构，数据元素集合含有n个有限元素(包括n≥0，n=0时为空树)，线性结构中的数据元素是一对一，树形结构中的数据元素是一对一一对多”的关系。
• 树（n>0)满足两个条件，一棵树只有一棵根结点，根结点没有前驱结点，除根结点外，所有其他结点只有一个前驱结点；剩下的结点是m(m≥0)一个不相交的非空集合，每一个集合也可以称为一棵树，即根的子树。
• 树的两个结点之间路径由两个结点之间的序列组成，路径长度树的路径长度是从根结点到每个结点的路径长度的总和。

另外，由m（m≥0)互不相交的树的集合称为森林。

（二）结点 叶结点、儿童结点、双亲结点、兄弟结点： 1、叶子结点也称为终端结点，它是没有子结点的结点（度为0），例如上图中，D、E、F、G都是叶结点； 2.结点的后继结点称为结点孩子结点，例如，在上图中，A儿童结点是B、C； 3.一个结点称为后继点双亲结点，例如，在上图中，B、C双亲结点是A，D、E双亲结点是B； 4.同一双亲结点下的儿童结点互为兄弟结点，例如，在上图中，B、C互为兄弟结点，他们有共同的父母A，另外D、E互为兄弟结点，他们有共同的父母B。

(三)树的性质 1、树中结点的子结点（孩子）个数称为该结点的度，树的结点最大度数称为树的度，例如，在上图中，结点B有两个子结点D和E，因此，结点B的度为2，结点D的度为0，树的度为2。

• ?树中结点的数量等于所有结点的度数之和加1。

例如，上图结点的数量是N=（2 2 2） 1=7。

• ?此外，树中结点的数量等于总分支加1，其中总分支=1n₁ 2n₂ 3n₃ … mn_m(m的结点导致m条分支)。

例如，在上图中，总分支数为6，因此结点数为6 1=7。

2.树中结点的最大层数是树的高度(深度)，结点的深度树的根结点从上到下开始，结点的高度从下到上从树的叶结点开始。

• ?树的第一层度为m（i≥1），至多有m^i-1个结点。

比如上图中树的度为2，m=2，第3层上（i=3）上至多有m^i-1=2²=4个结点。

(一)二叉树的概念

• 二叉树是一种特殊的树，与普通树相比，普通树的后继结点可以是任何多个，而且最多只有两个二叉树结点的后继结点，还有两种特殊的二叉树，满二叉树和完全二叉树，满二叉树是完全二叉树的特例。可以说，如果一棵树是满二叉树，那一定是完全二叉树，但不能说完全二叉树一定是满二叉树。

在完整的二叉树中，叶结点只能出现在下层和下层，下层的叶结点集中在树的左侧。

• 二叉树也是数据元素的集合(包括n个有限元素)n≥0，n=0时为空二叉树)，由一个根点和两个不相交的非空树分别称为左子树和右子树二叉树是一种特殊的组成有序树(结点各子树从左到右有序)，左右子树的顺序不能随意交换。同样，左右子树也是二叉树。

另外，完全二叉树的另一个定义是，如果深度是h，当结点数为n的二叉树编号后，每个结点的编号与深度为h的满二叉树同一位置结点上相应的编号相同时，该二叉树为完全二叉树。

满二叉树： 完全二叉树： 如果一棵二叉树的编号（从1的根点开始），根据二叉树的层次，从上到下，从左到右，我们可以得到以下性质：

• ?当一个结点的双亲结点为i时（i>1)如果是父母左孩子的结点，编号为2i，如果右孩子结点，编号为2i 1.即当i为偶数时，结点i的父母编号为i/2，这个结点是父母左孩子的结点i是奇数时，结点i的父母编号是（i-1)/2，这个结点是父母右孩子的结点。
• ?当2i≤n时（n为最后一个结点编号)，结点i的左孩子编号为2i，否则没有左孩子；当2i 1≤n结点i的右孩子编号为2i 1.否则没有正确的孩子。

例如，B是D、E双亲结点，即它是D、E双亲，结点D号为4，为偶数，说明是双亲B的左孩子结点，结点E号为5，为奇数，是双亲B的右孩子结点： (二)二叉树的性质

• ?在二叉树中，设度为0、1和2的结点数分别为n₀、n₁和n₂，即结点总数N=n₀ n₁ n₂。
• ?在二叉树中，叶结点数等于度为2的结点数加1，设度为0和2的结点数为n₀、n₂，即n₀=n 2+1。

例如，下图完全二叉树中，可以验证一下，度为2的结点个数为4，所以度为0的结点（叶子结点）个数为n₀=4+1=5。

• ✨二叉树中，分支总数=N-1=n₁+2n₂。

例如，下图完全二叉树中，分支总数等于9-1=8，或者等于度为1的结点个数加上两倍度为2的结点个数，即n₁+2n₂=0+2×4=8。

• ✨二叉树中，第i层上至多有2^i-1（i≥1）个结点，这种即为满二叉树的情况。

例如，在一棵二叉树中，第四层至多有2^4-1=2³=8个结点。

• ✨高度为h的二叉树至多有2^h-1个结点，另外高度为h的m叉树中，至多有（m^h-1）/（m-1）个结点。

例如下图是一个二叉树，其高度（深度）为4，h=4，即至多有2⁴-1=15个结点，这个二叉树并不是一个满二叉树，而是一个完全二叉树。

• ✨对于n个结点，可以组成N种不同的二叉树，如下： N = C 2 n n n + 1 N = \frac{C_{2n}^{n}}{n+1} N=n+1C2nn​​

例如，由3个结点构成的二叉树，可以有 N = C 6 3 3 + 1 = 20 / 4 = 5 种不同的二叉树。 N = \frac{C_{6}^{3}}{3+1}={20/4=5} 种不同的二叉树。 N=3+1C63​​=20/4=5种不同的二叉树。

（二）满二叉树的性质

• ✨一棵有n个结点的满二叉树，含有（n+1）/2个叶子结点，含有（n-1）/2个分支结点，其高度为h=log₂(n+1)。

推导过程：由于是满二叉树，所以度为1的结点为0，即n₁=0，由于二叉树的性质n₀=n₂+1以及n=n₀+n₁+n₂，可得n=2n₀-1，所以叶子结点n₀=（n+1）/2； 由于分支总数=n-1=n₁+2n₂，且n₀=n₂+1、n₁=0，所以分支总数=2n₂=n₀-1=（n-1）/2； 高度为h的满二叉树的结点数为1+2+4+……+2^h-1=2^h-1（首项为1，公比为2的等比数列），即n=S_n=[a₁(1-qⁿ)]/1-q=2^h-1，从中解出h，高度为h=log₂(n+1)。

（三）完全二叉树的性质

• ✨由于完全二叉树的结点排法，可知叶子结点尽可能地往左边排，故度为1的结点个数只有一个或零个。

例如，已知一棵完全二叉树的第6层有8个叶子结点，求该完全二叉树的最多和最少结点数。由于第6层有叶子结点，所以完全二叉树的高度可能为6或7，当为6时，完全二叉树拥有最少结点数，由于前5层都为满二叉树，即1+2+4+8+16+8=31+8+39；当为7时，前6层都为满二叉树，其中有8个结点没有左右结点，即1+2+4+8+16+32+(32-8)×2=63+48=111，故该完全二叉树的最多和最少结点数分别为39和111。

• ✨一棵含有n个结点的完全二叉树中，叶子结点个数等于n/2【n为偶数】或（n+1）/2【n为奇数】。

例如，已知一棵完全二叉树有1001个结点，所以其叶子结点个数就等于（1001+1）/2=501个。

例如，已知一棵完全二叉树具有124个叶子结点，求其最多和最少结点数。当结点数n为偶数时，结点数最大，124=n/2，解得n=248，n为奇数时，结点数最小，124=（n+1）/2，解得n=247，故最多和最少结点数为248和247。 另一种解法是，根据n₀=n₂+1可知，n₀=124，n₂=123，由于N=n₀+n₁+n₂，且该树为完全二叉树，根据完全二叉树的性质，度为1的结点个数只有一个或零个，即N=124+1+123=248和N=124+0+123=247，所以最多和最少结点数为248和247。

• ✨在完全二叉树中，编号为i（i≥1）的结点所在的层次为⌊log₂i⌋+1。
• ✨对于一棵含有n个结点的二叉树，当它为完全二叉树时，具有最小高度，最小高度为h=⌈log₂(n+1)⌉或⌊log₂n⌋+1（其中 ⌈ ⌉表示向上取整，取比自己大的最小整数，⌊ ⌋表示向下取整，取比自己小的最大整数）；当它为一棵单支树时具有最大高度，即为一个线性表。

例如，设一颗二叉树的结点个数为50，求其最小高度，我们知道当这棵树为完全二叉树时高度最小，n=50，即h=⌊log₂50⌋+1 =5+1=6，所以其最小高度为6。

例如，求一棵具有1025个结点的二叉树的高度，首先我们知道当二叉树为单支树时此时具有最大高度，即每层只有一个结点，最大高度为1025；另外，当二叉树为完全二叉树时高度最小，此时即最小高度为⌊log₂1025⌋+1=10+1=11，故该二叉树的高度为11~1025。

• ✨高度为h的完全二叉树最少有2^h-1个结点，最多有2^h-1个结点。

平衡二叉树的特点是其中任一结点的左右子树的深度之差都不超过1，如下是一个平衡二叉树和非平衡二叉树： 非平衡二叉树：

二叉树的存储结构分为顺序存储结构和链式存储结构。

1、二叉树的顺序存储结构通过使用一组地址连续的存储单元数组进行存储，其中根结点的编号设定为1，若结点的编号为i，则对应存储的一维数组下标为i-1，如下图：

若从数组下标array[0]开始存储二叉树，则上面的性质无法适用，即无法通过所给编号位置来计算出其孩子结点在数组中的位置，例如，结点C的编号i为3，2i=6≤7，该结点的左孩子编号为2i=6，即结点F，说明左孩子存在，但是在数组中结点F的存放位置array[5]并不是与编号相同。

2、但是顺序存储结构存在浪费情况，就是在最坏情况下，一个高度（深度）为h的单支二叉树需要占据2^h-1个数组存储单元，虽然它只有h个结点，如下：

• 二叉树的链式存储结构通过链表实现，一个二叉树链表结点由数据域和指针域组成，除了data数据域用于存放结点的信息外，每个结点含有两个指针，左指针域lchild和右指针域rchild，分别指向该结点的左孩子结点和右孩子结点，它们用于存放该结点左/右子树的地址，当左/右子树不存在，其指针域为空（“^”），如下图：

链式存储结构实现代码如下：

typedef struct BNode { 
        
	int data;		//数据域
	struct BNode *lchild,*rchild;		//左孩子、右孩子指针
} BTree;

例如，下面这个树的链式表示如下： 我们可以得到一个结论：

• ✨在由n个结点组成的二叉链表中，含有n+1个空指针域，含有n-1个非空指针域。

例如，上图二叉树中，含有8个结点，它含有8+1=9个空指针域，含有8-1=7个非空指针域。

二叉树的遍历是按某种规定的顺序来对访问树中的所有结点，且每个结点仅被访问一次，由于二叉树由根结点（D）、左子树（L）和右子树（R）组成，以下是二叉树的先、中、后以及层次遍历。

二叉树的先、中、后序遍历都可以通过递归算法实现，递归结束的条件是T==NULL，即当二叉树为空时，遍历结束。

（一）二叉树的先序遍历（DLR） 二叉树的先序遍历中，首先是根结点，遍历完根结点的左子树，然后再遍历完根结点的右子树，依次下去至所有结点都遍历到，例如上图二叉树，其先序遍历就是abefcgh。 （二）二叉树的中序遍历（LDR） 二叉树的中序遍历中，首先是遍历完根结点的左子树，然后是根结点，最后遍历完根结点的右子树，依次下去至所有结点都遍历到，例如上图二叉树，其中序遍历就是ebfagch。 （三）二叉树的后序遍历（LRD） 二叉树的后序遍历中，首先是遍历完根结点的左子树，然后遍历完根结点的右子树，最后是根结点，依次下去至所有结点都遍历到，也就是从二叉树的底层往上层依次遍历，例如上图二叉树，其后序遍历就是efbghca。 （四）二叉树的层次遍历 层次遍历中，层次优先，当对一层的结点都遍历完后，遍历下一层，按照次序对每个结点的左、右孩子进行遍历，例如上图二叉树，其层次遍历就是abcefgh。

• 层次遍历二叉树中可以通过链式队列实现，首先二叉树的根结点入队，然后进入循环，循环条件为队列是否为空，若不为空，则当前队头结点出队，此时该结点被访问到，并将该结点的左、右孩子结点插入到队列的队尾。

通过链式存储结构实现代码如下，其中包含数据域和两个指针：

#incldue<stdio.h>
/*二叉树的定义*/
typedef struct BNode { 
        
	int data;		//数据域
	struct BNode *lchild,*rchild;		//左孩子、右孩子指针
} *BTree;

创建一个二叉树，按二叉树的顺序（二叉树带空指针的顺序，空指针也算进去），即根结点、左子树、右子树的顺序依次输入结点的值【使用的顺序是先序序列】，若其中有空结点，用0表示，其中使用到递归的方法建立左右孩子结点，实现代码如下：

#include <malloc.h>
/*二叉树的建立*/
BTree CreateTree() { 
        
	BTree T;
	char ch;
	scanf("%c",&ch);
	getchar();	//getchar()用于接收每次输入字符结点后的回车符，从而以便输入下一个字符结点
	if(ch=='0')	//当为0时，将结点置空
		T=NULL;
	else { 
        
		T=(BTree)malloc(sizeof(BTree));	//分配一个新的结点
		T->data=ch;
		printf("请输入%c结点的左孩子结点：",T->data);
		T->lchild=CreateTree();		//通过递归建立左孩子结点
		printf("请输入%c结点的右孩子结点：",T->data);
		T->rchild=CreateTree();		//通过递归建立右孩子结点
	}
	return T;
}

通过广义表来显示建立的二叉树，一个非空的二叉树T，当对于左孩子结点或右孩子结点时，此时输出一个左括号“(”，递归处理左子树，输出一个“,”用于隔开结点，然后递归处理右子树，输出一个右括号“)”，从而完成一个根结点以下的两个左/右结点处理。

/*广义表输出二叉树*/
void ShowTree(BTree T) { 
        
	if(T!=NULL) { 
        
		//当二叉树不为空时
		printf("%c",T->data);	//输入出该结点的数据域
		if(T->lchild!=NULL) { 
        		//若该结点的左子树不为空
			printf("(");	//输出一个左括号
			ShowTree(T->lchild);	//通过递归继续输出结点的左子树结点下的各结点
			if(T->rchild!=NULL) { 
        	//若该结点右子树不为空
				printf(",");	//输出一个逗号
				ShowTree(T->rchild);	//通过递归继续输出结点的右子树结点下的各结点
			}
			printf(")");	//输出一个右括号
		} else { 
        	//若左子树为空，右子树不为空
			if(T->rchild!=NULL) { 
        
				printf("(");	//输出一个左括号
				ShowTree(T->lchild);	//通过递归继续输出结点的左子树结点下的各结点
				if(T->rchild!=NULL) { 
        		//若该结点的右子树不为空 
					printf(",");	//输出一个逗号
					ShowTree(T->rchild);	//通过递归继续输出结点的右子树结点下的各结点
				}
				printf(")");	//输出一个右括号
			}
		}
	}
}

例如，一个二叉树如下图，通过链式存储结构实现建立二叉树并输出。 代码如下：

#include <stdio.h>
#include <malloc.h>
/*1、二叉树的定义*/
typedef struct BNode { 
        
	int data;		//数据域
	struct BNode *lchild,*rchild;		//左孩子、右孩子指针
} *BTree;

/*2、二叉树的建立*/
BTree CreateTree() { 
        
	BTree T;
	char ch;
	scanf("%c",&ch);
	getchar();	//getchar()用于接收每次输入字符结点后的回车符，从而以便输入下一个字符结点
	if(ch=='0')	//当为0时，将结点置空
		T=NULL;
	else { 
        
		T=(BTree)malloc(sizeof(BTree));	//分配一个新的结点
		T->data=ch;
		printf("请输入%c结点的左孩子结点：",T->data);
		T->lchild=CreateTree();		//通过递归建立左孩子结点
		printf("请输入%c结点的右孩子结点：",T->data);
		T->rchild=CreateTree();		//通过递归建立右孩子结点
	}
	return T;
}

/*3、广义表输出二叉树*/
void ShowTree(BTree T) { 
        
	if(T!=NULL) { 
        
		//当二叉树不为空时
		printf("%c",T->data);	//输入出该结点的数据域
		if(T->lchild!=NULL) { 
        		//若该结点的左子树不为空
			printf("(");	//输出一个左括号
			ShowTree(T->lchild);	//通过递归继续输出结点的左子树结点下的各结点
			if(T->rchild!=NULL) { 
        	//若该结点右子树不为空
				printf(",");	//输出一个逗号
				ShowTree(T->rchild);	//通过递归继续输出结点的右子树结点下的各结点
			}
			printf(")");	//输出一个右括号
		} else { 
        	//若左子树为空，右子树不为空
			if(T->rchild!=NULL) { 
        
				printf("(");	//输出一个左括号
				ShowTree(T->lchild);	//通过递归继续输出结点的左子树结点下的各结点
				if(T->rchild!=NULL) { 
        		//若该结点的右子树不为空 
					printf(",");	//输出一个逗号
					ShowTree(T->rchild);	//通过递归继续输出结点的右子树结点下的各结点
				}
				printf(")");	//输出一个右括号
			}
		}
	}
}

/*主函数*/
int main() { 
        
	BTree T;
	T=NULL;
	printf("请输入二叉树的根结点：");
	T=CreateTree();		//建立二叉树
	printf("建立的二叉树如下：\n");
	ShowTree(T);		//通过广义表显示二叉树
}

依次输入各个结点的左右孩子结点，若结点不存在则输入0，例如树中结点d的左孩子结点不存在，结点f、g、h、i、j的左右孩子都不存在。 运行结果如下，结果通过广义表的定义显示：

例如对下图这个二叉树，进行先、中、后遍历： 1、先序遍历二叉树：

/*先序遍历二叉树*/
bool ProTree(BTree T) { 
        
	if(T==NULL)
		return false;			//递归结束
	else { 
        
		printf("%c ",T->data);	//输出当前结点的数据域
		ProTree(T->lchild);		//递归继续遍历该结点的左子树
		ProTree(T->rchild);		//递归继续遍历该结点的右子树
		return true;
	}
}

运行结果如下： 2、中序遍历二叉树：

/*中序遍历二叉树*/
bool InTree(BTree T) { 
        
	if(T==NULL)
		return false;			//递归结束
	else { 
        
		InTree(T->lchild);		//递归继续遍历该结点的左子树
		printf("%c ",T->data);	//输出当前结点的数据域
		InTree(T->rchild);		//递归继续遍历该结点的右子树
		return true;
	}
}

运行结果如下： 3、后序遍历二叉树：

/*后序遍历二叉树*/
bool PostTree(BTree T) { 
        
	if(T==NULL)
		return false;				//递归结束
	else { 
        
		PostTree(T->lchild);		//递归继续遍历该结点的左子树
		PostTree(T->rchild);		//递归继续遍历该结点的右子树
		printf("%c ",T->data);		//输出当前结点的数据域
		return true;
	}
}

运行结果如下：

层次遍历二叉树：

/*7、层次遍历二叉树*/
void LevelTree(BTree T) { 
        
	BTree q[MAXSIZE];		//MAXSIZE的值可自行定义
	int front=0,rear=0;		//初始化队头指针和队尾指针为0
	if(T!=NULL) { 
        			//当二叉树不为空
		q[rear++]=T;					//根结点入队
		while(front!=rear) { 
        			//当队列不为空时
			BTree head=q[front++];
			printf("%c ",head->data);	//访问队头结点的数据域
			if(head->lchild) 			//若当前结点的左孩子存在，将队头结点的左孩子入队
				q[rear++]=head->lchild;
			if(head->rchild) 			//若当前结点的右孩子存在，将队头结点的右孩子入队
				q[rear++]=head->rchild;
		}
	}
}

也是上图中的二叉树，进行层次遍历，运行结果如下：

二叉树的深度也是求最大深度，也是采用递归思想，分别递归计算左、右子树的深度，然后从左、右子树的深度中返回最大值，即为二叉树的深度，实现代码如下：

/*二叉树的深度*/
int DepthTree(BTree T) { 
        
	int ldepth=0,rdepth=0;		//分别代表左、右子树的深度，初始值都为0
	if(T==NULL)
		return 0;
	else { 
        
		ldepth=DepthTree(T->lchild);	//递归继续统计结点的左子树深度
		rdepth=DepthTree(T->rchild);	//递归继续统计结点的右子树深度
		if(ldepth>rdepth)		//求最大深度
			return ldepth+1;
		else
			return rdepth+1;
	}
}

对于上图中的二叉树，运行结果如下：

求一个二叉树的叶子结点数，也是递归方法实现，我们知道若一个结点的左、右孩子都为空，则这说明这是一个叶子结点，通过递归，最后return返回叶子结点数，实现代码如下：

/*二叉树的叶子结点数*/
int LeavesNum(BTree T) { 
        
	if(T!=NULL) { 
        	//当根结点不为空
		if(T->lchild==NULL&&T->rchild==NULL)	//若一个结点的左、右孩子都为空，即这是一个叶子结点 
			return 1;
	}
	return (LeavesNum(T->lchild)+LeavesNum(T->rchild));
}

对于上图中的二叉树，运行结果如下：

也是递归，当二叉树不为空时，二叉树的结点总数等于左子树结点个数+右子树结点个数，然后加1（二叉树的根结点），实现代码如下：

/*求二