目录
第7章 数和二叉树
第9章 查找
7.1 树的基本概念
树(tree)是由n个结(或元素）组成的有限集合（记为T）。树属于非线性结构。若n=0,则为一棵空树；若n>0,这n个结点中有且仅有一个结点作为树的根结点，简称为根(root）。
树结构常用于表示具有层次关系的数据。树的抽象数据类型基本运算描述如下：
InitTree(&t):初始化树，造一棵空树t. DestroyTree(&t):销毁树，释放树t占用的存储空间. TreeHeight(t):求树t中的高度. Parent(t,p):求树t中p所指结点的双亲结点. Borther(t,p):求树t中p所指结点的所有兄弟结点. Sons(t,p):求树t中p所指结点的所有子孙结点. ...
树的逻辑表示方法：
1.树形表示法；2.文氏图表示法；3.凹入表示法；4.括号表示法。
树的性质：
1.树中的结点数等于所以结点的度数之和加1；
2.度为m的树中第i层上最多有m^(i-1)个结点（i>=1);
3.高度为h的m次树最多有m^h-1/m-1个结点；
4.具有n个结点的m次树的最小高度为[logm（n(m-1)+1)].
树的基本运算及其过程：
1.先根遍历:(1)访问根结点；(2)按照从左到右的顺序先根遍历根结点的每一棵子树；
2.后根遍历:(1).按照从左到右的顺序后根遍历根结点的每一棵子树；(2)访问根结点；
3.层次遍历：从根结点开始按从上到下、从左到右的次序访问树中的每一个结点。
树的存储结构:
1.双亲存储结构；类型声明如下：
typedef struct { ElemType data; //存放结点的值 int parent; //存放双亲的位置 } PTree[MaxSize]; //PTree为双亲存储结构类型
2.孩子链存储结构；类型声明如下：
typedef struct node { ElemType data; //结点的值 struct node *sons[MaxSons]; //指向孩子结点 } TSonNode; //孩子链存储结构中的结点类型
3.孩子兄弟链存储结构，类型声明如下：
typedef struct tnode { ElemType data; //结点的值 struct tnode * hp; //指向兄弟 struct tnode * vp; //指向孩子结点 } TSBNode; //孩子兄弟链存储结构中的结点类型
7.2. 二叉树的概念和性质
二叉树的定义：二叉树是一个有限的结点集合，这个集合或者为空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树的定义是一个递归定义。
二叉树的性质：
1.非空二叉树上的叶子结点数等于双分支结点数加1；
2.非空二叉树的第i层上最多有2^(i-1)个结点；
3.高度为h的二叉树最多有2^h-1个结点；
二叉树与树、森林之间的转换：
将一颗树转换成二叉树的过程如下：
1.树中所有相邻兄弟之间加一条连线；
2.对树中的每个结点只保留它与长子之间的连线，删除与其他孩子之间的连线；
3.以树的根结点为轴心，将整棵树顺时针转动45°，使之结构层次分明。
原文：https://www.cnblogs.com/yuan-017/p/14723368.html