1.二叉树相关操作

（1）初始化一棵空二叉树；
（2）销毁以T为根的二叉树；
（3）插入以parent为双亲，x为左孩子的结点；
（4）删除以parent为双亲的左子树；
（5）在二叉树上查找结点值为x的结点；
（6）前序遍历二叉树；
（7）中序遍历二叉树；
（8）后序遍历二叉树；
（9）层次遍历二叉树。

2.二叉树的存储结构

2.1. 二叉树的顺序存储结构

顺序存储结构就是开辟一个连续的空间来存储二叉树的数据。由二叉树的性质5来看，对于满二叉树和完全二叉树可以进行编号，同时对编号的操作可以方便的找到结点之间的关系。对于一般的二叉树来说，可以通过补充没有数据的结点来“完全化”，进而进行编号。但是此时对空间会进行一定的浪费，最坏的情况是右单支树的情况。
结论：顺序存储结构适合存储完全二叉树，方便查找双亲和孩子。

2.2. 二叉链表存储结构

通过指针域中左孩子和右孩子的指针来找到该结点的左孩子和右孩子的存储地址。
性质：在含有n个结点的二叉链表中，有n+1个空指针域
结论：二叉链表方便找到孩子，但是不方便找到双亲。

2.3 三叉链表存储结构

在二叉链表的基础上，增加一个指向双亲结点的指针。
结论：方便找到孩子和双亲结点。

3.二叉树的遍历的操作

二叉树的遍历就是，按照某种顺序遍历二叉树中每一个结点，使得每个结点都被有且仅有一次被访问。遍历操作可以将非线性结构转换成线性结构

3.1. 递归遍历二叉树

（1）先序遍历；（2）中序遍历；（3）后序遍历

//递归遍历二叉树
void preorder(BiTree T)//先序遍历DLR
{
	if (T)//当T为空树的时候结束——递归结束标志
	{
		printf("%c", T->data);//访问根结点
		preorder(T->lchild);//先序遍历左子树
		preorder(T->rchild);//先序遍历右子树
	}

}
void inorder(BiTree T)//中序遍历LDR
{
	if (T)//当T为空树的时候结束——递归结束标志
	{
		inorder(T->lchild);//中序遍历左子树
		printf("%c", T->data);//访问根结点
		inorder(T->rchild);//中序遍历右子树
	}
}
void postorder(BiTree T)//后序遍历LRD
{
	if (T)//当T为空树的时候结束——递归结束标志
	{
		inorder(T->lchild);//后序遍历左子树
		inorder(T->rchild);//后序遍历右子树
		printf("%c", T->data);//访问根结点
	}
}

3.2. 非递归遍历二叉树

3.2.1. 基于任务分析的二叉树遍历非递归算法

每一个子树的根结点担负着三个任务：左子树的遍历、根结点的访问和右子树的遍历。以中序遍历为例：
根结点的任务按照性质分成：遍历和访问，用1和0来表示。
进栈时，对非空结点按照中序布置任务；出栈的时候，根据任务的性质来处理任务。
【算法实现】

//非递归遍历二叉树
void InOrder_iter(BiTree T)
{
	//利用栈实现中序遍历二叉树，T为指向二叉树的根结点的头指针
	Stack S;
	StackInit(&S);
	STDataType e;
	e.ptr = T; e.task = 1;//e是一个栈元素的结构体变量
	if (T)StackPush(&S, e);//布置初始任务
	while (!StackEmpty(&S))//中序遍历
	{
		e = StackTop(&S);
		StackPop(&S);
		if (e.task == 0)printf("%c", e.ptr->data);//e.task == 0处理访问任务
		else
		{
			BiTree p = e.ptr;
			e.ptr = p->rchild;
			if (e.ptr)StackPush(&S, e);//遍历右子树
			e.ptr = p; e.task = 0;
			StackPush(&S, e);//访问根结点
			e.ptr = p->lchild; e.task = 1;
			if (e.ptr)StackPush(&S, e);//遍历左子树
		}//end_else
	}//end_while
}

