在此文，我们将总结下数据结构中树结构的主要知识点。1、树的定义
树（Tree）时n（n>=0）个结点的有限集，当n==0时称为空树，对于非空树：
（1）、有且仅有一个根结点；
（2）、除去根结点，其余结点可分为m（m>0）个互不相交的有限集，其中每个集合本身也是一棵树，称为根结点的子树（SubTree）。（个人认为有一个特例：只有一个根结点的树，它并没有子树，不具备非空树的第二个定义，但课本里并没有特别写出这点）
结点分类
按照所处层次的不同，分为根结点、分支结点、叶结点
结点间的关系
按照所在的相对位置，有“子结点”、“父结点”、“兄弟结点”。
上图树结构中，A是他们仨的父结点或双亲结点，反过来说，B、C、D三个结点便是A结点的子结点，BCD处于同一层，互称为兄弟结点。
结点的度
结点的度是指该结点的子结点个数。上图中根结点A的度为3，B结点的度为2，所有叶结点的度为0。
树的度
树的度是指树的各个结点的度的最大值。图中树的度为3。
树的深度
从根结点开始为第一层，最大的层次数称为数的深度
上图中树的深度为4。
有序树和无序树 普通树中的结点的左右子树是可以互换的，称为 无序树，而若将树中结点的各子树看成从左往右是有次序的，不能互换，则称该树为 有序树，如二叉树便是一种有序树。有序树中最左边的子树的根称为第一个孩子，最右边的子树的根称为最后一个孩子。
树和森林
森林是m（m>=0）棵互不相交的树的集合。
ADT Tree{InitTree(&T);//构造空树DestroyTree(&T);//销毁树TCreateTree(&T, definition);//根据definition中给出的树的定义来构造树ClearTree(&T);//若树存在，则将树T清空为空树TreeEmpty(T);//若树为空树，返回treu，否则返回falseRoot(T);//返回T的根结点Value(T, cur_e);//cur_e是树T中的一个结点，返回此值Assign(T, cur_e, value);//给树T的根结点cur_e赋值为valueParent(T, cur_e);//若cur_e是树T的非根结点，则返回它的父结点LeftChild(T, cur_e);//若cur_e是树的非叶结点，则返回它的最左孩子RightSibling(T, cur_e);//若cur_e有右兄弟，则返回它的右兄弟否则返回空InsettChild(&T，p, i, c);//其中p指向树T的某个结点，i为所指结点p的度数加1，非空树c与T不相交，操作结果为插入c为树T中p指向结点的第i棵子树DeleteChild(&T, p, i);//其中p指向树T的某个结点，i为所指结点p的度，操作结果为删除T中p所指向结点的第i棵子树TraverseTree(T);//按某种次序对T的每个结点访问一次}
2、二叉树
二叉树与树的主要区别：
（1）、二叉树每个结点至多只有两棵子树，即不存在度大于2的结点；
（2）、二叉树的子树有左右之分，其次序不能任意颠倒。
二叉树的性质
1）、二叉树的第i层上至多有2^(i-1)个结点；
2）、深度为k的二叉树至多有2^k-1个结点；
下面介绍两种比较特殊的二叉树：满二叉树和完全二叉树
满二叉树：深度为k且含有（2^k）-1个结点的二叉树。下图为一棵深度为4的二叉树。
特点：每一层上的结点数都为最大结点数；可对满二叉树进行编号，自上而下，自左至右。
满二叉树
完全二叉树：（课本官方定义）深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称该树为完全二叉树。个人比较庸俗不过比较容易理解的想法：深度为k的二叉树，除了第k层的结点依次从左往右排列，前面k-1层结点组成满二叉树，则称该二叉树为完全二叉树。如下图为深度为4的完全二叉树。
特点：1）、叶结点只可能在层次最大的两层上出现；
2）、具有n个结点的完全二叉树的深度为：log2n（向下取整）+1
完全二叉树
在二叉树的一些应用中，常会用到特殊的二叉树——哈夫曼树（即最优二叉树）、线索二叉树、平衡二叉树等等，在之后会有篇专讲这些二叉树的，今天的课到这先告一段落啦。
最后再附上二叉树的基本操作
ADT BinaryTree{InitBiTree(&T); //构造空二叉树TDestroyBiTree(&T);//销毁二叉树TCreatBiTree(&T,definition);//按definition构造二叉树TClearBiTree(&T);//将二叉树清为空树BiTreeEmpty(T);//判断T是否为空二叉树，若是则返回true，不是返回falseBiTreeDepth(T);//返回T的深度Root(T);//返回T的根Value(T,e);//返回e的值Assign(T,&e,value);//结点e赋值Parent(T,e);//若e是T的非根结点，则返回它的双亲，否则返回“空”LeftChild(T,e);//返回e的左孩子，若e无左孩子，则返回“空”RightChild(T,e);//返回e的右孩子，若e无右孩子，则返回“空”LeftSibling(T,e);//返回e的左兄弟，若e无左兄弟，则返回“空”RightSibling(T,e);//返回e的右兄弟，若e无右兄弟，则返回“空”InsertChild(&T,p,LR,c);//插入子树，根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树DeleteChild(&T,p,LR);//删除子树，根据LR为0或1，删除T中p所指结点的左或右子树PreOrderTraverse(T);//先序遍历T，对每个结点访问一次InOrderTraverse(T);//中序遍历T，对每个结点访问一次PostOrderTraverse(T);//后序遍历T，对每个结点访问一次LevelOrderTraverse(T);//层序遍历T，对每个结点访问一次}