树的基本概念 节点的度：节点的儿子数 树的度：Max{节点的度} 节点的高度：节点到各叶节点的最大路径长度 树的高度：根节点的高度 节点的深度（层数）：根节点到该节点的路径长度
树的遍历 ·前序遍历：根左右（x,Tl,Tr） ·中序遍历：左根右（Tl,x,Tr） ·后序遍历：左右根（Tl,Tr,x）
树的表示法
1.父节点数组表示法 （寻找父节点O（1），寻找儿子节点O（n））
2.儿子链表表示法 （为克服找父节点不方便，可牺牲空间换时间：）
3.左儿子右兄弟表示法 （通过左儿子右兄弟表示法将一个树存储方式变化为二叉树形态） （可将森林用类似的方法变化为二叉树（不同的树根节点用右兄弟的指针连接））
二叉树基本概念 ·n个节点的二叉树 高度h的取值范围是 [logn向下取整，n-1] ·高度为h的二叉树 节点数n的取值范围是 [h+1,2^(h+1)-1] ·满二叉树：高度为h且有2^(h+1)-1个节点 ·近似满二叉树：除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。 对每个结点i，满足： i / \ 2i 2i+1 因此可用数组存储（节点间关系显见），若为非近似满二叉树想要这样存储，没有该节点的位置可用空占位（牺牲空间）。 ·节点数（设度为i的节点数为ni） N = n0+n1+n2 = n0×0+n1×1+n2×2 +1 （ 节点数 = 分枝数+1 ） 可得结论 => ① n0 = n2 + 1 ② N = 2×n0 + n1 - 1 = 2×n2 + n1 + 1 在哈夫曼树中n1 = 0，则有N = 2×n0 - 1 = 2×n2 + 1
·含有n个结点二叉树的不同形态数Bn Bn = ∑（Bl × Bn-l-1） （左子树+右子树） =>卡特兰数Bn = 1/(n+1) × C（2n，n）
·二叉树与树 ①二叉树是一棵度不超过2的树。（错误，二叉树的儿子节点有左右之分） ②二叉树是一棵读不超过2的有序数。（错误，当只有1个儿子节点时二叉树也有左右之分）
ADT二叉树
·支持的运算
1.BinaryInit()：创建一棵空二叉树 2.BinaryEmpty(T)：判断二叉树T是否为空 3.Root(T)：返回根节点标号 4.MakeTree(x,T,L,R)：以x为根节点，L、R为左右子树构建新二叉树T 5.BreakTree(T,L,R)：将T拆分为根节点元素、左右子树三个部分 6.PreOrder(T)：前序遍历 7.InOrder(T)：中序遍历 8.PostOrder(T)：后序遍历 /*6、7、8在书上写的函数参数是（visit，T），没解释visit是什么，然后9,10,11是输出前中后序列表，参数只有T。博客这里就使用6,7,8函数名字当它作用就是输出列表了，略去了书上的9,10,11。*/ 9.Delete(T)：删除二叉树 10.Height(T)：二叉树高度 11.Size(T)：二叉树结点数
二叉树的实现
1.顺序存储结构 （从树根起，从上往下逐层编号存在数组里。适用于满二叉树，若非满二叉树，则用0占空。）
以该种存储方式得到的性质： 1.当且仅当i = 1时为根节点。 2.不为1时，父节点为i/2（向下取整） 3.左儿子为2i 4.右儿子为2i+1 5.i为奇数且不为1时，左兄弟为i-1 6.i为偶数时，右兄弟为i+1
2.结点度表示法 （将所有结点以后序列表排列，给每个结点附加一个0~3的整数表示状态，0表示叶节点，1表示有一个左儿子，2表示有一个右儿子，3表示有两个儿子。）
得到性质： 1. i-1 为右儿子结点 2.必然有左儿子在 i 前，父节点在 i 后
3.用指针实现
线索二叉树 （在每个结点中增加指向在某种遍历下其前驱和后继结点的指针）
线索：所引入的非空指针称为线索。 线索二叉树：加上了线索的二叉树称为线索二叉树。 线索标志位：为了区分一个结点的指针是指向其儿子结点的 指针，还是指向其前驱或后继结点的线索,在每个结点中增 加2个位—leftThread、rightThread分别称为左、右线索标志位。 线索化：对一棵非线索二叉树以某种次序遍历使其变为一棵 线索二叉树的过程称为二叉树的线索化。
二叉树线索化： 由于线索化的实质是将二叉树中的空指针改为指向其前 驱结点或后继结点的线索(并做上线索标志)，而一个结 点的前驱或后继结点只有遍历才能知道，因此线索化的 过程是在对二叉树遍历的过程中修改空指针的过程。 为了记下遍历过程中访问结点的先后次序，可引入指针p 指引遍历，而引入指针pre跟踪p的前驱。首先将pre和p 初始化为遍历的第一结点。然后让p往遍历的方向走找 pre的后继。一旦找到，则它们互为前驱和后继，建立相 应线索。接着将p赋给pre，重复下去直到遍历结束。 二叉树的中序线索化 增加一个头结点，其LeftChild指针指向二叉树的根结 点，其RightChild指针指向中序遍历的最后一个结点。 而最后一个结点的RightChild指针指向头结点。这样一 来，就好象为二叉树建立了一个双向线索链表，既可从 中序遍历的第一个结点起进行中序的遍历；也可从中序 遍历的最后一个结点起进行逆中序的遍历。
在树的运算实现中常常用到递归。 如：
1.求二叉树叶结点数
2.求二叉树高度 H = Max{Hl，Hr} + 1
3.求二叉树结点数 N = Nl+Nr+1 伪代码：
if(!t) return 0; l = Size(t->left) r = Size(t->right) return l+r+1;
思考：给定二叉树前中后序中的任意2个能否唯一确定该树？给出证明和设计算法确定树。
（转）下面是这个问题的证明与结论： ①给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。 证明：因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设1个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中’根-左子树-右子树’的顺序，则由从第二元素开始的1个结点序列和中序序列根左边的1个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。 ②由中序序列和先序序列能唯一确定一棵二叉树，但是由先序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。 反例：任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。 ③已经说明由二叉树的前序序列和中序序列可以确定一棵二叉树，现在来证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。 证明： 当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。 设当n=m-1时结论成立，现证明当n=m时结论成立。 设中序序列为S1,S2,…,Sm,后序序列是P1,P2,…,Pm。因后序序列最后一个元素Pm是根，则在中序序列中可找到与Pm相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，因中序序列是由中序遍历而得，所以Si是根结点，S1,S2,…,Si-1是左子树的中序序列，而Si+1,Si+2,…,Sm是右子树的中序序列。 若i=1，则 S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,则{S2,S3,…,Sm}和{P1,P2,…,Pm-1}可以唯一确定右子树，从而也确定了二叉树。 若i=m，则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1,S2,…,Sm-1}和{P1,P2,…,Pm-1}唯一确定左子树，从而也确定了二叉树。 最后，当1 < i < m时，Si把中序序列分成{S1,S2,…,Si-1}和{Si+1,Si+2,…,Sm}。由于后序遍历是’左子树-右子树-根结点’，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉树的左子树和右子树的后序遍历序列。因而由{S1,S2,…,Si-1}和{P1,P2,…,Pi-1}可唯一确定二叉树的左子树，由{Si+1,Si+2,…,Sm}和{Pi,Pi+1,…,Pm-1}可唯一确定二叉树的右子树。
题目如HDU1710（先序中序求后序） 思路参考http://www.cr173.com/html/18891_1.html
#include<cstdio> #define MAX (1000+7) #include<iostream> using namespace std; struct Node { int left; int right; }node[MAX]; int pre[MAX]; int in[MAX]; int n; int find(int l,int r) //子树在in中位置为l~r 返回根节点 { for(int i = 0; i < n; i++) { for(int j = l ; j <= r; j++) if(pre[i] == in[j]) return pre[i]; } return 0; } void split(int l,int r,int root) //在中序找根并确定左右 { int i; for(i = l; i <=r; i++) if(in[i] == root) break; node[root].left = find(l,i-1); node[root].right = find(i+1,r); if(node[root].left) split(l,i-1,node[root].left); if(node[root].right) split(i+1,r,node[root].right); } void post(int root,int r) { if(node[root].left) post(node[root].left,r); if(node[root].right) post(node[root].right,r); if(root == r) printf("%d",root); else printf("%d ",root); } int main() { freopen("xx.in","r",stdin); freopen("xx.out","w",stdout); while(scanf("%d",&n)!=EOF) { for(int i = 0; i < n; i++) scanf("%d",&pre[i]); //根左右 for(int i = 0; i < n; i++) scanf("%d",&in[i]); //左根右 int root = pre[0]; split(0,n-1,root); post(root,root); printf("\n"); } }//–作业题
6.3 sights
（到y的总额 = 到根节点前的花费 + 根节点到y的花费 = 到m的总额-根节点到m的花费 + 根节点到y的花费。邻接表存储然后从根节点开始BFS遍历下更新根节点到该节点的花费。然后按上面公式算下就好。）
#include<iostream> #include<cstdio> #include<queue> #define MOD 707063423 #define MAX 100000 using namespace std; int p[2*MAX+10]; int first[MAX+10]; int next[2*MAX+10]; int son[2*MAX+10]; int sum[MAX+10]; int vis[MAX+10]; int i; queue<int> que; void search() { que.push(1); vis[1] = true; while(!que.empty()) { int fa = que.front(); que.pop(); for(i = first[fa]; i > 0; i = next[i]) { if(!vis[son[i]]) { vis[son[i]] = true; sum[son[i]] = (sum[fa]+p[i]) % MOD; que.push(son[i]); } } } } int main() { //read int n,x,y; scanf("%d",&n); for(i = 1; i < n; i++) { scanf("%d%d%d",&x,&y,&p[i]); next[i] = first[x]; first[x] = i; son[i] = y; next[i+n] = first[y]; first[y] = i+n; p[i+n] = p[i]; son[i+n] = x; } //work search(); //print int q,m,mcost,v; scanf("%d",&q); for(i = 1; i <= q; i++) { scanf("%d%d%d",&m,&mcost,&v); int pre = mcost%MOD-sum[m]; if(pre<0) pre+=MOD; printf("%d\n",(pre+sum[v])%MOD); } return 0; }6.4 order
（给定父亲结点和中序遍历求先序和后序，那么只要把这棵树确定下来就可以了。对于中序遍历，必然有左根右的顺序，那么如果结点i的父节点fa在中序中的位置在i之后，那么i是fa的左儿子，反之为右儿子。然后递归输出先序后序就行了。）
#include<cstdio> #include<iostream> using namespace std; #define MAX 10000 #include<map> struct Node { int lef; //左儿子 int rig; //右儿子 }a[MAX+10]; int fa[MAX+10]; map<int,int> order; int i; void preOrder(int root) { if(root == -1) return; printf("%d ",root); preOrder(a[root].lef); preOrder(a[root].rig); } void aftOrder(int root) { if(root == -1) return; aftOrder(a[root].lef); aftOrder(a[root].rig); printf("%d ",root); } int main() { //read int n; scanf("%d",&n); int root; for(i = 1; i <= n; i++) { scanf("%d",&fa[i]); if(fa[i] == 0) root = i; } int num; for(i = 1; i <= n; i++) { scanf("%d",&num); order[num] = i; } //init for(i = 1; i <=n; i++) { a[i].lef = -1; a[i].rig = -1; } //work for(i = 1; i <=n; i++) { if(fa[i]) if(order[fa[i]] > order[i]) a[fa[i]].lef = i; else a[fa[i]].rig = i; } preOrder(root); printf("\n"); aftOrder(root); return 0; }besides：给定一棵二叉树前中后序中的任两个，能否得出第三个序列 answer：已知前序和中序、或中序和后序的情况下，可以求另一个；但知道前序和后序不能求中序，因为知道前序后序不能把树唯一确定下来。比如前序AB，后序BA，不能确定B是左儿子还是右儿子。
//–练习题
6.1 brothers
（只要知道了树中每层的节点数，fa相同的结点数-1 则为兄弟数，所在层的节点数-fa相同的节点数 则为堂兄弟数。用de[deep]数组来存deep层的结点数。根节点1的deep为0，de[0] = 1。层次遍历每次更新i结点的儿子结点的deep为i的deep+1，,de[deep+1]++，最后根据询问输出即可。）
#include<iostream> #include<cstdio> #include<queue> using namespace std; #define MAX 100000 int i; struct Node { int left; int right; int deep; }node[MAX+10]; int fa[MAX+10]; int de[MAX+10]; //每层结点数 int main() { int n; scanf("%d",&n); for(i = 1; i <= n; i++) { scanf("%d%d",&node[i].left,&node[i].right); fa[node[i].left] = i; fa[node[i].right] = i; } queue<int> que; que.push(1); de[0]++; node[1].deep = 0; while(!que.empty()) { int a = que.front(); que.pop(); if(node[a].left) { que.push(node[a].left); node[node[a].left].deep = node[a].deep + 1; de[node[a].deep + 1]++; } if(node[a].right) { que.push(node[a].right); node[node[a].right].deep = node[a].deep + 1; de[node[a].deep + 1]++; } } int q; scanf("%d",&q); for(i = 1; i <=q; i++) { int num; scanf("%d",&num); if(num == 1) { printf("0 0\n"); continue; } int sub = 0; if(node[fa[num]].left) sub++; if(node[fa[num]].right) sub++; printf("%d %d\n",sub-1,de[node[num].deep]-sub); } return 0; }6.2 expectation
（树上DP。用邻接表存下整棵树，nodesum为以结点 i 为父节点的整颗子树的结点权值和，distsum为以结点 i 为父节点的子树上的所有结点到i的所求权值和。对于询问i的时候，所求权值也即 i 的distsum再加上它这棵子树以外的结点到它的所求权值和，外面的部分也即以 i 的父节点为根的子树扣除掉 i 子树的那部分的权值和，该部分包括了fa的distsum - i 的distsum值（其余结点先走到fa），以及fa的nodesum - i 的nodesum乘上fa到 i 的边权（再从fa走到 i ）。然后不断沿着父节点的父节点一层层往上找一直到根节点。）
#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; #define N 200005 #define LL __int64 #define MOD 707063423 int n, i, j, u, v, c; int tot, V[N], head[N], vis[N], fa[N], fadis[N]; LL ans; struct Edge { int val, to, next; } e[N]; struct Node { int nodesum, distsum; } t[N]; void addedge(int u, int v, int c) { e[++tot].to = v; e[tot].val = c; e[tot].next = head[u]; head[u] = tot; } void dfs(int u) { vis[u] = 1; int i, v, c; for (i = head[u]; ~i; i = e[i].next) { v = e[i].to, c = e[i].val; if (vis[v]) continue; fa[v] = u; dfs(v); fadis[v] = c; t[u].nodesum += t[v].nodesum; t[u].distsum += c * t[v].nodesum + t[v].distsum; } } int main() { memset(vis, 0, sizeof(vis)); memset(head, -1, sizeof(head)); tot = 0; fa[1] = 0; scanf("%d", &n); for (i = 1; i <= n; ++i) { scanf("%d", &V[i]); t[i].nodesum = V[i]; } for (i = 1; i < n; ++i) { scanf("%d%d%d", &u, &v, &c); addedge(u, v, c); addedge(v, u, c); } dfs(1); int q, x, y, z; scanf("%d", &q); while (q--) { scanf("%d", &x); ans = t[x].distsum, z = 0; while (x != 1) { y = fa[x], z += fadis[x]; ans += t[y].distsum - t[x].distsum - t[x].nodesum * fadis[x] + (t[y].nodesum - t[x].nodesum) * z; x = fa[x]; } printf("%d\n", ans); } return 0; }