3.2.2. 基于搜索路径分析的二叉树遍历的非递归算法

从二叉树的遍历可以知道，每个结点在遍历的过程中，都有三次相遇的机会。以后序遍历为例：第一次相遇是进栈前，如果该结点的左子树不为空，则该结点进栈；如果左子树遍历结束，则回到栈顶，第二次相遇；如果栈顶结点的右子树不为空，则开始遍历右子树。右子树遍历结束，回到栈顶，第三次相遇，此时访问该栈顶的结点的数据并弹出。用标记字符数组，标记第一次相遇为L，标记第二次相遇为R，当当标记数组为R的时候，表示此结点遍历结束，访问并弹出。
（1）进栈：第1次相遇的结点地址进栈，标记L
（2）修改标记：第2次相遇，将标记L改为R
（3）出栈并访问。
【算法实现】

//寻找子树最左下方的结点
BiTree PriGoFarLeft(BiTree T, Stack* S, char c[])
{
	if (!T)return NULL;
	while (T->lchild)//找到
	{
		StackPush(S, T); c[S->_top] = 'L';//第一次遇到，进栈
		T = T->lchild;
	}
	return T;
}
void NrPostorder(BiTree T)//基于路径分析的后序遍历非递归算法
{
	BiTree t;
	Stack S;
	StackInit(&S);
	char lrtag[STACK_INITMAXSIZE] = { 0 };//标记数组
	t = PriGoFarLeft(T, &S, lrtag);
	while (t)
	{
		lrtag[S._top] = 'R';//第二次遇到，修改标记
		//找t的右子树最左下的结点
		if (t->rchild)t = PriGoFarLeft(t->rchild, &S, lrtag);
		else
		{
			while (!StackEmpty(&S) && lrtag[S._top] == 'R')//第三次遇到，出栈，并输出
			{
				StackPop(&S);
				printf("%c", t->data);
			}
		}
		if (!StackEmpty(&S))t = StackTop(&S);
		else t = NULL;
	}//end_while
}

3.3. 二叉树层次遍历算法

层次遍历就是从上到下，从左到右遍历二叉树。这就符合先进先出的原则，即为队列结构，将结点依次进队列在依次出队列即可。
【算法实现】

//层次遍历二叉树
void LayerBitree(BiTree T)
{
	Queue Q;
	InitQueue(&Q);//初始化队列
	if (T)EnQueue(&Q, T);//进队列
	while (!QueueEmpty(&Q))
	{
		BiTree p = DeQueue(&Q); printf("%c", p->data);//出队列，访问结点
		if (p->lchild)EnQueue(&Q, p->lchild);//左子树根进队列
		if (p->rchild)EnQueue(&Q, p->rchild);//右子树根进队列
	}//end_while
}

4.二叉树遍历算法的应用

4.1. 创建二叉树的二叉链表存储结构

4.1.1. 以“根左子树右子树”的字符串形式读入结点值创建二叉链表的递归算法

按先序遍历的顺序（空节点以#表示）读入每个结点的值，将前序遍历算法中的访问结点的语句改为创建新结点即可。
【算法实现】

void crt_tree(BiTree* T)//递归形式
{
	char ch = getchar();
	if (ch == '#')*T = NULL;
	else
	{
		//创建根结点
		*T = (BiTree)malloc(sizeof(BiNode));
		if (*T == NULL)
		{
			perror("malloc fail");
			return;
		}
		(*T)->data = ch;
		//创建左子树
		crt_tree(&((*T)->lchild));
		//创建右子树
		crt_tree(&((*T)->rchild));
	}//end_else
}

4.1.2. 非递归算法创建二叉树的二叉链式结构

