一颗曾经砸中牛顿的苹果树
树的定义「树（Tree）」是n(n=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中，有且仅有一个特定的称为根的结点。当n1时，其余结点可分为m(m0)个互不相交的有限集T1、T2、……、Tm。其中每一个集合本身又是一棵树，并且称为根的「子树（SubTree）」，如下图所示：
树的示意图树的属性结点和度树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的的子树数称为结点的度。度为0的称为叶结点或者终端结点；度不为0的结点称为非终端结点或者分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
结点间关系结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点.
结点的层次结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层，其双亲在同一层的结点互为堂兄弟。
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
「双亲（parentnode）」：对于除根以外的每个结点，定义为从该结点到根路径上的第二个结点。根结点没有双亲结点。
「祖先（ancestor）」：一个结点到根结点的路径上，除了它本身外的结点。根结点的祖先集合为空。
「子结点（childnode）」：如果
是
的父亲，那么
是
的子结点。子结点的顺序一般不加以区分，二叉树是一个例外。
「兄弟（sibling）」：同一个父亲的多个子结点互为兄弟。
「后代（descendant）」：子结点和子结点的后代。或者理解成：如果
是
的祖先，那么
是
的后代。
「子树（subtree）」：删掉与父亲相连的边后，该结点所在的子图。
高度深度层结点n的高度:n结点到叶子结点所有路径上包含结点个数的最大值。叶子结点的高度为1，往上结点的高度依次递增。
结点n的深度:从根结点到结点n唯一的路径的长，根结点深度为1
层数：根结点为第一层，往下依次递增。
树中结点的最大层数称之为树的深度或者高度，所以在基数为1时树的深度=树的高度=最大层数
但是结点的深度和高度并没有必然的关系
结点的度：结点拥有的子树的个数，度为0的结点称之为叶子结点
树的度：是树内所有结点度的最大值
树的深度：树内所有结点深度的最大值，也就是所有叶子结点深度的最大值，也就是树的层数
树的高度：树内所有结点高度的最大值，也就是根结点的高度，也就是数的层数
特殊的树「链（chain/pathgraph）」：满足与任一结点相连的边不超过
条的树称为链。
「菊花/星星（star）」：满足存在
使得所有除
以外结点均与
相连的树称为菊花。
「有根二叉树（rootedbinarytree）」：每个结点最多只有两个儿子（子结点）的有根树称为二叉树。常常对两个子结点的顺序加以区分，分别称之为左子结点和右子结点。
大多数情况下，「二叉树」一词均指有根二叉树。
树的存储结构双亲表示法我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在链表中的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里.
/*树的双亲表示法的结点结构定义*/constintMAX_TREE_SIZEstructNode//结点结构{intdata;//数据域intparent;//父结点位置};Nodetree[MAX_TREE_SIZE];//把结点存在数组中
这样的存储结构，我们可以根据结点的parent指针很容易找到它的双亲结点，所用的时间复杂度为〇(1)，直到parent为-1时，表示找到了树结点的根。
「总结」
「优点：」该存储方式根据结点的parent指针很容易找到它的双亲结点，时间复杂度为O(1)。
「缺点：」如果需要知道某个结点的所有孩子，需要遍历整棵树。
孩子表示法/*树的孩子表示法结构定义*/constintm=3;structNode{intdata;Node*chile[m];}Node*tree;
「总结」
「缺点：」如果需要知道某个结点的双亲，需要遍历整棵树
「改进：」孩子兄弟表示法
双亲孩子表示法constintm=10;structNode{intdata;//数据域intparent;//父亲结点Node*child[m];//指针域,指向孩子结点}孩子兄弟表示法
strcutNode{intdata;intfirstchild;intnext;}Node*tree;
「总结」
「优点：」可以把一棵复杂的树变成一棵二叉树，这样就可以充分利用二叉树的特性和算法来处理这棵树了。
例题找树根和孩子问题描述给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子
输入格式第一行：n（结点数=），m（边数=）。
以下m行；每行两个结点x和y，
表示y是x的孩子(x,y=0)。
输出格式第一行：树根：root。
第二行：孩子最多的结点max。
第三行：max的孩子。
输入样例输出样例
参考程序
#includeiostreamusingnamespacestd;constintN=;intn,m,x,y,tree[N],root,maxn,maxroot;intmain(){cinnm;for(inti=1;i=m;i++){cinxy;tree[y]=x;}for(inti=1;i=n;i++){if(tree==0){root=i;break;}}for(inti=1;i=n;i++){intsum=0;for(intj=1;j=n;j++){if(tree[j]==i)sum++;}if(summaxn){maxn=sum;maxroot=i;}}coutrootendl;coutmaxrootendl;for(inti=1;i=n;i++){if(tree==maxroot)couti"";}return0;}单词查找树题目描述
在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：
1．根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母；
2．从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；
3．在满足上述条件下，该单词查找树的结点数最少。
4．例如下图左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。
输入为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母。文件总长度不超过32K，至少有一行数据。
输出仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。
输入样例AANASPASASCASCIIBASBASIC输出样例
13
参考代码#includebits/stdc++.husingnamespacestd;intn,t,k;stringa[];strings;intmain(){while(cina[++n]);n--;sort(a+1,a+1+n);t=a[1].size();for(inti=2;i=n;i++){intj=0;while(a[j]==a[i-1][j]ja[i-1].size())j++;t+=a.size()-j;}coutt+1endl;}二叉树定义
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点).
二叉树的子树有左子树、右子树。其次序不能颠倒。所以二叉树是一棵严格的有序树。
5种形态例题按照二叉树的定义，4个节点的二叉树有多少种？（）
A13B14C15D16分析
设n个结点的二叉树有f(n)种，对于f(4),分类讨论:
左子树有0个结点，右子树有3个结点,种数为f(0)*f(3)左子树有1个结点，右子树有2个结点,种数为f(1)*f(2)左子树有2个结点，右子树有1个结点,种数为f(1)*f(2)左子树有3个结点，右子树有0个结点,种数为f(1)*f(2)f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0)f(0)=1,f(1)=1,f(2)=2,f(3)=(1,1,2)*(2,1,1)=5f(4)=(1,1,2,5)*(5,2,1,1)=14
二叉树节点算法
或者
二叉树的分类满二叉树完美二叉树(perfectbinarytree)
除最后一层无任何子结点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。结点数达到最大值，所有叶子结点必须在同一层上。
满二叉树的性质(设根结点的深度是1):
一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;叶子数为;第k层的结点数是：
总结点数是：
，且总结点数一定是奇数完全二叉树(