数据结构-二叉树

本节目录
1.树的结构
2.树的遍历
3.并查集

树的结构
·一棵树是由n（n>0）个元素组成的结构，其中：
·（1）每个元素称为结点（node）
·（2）有一个特定的结点，称为根节点或树根root
·（3）除根结点外，其余结点能分成m（m>=0）个互不相交的有限集合T0,T1,T2,…Tm-1。其中的每个子集又都是一棵树，这些集合称为这棵树的子树。

树的基本概念
·树的递归定义的
·在用图形表示的树型结构中，对两个用线段（称为树枝）连接的相关联的结点，称为上端结点为下端结点的父结点，称下端结点为上端结点的子结点。称一个父节点的多个子节点为兄弟结点。
·一棵树至少有1个结点，每个结点的子节点可能有0~n个
·根结点–没有父结点
·叶结点–没有子结点
有根树/无根树
·实际上，树还可以不设置根节点，此时被称为无根树，任意一点均可作为根节点。

·树中可以保证任意两点有且仅有一条路径相连。
·二叉树就是每个节点至多有两个儿子的有根树。
·我们称左边的子节点为左儿子，右边的为右儿子。
·以某节点的左二子为根的子树称为该节点的左子树，右子树同理。
·完全二叉树：除最后一层外，所有层都是满的，最后一层的所有节点从左到右排
·满二叉树：所有层都是满的，也即除了最后一层外，所有节点都有两个子节点。
·满二叉树是一种特殊的完全二叉树。
二叉树的性质
·有N个结点的树的边数是N-1
·二叉树的第i层结点数最多是2^i-1
·有N个结点的完全二叉树的叶结点树是N/2
树的存储–方法1
·方法1：存储父结点和子结点信息
·用数组来存储树的结构
·int fa[N]; //fa[i]记录i结点的父节点编号
·vector son[N]; //son[i]是一个结构体，里面保存i结点的所有子节点编号
二叉树的存储–方法2
·一般的树需要结构体等方式存储，但是二叉树却有一个简单的方式，即数组下标。
·如图上的这颗二叉树，观察父亲和两个儿子的下标关系，可以发现什么？
·父亲节点下标为i，则左儿子下标为2i，右儿子下标为2i+1。
·我们可以在数组里存储信息，而不存在的节点则
设置空标记，如0或-1。
·以1号结点为根节点，每个结点2与2+1为左右子结点
·结点对应的数组位置为0则表示该结点不存在，否则数组内的数据为该结点存储的内容
树的存储–方法3
·方法3：将树当成图，可以使用所有的图存储方法来存储树
·1234找树根和孩子
二叉树的遍历
·树的遍历–访问一遍树上的所有节点，对每个访问到的节点进行某种 *** 作（如输出编号）。通用DFS或BFS的方式来实现。
·二叉树的遍历则右三种不同的遍历：前（先）序遍历，中序遍历，后序遍历
·前、中、后实际表示了父节点相对于左右儿子节点的遍历顺序。
·前序遍历：先父亲节点，再依次左子树及右子树
·A B D E C F G
·中序遍历：先左子树，再父节点，最后右子树
·D B E A F C G
·后序遍历：先左子树，再右子树，最后父节点
·D E B F G C A

二叉树的前序遍历
·前序遍历：先遍历父亲节点，再依次遍历左子树及右子树。
·我们的目标是遍历整个树，而遍历过程中又要遍历子树–递归！DFS！
·函数DFS(x)表示遍历以x为根的树。
·过程中先输出父亲节点，再DFS自己的左右儿

char TreeNode[100];
for(int i=1;i<=7;++i) TreeNode[i]='A'+i-1;

void preDFS(int root)
{
	printf("c",TreeNode[root]);
	if(TreeNode[root*2]) preDFS(root*2);
	if(TreeNode[root*2+1]) preDFS(root*2+1);
}

·ABDECFG
遍历顺序之间的转换
·已知前、中、后序遍历中的任意两个，如何求另一个？
·前序、中序、后序遍历顺序有什么特点？
·前序遍历：A—BDE—CFG
·中序遍历：DBE—A—FCG
·后序遍历：DEB—FGC— A
已知前、中，求后
·前序遍历：A—BDE—CFG
·中序遍历：DBE—A—FCG
·1.根据前序遍历，第一个出现的A一定是根
·2.用A去中序遍历中划分出DBE和FCG两个子树
·3.再用这两个子树去前序遍历中划分出BDE和CFG
·4.对于子树1，前中序遍历分别是BDE、DBE
·5.对于子树2，前中序遍历分别是CFG、FCG
已知中、后，求前
·中序遍历：DBE—A—FCG
·后序遍历：DEB—FGC—A
·1.根据后序遍历，最后出现的A一定是根
·2.用A去中序遍历中划分出DBE和FCG两个子树
·3.再用这两个子树去后序遍历中划分出DEB和FCG
·4.对于子树1，前中序遍历分别是DBE、DBE
·5.对于子树2，前中序遍历分别是FCG、FGC
代码实现

#include 
using namespace std;

char s[15],t[15];//s存中序，t存后续

void dfs(int l1,int r1,int l2,int r2)
{
	//当前考虑中序的[l1,r1]，后序的[l2,r2]
	//这两段字符串表示同一个子树的中序和后序遍历
	if(l1 > r1) return;
	char root = t[r2];//子树的根为后续遍历的最后一个元素
	printf("%c",root);//输出根
	for(int i=l1;i<=r1;++i)
	{
		if(s[i]==root)//找到根的位置
		{
			int len1=(i-1)-l1+i;
			int len2=r1-(i+1)+1;
			dfs(l1,i-1,l2,l2+len1-1);
			dfs(i+1,r1,l2+len1,r2-1);
			break; 
		}	
	} 
}

int main()
{
	while(scanf("%s%s",s,t)!=EOF) 
	{
		int len = strlen(s);
		dfs(0,len-1,0,len-1);
		printf("\n");
	}
	return 0;
}