（1）二叉树的广义表的字符串创建二叉链表
结点值出现的顺序与前序遍历一致。如果左右子树均为空，则子树的形式为“根”。由于父亲结点创建在左孩子结点之前，用标志量tag表示。当遇到左括号，先将前面创建的父亲结点进栈，令key=1，开始创建左子树；遇到逗号，表示左孩子结点已经创建完毕，令key=2，开始创建右子树；遇到右圆括号，表示子树创建完成，将子树根出栈。遇到字母，创建叶子结点。如果key=1，将叶子结点的链接为父亲结点的左孩子；如果key=2，将叶子结点链接为栈顶结点的右孩子，直至栈为空。
【算法实现】

void CreateBiTree(BiTree* BT, char* s)//二叉树的广义表的字符串创建二叉链表
{
	char ch;
	int i,key;
	struct
	{
		BiTree node[50];
		int top;
	}ptrNode;//顺序栈用于存储创建过程中的子树根的地址
	ptrNode.top = -1;
	BiTree p = NULL;
	*BT = NULL;
	ch = s[0];
	i = 1;
	while (ch != '0')
	{
		switch (ch)
		{
		case '(':
			ptrNode.node[++ptrNode.top] = p;//遇到左括号，结点地址进栈
			key = 1;//标记创建左子树根
			break;
		case ')':
			ptrNode.top--;//遇到右括号，表示右子树创建完成
			break;
		case ',':
			key = 2;//标价创建右子树根
			break;
		default:
			//创建叶子结点
			p = (BiTree)malloc(sizeof(BiNode));
			if (p == NULL)
			{
				perror("malloc fail");
				return;
			}
			p->data = ch;
			p->lchild = p->rchild = NULL;
			//创建根结点
			if (*BT == NULL)*BT = p;
			else
			{
				if (key == 1)//创建左子树根
					ptrNode.node[ptrNode.top]->lchild = p;
				else if (key == 2)//创建右子树
					ptrNode.node[ptrNode.top]->rchild = p;
			}
		}//end_switch
		ch = s[i++];
	}//end_while
}

（2）读入边来创建二叉链表的非递归算法（层次遍历的应用）
按照从上到下，从左到右的顺序依次输入二叉树的边，边的信息为（father，child，lrflag），其中father为父亲结点，child表示孩子结点，lrflag为0表示左孩子，1表示为右孩子。该算法需要一个队列保存已经创建好的结点地址。
算法核心：
①每读一条边，生成孩子结点，并作为叶子结点，之后将该结点的指针保存在队列中。
②从队头找到该结点的双亲结点指针。如果队头不是，出队列，直至队头是该结点的双亲结点指针。再按lrflag的值建立双亲节点安的左右孩子关系。
【算法实现】

void Creat_BiTree(BiTree* T)//读入边来创建二叉链表——层次遍历的应用
{
	Queue Q;
	InitQueue(Q);
	*T = NULL;
	char fa, ch;
	int lrflag;
	scanf("%c%c%d", &fa, &ch, &lrflag); getchar();
	while (ch != '#')
	{
		BiTree p = (BiTree)malloc(sizeof(BiNode));
		if (p == NULL)
		{
			perror("malloc fail");
			return;
		}
		p->data = ch;//创建孩子结点
		p->lchild = p->rchild = NULL;//做成孩子结点
		EnQueue(Q, p);//指针入队列
		if (fa == '#')*T = p;//创建根结点
		else
		{
			BiTree s = GetHead(Q);//取队列头元素（指针值）
			while (s->data != fa)//在队列中找到双亲结点
			{
				DeQueue(Q);
				s = GetHead(Q);
			}
			if (lrflag == 0)s->lchild = p;//链接左孩子结点
			else s->rchild = p;//链接右孩子结点
		}
		scanf("%c%c%d", &fa, &ch, &lrflag); getchar();
	}//end_while
}

（3）由二叉树的遍历序列确定二叉树（先序遍历的应用）
问题：已知二叉树的遍历序列，如何确定二叉树？

• 已知二叉树的先序序列和中序序列，可唯一确定一棵二叉树。
  证明：通过根结点+中序序列可以知道该根结点左右子树的结点以及左右子树结点的先序关系和中序关系。通过递归算法，可以唯一确定一棵二叉树

