二叉树结构定义

typedef struct BiTNode{
	int data;
	struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree;

树的递归遍历

先序遍历

按照“根-左-右”顺序

void preOrderTraverse(BiTree T) {
	if (T != NULL) {
		cout << T -> data;
		preOrderTraverse(T->lchild);
		preOrderTraverse(T->rchild);
	}
}

中序遍历

按照“左-根-右”顺序

  void preTraverse(BiTree T) {
      if (T != NULL) {
          preTraverse(T->lchild);
          cout << T -> data;
          preTraverse(T->rchild);
      }
  }

后序遍历

按照“左-右-根”顺序

void postOrderTraverse(BiTree T) {
	if (T != NULL) {
		postOrderTraverse(T->lchild);
		postOrderTraverse(T->rchild);
		cout << T -> data;
	}
}

层序遍历

设置一个队列，根入队后出队，出队时其左右孩子入队，判断左右孩子是否为空，如果非空，则入队。直至队列为空。

void seqOrderTraverse(BiTree T) {
	SqQueue Q;
	InitQueue(Q);
	EnQueue(Q, T); 
	while(Q.rear != Q.front) {
		BiTree root;
		DeQueue(Q, root);
		cout << root -> data;
		if (root -> lchild)
			EnQueue(Q, root->lchild);
		if (root -> rchild)
			EnQueue(Q, root->rchild);
	}
}

树的非递归遍历

先序遍历

1. 先将根节点入栈
2. 循环访问左子树，执行入栈操作，直至左子树为空
3. 栈不为空，根结点出栈，访问右子树

void PreOrder2(BiTree T) {
	SqStack S;
	InitStack(S);
	BiTree p = T;
	while(p || !stackEmpty(S)) {
		if (p) {
			cout << p -> data;
			Push(S, p);
			p = p -> lchild;
		} else {
			Pop(S, p);
			p = p -> rchild; 
		}
	}  
}

中序遍历

思路同中序遍历类似。

void InOrder2(BiTree T) {
	SqStack S;
	InitStack(S);
	BiTree p = T;
	while(p || !stackEmpty(S)) {
		if (p) {
			Push(S, p);
			p = p -> lchild;
		} else {
			Pop(S, p);
			cout << p -> data;
			p = p -> rchild;
		}
	}
}

后序遍历

1. 沿着根的左孩子，依次入栈，直到左孩子为空
2. 读取栈顶元素，若其右孩子不空且未被访问，继续执行1，否则栈顶元素出栈并访问

void postOrder2(BiTree T) {
	SqStack S;
	InitStack(S);
	BiTree p = T;
	BiTree r = NULL;
	while(p || !stackEmpty(S)) {
		if (p) {
			Push(S, p);
			p = p -> lchild;
		} else {
			p = S.btData[S.top];	//读取栈顶元素 
			if (p -> rchild && p -> rchild != r) {
				//若右子树存在，且未被访问过
				p = p -> rchild; 
			} else {
				//弹出结点并访问 
				Pop(S, p);
				cout << p -> data;
				r = p;	//记录最近访问结点
				p = NULL; //结点访问完后，重置p指针 
			}
		}
	} 
}

二叉树相关题目

设计一个二叉树自下而上、从右到左的层序遍历算法

思路：
只需在bfs时，将出队的元素放入堆栈中，最后输出堆栈元素即可。

void InvertLevel(BiTree T) {
	SqStack S;
	SqQueue Q;
	if (T != NULL) {
		InitStack(S);
		InitQueue(Q);
		EnQueue(Q, T);
		while(Q.rear != Q.front) {
			BiTree root;
			DeQueue(Q, root);
			Push(S, root);
			if (root -> lchild)
				EnQueue(Q, root->lchild);
			if (root -> rchild)
				EnQueue(Q, root->rchild);	
		}
	}
	while(!stackEmpty(S)) {
		BiTree root;
		Pop(S, root);
		cout << root -> data;
	}
}

设计一个非递归算法求二叉树的高度

思路：
bfs层序遍历中，设置一个结点指针指向当前最右结点，每次出队时与此结点比较，如果相等，则表明遍历到当前层末尾，层数加1，并让其指向下一层的最右结点，直至结束。

int depth(BiTree T) {
	SqQueue Q;
	int ans = 0;
	int last = 1;
	if (T == NULL)
		return ans;
	InitQueue(Q);
	EnQueue(Q, T);
	while(Q.rear != Q.front) {
		BiTree root; 
		DeQueue(Q, root);
		if (root -> lchild)
			EnQueue(Q, root -> lchild); 
		if (root -> rchild)
			EnQueue(Q, root->rchild);
		if (Q.front == last) {
			ans ++;
			last = Q.rear;
		}
	}
	return ans;
}

递归写法：

int depth2(BiTree T) {
	if (T == NULL)
		return 0;
	return max(depth(T->lchild), depth(T->rchild)) + 1; 
}	

根据先序和中序遍历建立二叉树

思路：

1. 根据先序遍历确定树的根节点
2. 根据根节点在中序序列中划分出二叉树的左右子树，然后根据左右子树结点在先序序列中确定子树的根节点。重复步骤1，知道每颗子树仅有一个结点为止。

BiTree PreInCreate(char pre[], char in[], int pl, int pr, int il, int ir) {
	// pl, pr 下标均从1开始 
	BiTree root = (BiTree)malloc(sizeof(BiTNode));
	root -> data = pre[pl];
	int i;
	for (i = il; in[i] != root -> data; i ++); 
	int lLen = i - il;	//中序数列中左子树的个数
	int rLen = ir - i;  //中序数列中右子树的个数
	if (lLen)
		root -> lchild = PreInCreate(pre, in, pl + 1, pl + lLen, il, il + lLen - 1);
	else
		root -> lchild = NULL;
	if (rLen)
		root -> rchild = PreInCreate(pre, in, pr - rLen + 1, pr, ir - rLen + 1, ir);
	else
		root -> rchild = NULL;
	return root;
}

根据先序遍历确定一个满二叉树的后序遍历

思路：
因为满二叉树左右子树结点个数相同且总节点数为奇数个，只要能确定根节点就可以确定后序序列。

1. 找出先序序列的根节点，将其放入后序序列数组末尾；
2. 将根节点之后的节点分成左右两堆，在分别执行上一步
3. 直至全部处理完

void PreToPost(char *pre, char *post, int l1, int h1, int l2, int h2) {
	int half;
	if (l1 <= h1) {
		post[h2] = pre[l1];
		half = (h1 - l1) / 2;
		PreToPost(pre, post, l1 + 1, l1 + half, l2, l2 + half - 1); //递归左子树 
		PreToPost(pre, post, l1 + half + 1, h1, l2 + half, h2 - 1); //递归右子树 
	}
}

判断一个二叉树是否是完全二叉树

思路：
bfs层序遍历，如果一个空节点后面还有结点，则不是完全二叉树。

bool IsComplete(BiTree T) {
		SqQueue Q;
		InitQueue(Q);
		if (T) {
			EnQueue(Q, T);
			while(Q.rear != Q.front) {
				BiTree root;
				DeQueue(Q, root);
				if (root) {
					EnQueue(Q, root->lchild);
					EnQueue(Q, root->rchild);
				} else {	//结点为空看其后面是否还有非空结点
					while(Q.rear != Q.front) {
						DeQueue(Q, root);
						if (root)	return false;
					}
				}
			}
		}
		return true;

计算给定二叉树的所有双分支结点

思路：
当前结点是双分支结点时累增并向下左右递归。

int calcDNode(BiTree T) {
	if (T == NULL) {
		return 0;
	} else if (T -> lchild != NULL && T->rchild != NULL) {
		//双分支结点
		return calcDNode(T->lchild) + calcDNode(T->rchild) + 1;
	} else {
		//单分支结点或叶子结点 
		return calcDNode(T->lchild) + calcDNode(T->rchild);
	}
}

将二叉树中所有左右子树交换

思路：
现递归左右子树，然后交换左右孩子结点。

void swap(BiTree T) {
	if (T) {
    	//递归左右子树
		swap(T->lchild);
		swap(T->rchild);
        //交换左右孩子结点
		BiTree temp = T->lchild;
		T->lchild = T->rchild;
		T->rchild = temp; 
	}
}

求先序遍历中第k个节点的值

思路：
记录一个全局遍历用来统计访问结点次数
当二叉树为空时，返回特殊字符‘#’
当$pos=K$时，返回数据
当$pos\ne K$，先递归左子树查找，若找到则返回，否则在右子树递归查找并返回结果。

int pos = 1;
char searchK(BiTree T, int K) {
	if (T == NULL)
		return '#';
	if (pos == K)
		return T -> data;
	pos ++;
	char ch = searchK(T -> lchild, K);
	if (ch != '#')
		return ch;
	return searchK(T -> rchild, K);
}

删除二叉树中以x为根的子树

思路：
层序遍历，如果当前结点子树有x，则递归删除其所在的子树。

void DeleteXTree(BiTree &T) {
	if (T) {
		DeleteXTree(T->lchild);
		DeleteXTree(T->rchild);
		free(T);
	}
}

void searchX(BiTree T, char x) {
	if (T) {
		if (T->data == x) {
			DeleteXTree(T);
			return ;
		}
		SqQueue Q;
		InitQueue(Q);
		EnQueue(Q, T);
		while(Q.rear != Q.front) {
			BiTree root;
			DeQueue(Q, root);
			if (root -> lchild) {
				if (root -> lchild -> data == x) {
					DeleteXTree(root -> lchild);
					root -> lchild = NULL;
				} else {
					EnQueue(Q, root->lchild);
				}
			}
			if (root -> rchild) {
				if (root -> rchild -> data == x) {
					DeleteXTree(root -> rchild);
					root -> rchild = NULL;
				} else {
					EnQueue(Q, root->rchild);
				}
			}
		}
	}
}

输出二叉树中值为x的所有祖先(x最多只有1个）

思路：
采用非递归的后序遍历，当结点值为x，此时栈中元素都是x的祖先。

void searchFather(BiTree T, char x) {
	SqStack S;
	InitStack(S);
	BiTree p = T;
	BiTree r = NULL;
	while(p || !stackEmpty(S)) {
		if (p) {
			Push(S, p);
			p = p -> lchild;
		} else {
			p = S.btData[S.top];	//读取栈顶元素 
			if (p -> rchild && p -> rchild != r) {
				//若右子树存在，且未被访问过
				p = p -> rchild; 
			} else {
				//弹出结点并访问 
				Pop(S, p);
				// 查到x结点 
				if (p -> data == x) {
					//输出堆栈所有元素 
					while(!stackEmpty(S)) {
						cout << S.btData[S.top --] -> data;
					}
					return; 
				}
				r = p;	//记录最近访问结点
				p = NULL; //结点访问完后，重置p指针 
			}
		}
	} 
}

找到二叉树中任意p、q两结点的最近公共祖先

思路：
依然采用非递归后序遍历，当访问到p是，先将当前栈中元素保存到一个辅助栈中，再继续遍历到q，这是按照当前栈和辅助栈进行比对，第一个相同的即为所求。

BiTree searchCommon(BiTree T, char cp, char cq) {
	if (T->data == cp || T->data == cq) {// 一个结点与根节点的LCA是其根节点 
		return T;
	}
	SqStack S, Temp;
	InitStack(S);
	InitStack(Temp);
	BiTree p = T;
	BiTree r = NULL;
	bool flag = false; // 判断是否访问过cp结点 
	while(p || !stackEmpty(S)) {
		if (p) {
			Push(S, p);
			if (!flag)	//如果还没有访问到cp结点就入辅助栈 
				Push(Temp, p); 
			p = p -> lchild;
		} else {
			p = S.btData[S.top];	//读取栈顶元素 
			if (p -> rchild && p -> rchild != r) {
				//若右子树存在，且未被访问过
				p = p -> rchild; 
			} else {
				//弹出结点并访问 
				Pop(S, p);
				if (!flag)
					Pop(Temp, p);
				if (p -> data == cp) {	// 访问到了cp结点，无需再往里添加 
					flag = true; 
				}
				// 访问到了cq结点，此时将辅助栈中的元素和当前栈的元素对比，找第一个相同的 
				if (p -> data == cq) {
					// 如果cq祖先长度比cp祖先长度长，先将cq祖先出栈 
					if (S.top > Temp.top) {
						while(S.top != Temp.top) {
							Pop(S, p); 
						}
					// 反之则将cp祖先出栈  
					} else if (S.top < Temp.top) {
						while(S.top != Temp.top) {
							Pop(Temp, p);
						}
					}
					Pop(S, p);
					return p;
				}
				r = p;	//记录最近访问结点
				p = NULL; //结点访问完后，重置p指针  
			}
		}
	}
	return NULL;
}

求二叉树的最大宽度

思路：
通过层次遍历二叉树，每次统计一层结点的个数。

int calcWidth(BiTree T) {
	SqQueue Q;
	InitQueue(Q);
	EnQueue(Q, T);
	int ans = 0;
	while(Q.rear != Q.front) {
		int len = Q.rear - Q.front;
		ans = max(ans, len);
		for (int i = 1; i <= len; i ++) {
			BiTree root;
			DeQueue(Q, root);
			ans = max(ans, len);
			if (root -> lchild)
				EnQueue(Q, root -> lchild);
			if (root -> rchild)
				EnQueue(Q, root -> rchild);
		}
	}
	return ans;
}

判断两个二叉树是否相似

相似（T1和T2都是空二叉树，或者都只有1个根节点，或T1左子树与T2左子树相似且T1右子树与T2右子树相似）
思路：
递归遍历两棵二叉树相同的位置。T1和T2都为空 或者 都不空且T1的左右子树和 T2 的左右子树分别相似，则T1和T2相似

bool isSimilarTree(BiTree T1,BiTree T2){
	if(T1 == NULL && T2 == NULL) return true;
	if(!(T1 && T2)) return false; 	//如果有一个为空，返回false
	return  isSimilarTree(T1->lchild,T2->lchild) && isSimilarTree(T1->rchild,T2->rchild);
}

设计一个求二叉树的带权路径长度（WPL）算法

思路：
设置一个静态局部变量,用来保存所遍历根结点的带权路径长度，每遇到一个根结点，便把该结点的带权路径长度与static变量相加，当遍历完所有的根结点，便可得到该二叉树的WPL。

//二叉树结点数据类型
typedef struct BitNode
{
    int weight;
    BitNode *left,*right;
}BitNode,*BitTree;

int WPL(BitNode root) {
    return wplPreOrder(root,0);
}
int wplPreOrder(BitNode root,int deep) {
    static int wpl=0;
    if(root->left==NULL && root->right==NULL)//若为叶结点，则累积WPL
        wpl+=deep*root->weight;
    if(root->left!=NULL)
        wplPreOrder(root->left,deep+1);//如果左子树不为空，则对左子树进行递归遍历
    if(root->right!=NULL)
        wplPreOrder(root->right,deep+1);//如果右子树不为空，则对右子树进行递归遍历
    return wpl;//返回WPL值
}

将给定的表达式树（二叉树）转化为等价的中缀表达式

思路：
中序遍历二叉树，在必要的地方加入括号，表达式的最外层根节点和操作数对应的叶结点不需加括号。

void BitreeToE(BiTree T) {
	BitreeToExp(T, 1);
}

void BitreeToExp(BiTree T, int deep) {
	if (T == NULL)	return ;
	else if (!T->lchild && !T->rchild) {	//根节点 
		cout << T -> data;
	} else {
		cout << "(";
		BitreeToExp(T -> lchild, deep + 1);
		cout << T -> data;
		BitreeToExp(T -> rchild, deep + 1);
		cout << ")";
	}
}

Q.E.D.