构造该二叉树的过程：
①根据先序序列的第一元素建立根结点。
②在中序序列中找到该元素，确定根结点的左右子树的中序序列。
③在先序序列中确定左右子树的先序序列。
④由左子树的先序序列和中序序列建立左子树。
⑤由右子树的先序序列和中序序列建立右子树。

void CrtBT(BiTree* T, char pre[], char ino[], int ps, int is, int n)//由二叉树的遍历序列确定二叉树（先序遍历的应用）
{
	//pre[ps..ps+n-1]为二叉树的先序序列，n是序列字符个数
	//ino[is..is+n-1]为二叉树的中序序列
	//ps是先序序列的第一个字符的位置，初值为0，is是中序序列的第一个字符的位置，初始值为0
	if (n == 0)*T = NULL;
	else//在中序序列中查询根，k为-1，没有找到，否则k为根在中序序列中的位置
	{
		int k = Search(ino, pre[ps]);
		if (k == -1)*T = NULL;
		else
		{
			if (!(*T = (BiTree)malloc(sizeof(BiNode))))exit(0);
			(*T)->data = pre[ps];//建立根结点
			if (k == is)(*T)->lchild = NULL;//没有左子树
			//创建左子树
			else CrtBT(&((*T)->lchild), pre, ino, ps + 1, is, k - is);//k-is 表示左子树的结点数
			if (k == is + n - 1)(*T)->rchild = NULL;//没有右子树
			//创建安右子树
			else CrtBT(&((*T)->rchild), pre, ino, ps + 1+(k-is), k + 1,n-(k-is)-1);

		}
	}
}

• 由二叉树的后序序列和中序序列可确定唯一确定一棵二叉树
• 由二叉树的先序序列和后序序列不能唯一确定一棵二叉树

4.2. 有算术表达式创建表达式二叉链表（后序遍历的应用）

先序序列为原式表达式的前缀表达式；中序序列为原式表达示的中缀表达式；后序序列为原式表达式的后缀表达式。
表达式二叉树的特点如下。
（1）所有的叶子结点均为操作数。
（2）所有的分支结点均为运算符，左子树的计算结果是分支结点运算符的第一个操作数，右子树的计算结果是分支结点运算符的第二个操作数。
（3）表达式的值的计算顺序按后序遍历的顺序进行。
用两个栈，一个用于存储运算符，一个用于存储子树根结点的地址。
【算法实现】

void CrtExptree(BiTree* T, char exp[])//主函数：创建表达式二叉链表
{
	SubTreeStack PTR;//PTR是子树栈
	SqCharStack PND;//PND是运算符栈
	char* p = exp;
	char ch, c;
	ch = p[0];
	int_CharStack_exp(&PND); pushChar(&PND, '#');//初始化运算符栈
	int_SubtreeStack_exp(&PTR);//初始化子树栈
	while ((c = getChar_top(PND)) != '#' || ch != '#')
	{
		if (!IN(ch))CrtNode(T, &PTR, ch);//ch不是运算符，建子结点并进入PTR栈
		else
		{
			switch (ch)//ch是运算符
			{
			case '('://'('运算符进运算符栈
				pushChar(&PND, ch); break;
			case ')'://')'运算符，出栈，直到运算符'('结束出栈
				popChar(&PND, &c);
				while (c != '(')
				{
					CrtSubtree(T, &PTR, c);//建二叉树并入PTR栈
					popChar(&PND, &c);
				}
				break;
			default ://其他运算符
				while ((c != getChar_Top(PND)) != '#' && precede(c, ch))
				{
					//当栈顶运算符不是#号
					//且当前运算符时优先级低于栈顶的运算符的时候
					//取栈顶的运算符建子树，再出栈
					CrtSubtree(T, &PTR, c);
					popChar(&PND, &c);
				}
				if (ch != '#')pushChar(&PND, ch);
			}//end_switch
		}//end_else
		if (ch != '#')
		{
			p++;
			ch = *p;
		}
	}//end_while
	popSubtree(&PTR, T);//将二叉树根地址出栈
}
void CrtNode(BiTree* T, SubTreeStack* PTR, char ch)//子函数：创建叶子结点的函数
{
	//建立子结点并进PTR栈
	if (!(*T = (BiTree)malloc(sizeof(BiNode))))exit(0);
	(*T)->data = ch; (*T)->lchild = (*T)->rchild = NULL;
	pushSubtree(PTR, *T);
}
void CrtSubtree(BiTree* T, SubTreeStack* PTR, char c)//子函数：创建子树函数
{
	//建立子树并入PTR栈
	BiTree lc, rc;
	if (!(*T = (BiTree)malloc(sizeof(BiNode))))exit(0);
	(*T)->data = c;
	popSubtree(PTR, &rc); (*T)->rchild = rc;
	popSubtree(PTR, &lc); (*T)->lchild = rc;
	pushSubtree(PTR, *T);
}

4.3. 二叉树遍历算法的其他应用

4.3.1.求二叉树深度

分析：基于二叉树的后序遍历，若二叉树为空，则它的深度为0；否则，可以求左子树和右子树的最大深度并加1.
【算法实现】

int depth(BiTree T)//求二叉树深度
{
	if (T == NULL)return 0;
	else
	{
		int depl = depth(T->lchild);//左子树深度
		int depr = depth(T->rchild);//右子树深度
		if (depl > depr)return depl + 1;
		else return depr + 1;
	}
}

4.3.2. 求二叉树的叶子结点数

分析：基于二叉树的中序遍历，若二叉树为空，则它的叶子结点数为0；否则，判断一个结点是否为叶子结点，如果是计算器加1
【算法实现】

void leafcount(BiTree T, int* count)//求二叉树的叶子结点数
{
	if (T == NULL)return;
	else
	{
		leafcount(T->lchild, count);
		if (T->lchild == NULL && T->rchild == NULL)(*count)++;//去掉判断条件，计算的就是整个二叉树结点的数
		leafcount(T->rchild, count);
	}
}

4.3.3. 以凹入表的形式显示二叉树

分析基于二叉树的先序遍历，对每一个结点有所在的层确定线段的长短。
【算法实现】

void dispBitree(BiTree T, int level, char c)//以凹入表的形式显示二叉树
{
	int i, k;
	if (T)
	{
		for (i = 1; i < level; i++)putchar(' ');
		printf("%c(%c)+", T->data, c);//显示结点和标注
		for (k = i + 4; k < 20; k++)putchar('-');
		putchar('\n');
		dispBitree(T->lchild, level + 2, 'L');
		dispBitree(T->rchild, level + 2, 'R');
	}
}

4.3.4. 以广义表的形式显示二叉树

分析：二叉树的广义表形式的结点顺序与二叉树的前序遍历一致，只需要在前序遍历算法的基础上判断何时输出左圆括号和右圆括号以及逗号即可。
【算法实现】

void gListBiTree(BiTree T)//以广义表形式显示二叉树
{
	if (T)
	{
		printf("%c", T->data);
		if (T->lchild != NULL || T->rchild != NULL)
		{
			printf("(");
			gListBiTree(T->lchild);
			if (T->rchild)
			{
				printf(",");
				gListBiTree(T->rchild);
			}
			printf(")");
		}
	}
}

4.3.5. 求任意结点的祖先

分析：按照后序遍历，一旦找到指定的结点，只需将它的所有结点按由近到远的顺序进栈即可。
【算法实现】

int an_BitreeNode(BiTree T, char x, STACK* S)//求二叉树任一结点的祖先
{
	//求x的祖先
	if (T == NULL)return 0;
	if (T->data == x)return 1;
	if (an_BitreeNode(T->lchild, x, S) == 1 || an_BitreeNode(T->rchild, x, S) == 1)
	{
		//一旦在T的左子树或右子树上找到x，x的双亲进栈
		push(S, T->data);//祖先进栈
		return 1;
	}
	return 0;
}