1.1 树和二叉树的定义
1.2树和二叉树的抽象数据类型定义
1.3二叉树的性质和存储结构
1.4遍历二叉树和线索二叉树
1.5树和森林
1.6哈夫曼树及应用

数据的逻辑结构
1、线性结构
（1）线性表
（2）栈（特殊线性表）
（3）队列（特殊线性表）
（4）字符串、数组、广义表
2、非线性结构
（1）树形结构
（2）图形结构
树型结构（结点之间有分支，具有层次关系）

1.11树的定义
树是n(n>=0)个结点的有限集。
若n=0,称为空树；
若n>0，则他满足如下两个条件：
（1）有且仅有一个特定的称为根的结点；
（2）其余结点可分为m（m>=0）个互不相交的有限集T1，T2，T3，，，，Tm,其中每一个集合本身又是一棵树，并称为根的子树。
根结点：非空树中无前驱结点的结点；
结点的度：结点拥有的子树数；
度！=0分支结点；
根结点以外的分支结点称为内部结点；
叶子：度=0，终端结点；
堂兄弟：双亲在同一层的结点；
兄弟：同一双亲的孩子之间互称兄弟；
祖先：从根到结点所经分支上的所有结点；
子孙：以某节点为根的子树中任意一结点都称为该节点的子孙。
双亲和孩子：结点的子树的根称为该节点的孩子，该节点称为孩子的双亲；
1.12树的基本术语
森林：是m(m>=0)棵互不相交的树的集合。
把根节点删除的树就变成了森林。
一棵树可以看成是一个特殊的森林。
给森林中的各子树加一个双亲结点，森林就变成了树。
树结构和线性结构的比较

1.13 二叉树的定义
二叉树是n(n>=0)个结点的有限集，它或者是空集（n=0）或者有一个根节点及俩棵互不相交的分别称作这个根的左子树或右子树的二叉树组成。
特点：
1、每个结点最多有两个孩子（二叉树中不存在度大于2的结点）。
2、子树有左右之分；
3、二叉树可以是空集合，根可以有空的左子树或右子树；
注：二叉树不是树的特殊情况，他们是两个概念；
具有3个结点的二叉树可能有5种不同的形态；树有2种形态；
二叉树的五种基本形态
（1）空二叉树 （2）根和空的左右子树 （3）根和左子树 （4）根和右子树 （5）根和左右子树
**

**
性质1：二叉树的第i层（深度为i>=1）上至多有2^i-1个结点（i>=1）.
性质2：对任意一颗二叉树T，如果其叶子树为n0，度为2的结点数为n2，则n0=n2+1.n1为度为1的结点数，
n=n0+n1+n2;
n=n1+2n2+1;
总边数 B=n-1=n1+2n2;
当结点数为奇数时n1==0;
两种特殊形式的二叉树
满二叉树：
一颗深度为k且有（2^k）-1个结点的二叉树称为满二叉树。
特点：1.每一层上的结点数都是最大节点数（即每层都满）
2.叶子结点全部在最底层
完全二叉树
深度为k的具有n 个结点的二叉树，当且仅当每一个结点都与深度为k 的满二叉树中编号为1-n 的结点一一对应是称为完全二叉树。
注：
在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一颗完全二叉树。
满二叉树--------->一定是完全二叉树；
完全二叉树————>不一定是满二叉树；
特点：1.叶子结点只可能分布在层次最大的两层上。
2.对任意一结点，如果其右子树的最大层次为i,则其左子树的最大层次比为i 或i+1
完全二叉树的性质
性质1：具有n个结点的完全二叉树的深度为|log2 n|+1.
性质2: 如果对一棵有n 个结点的完全二叉树（深度为|log2 n|+1）的结点按层序编号（从第一层到第|log2 n|+1层，每层从左到右），则对任意结点i（1<=i<=n）,有：
（1）如果I=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点|i/2|.(|_ _|为向下取整符省去小数点后的小数)
（2）如果2i>n，则结点i为叶子结点，无左孩子，否则其左孩子是结点2i；
（3）如果2i+1>n,则结点i无右孩子，否则，其右孩子是结点2i+1;
二叉树的存储结构

二叉树的存储结构分为顺序存储结构和链式存储结构。链式存储结构又分为二叉链表和三叉链表。
二叉树的顺序存储缺点：
最坏情况：深度为k 的且只有k个结点的单支树需要长度为(2^k)-1的一维数组。
特点：
节点空间关系蕴含在其存储位置中。
浪费空间，适于存满二叉树和完全二叉树。

二叉链表存储结构

typedef struct BiNode{
  TElemType data;
  struct BiNode *lchild,*rchild;
  }BiNode ,*BiTree;

存储方式：

在n 个结点的二叉链表中，有n+1个空指针域
三叉链表
存储方式
|lchild|data|parent|rchild|

typedef struct Tritnode{
  Telemtype  data;
  struct Ttitnode *lchild,*rchild,*parent;
  }Trinode,*Tritree;

遍历定义——顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次（又称周游）；
遍历目的——得到树中所有结点的一个线性排列。
遍历用途——他是树结构插入，删除，修改，查找和排序运算的前提，二叉树一切运算的基础和核心。
遍历二叉树算法描述
有三种情况：
（1）DLR——先（根）序遍历；
（2）LDR——中（根）序遍历；
（3）LRD——后（根）序遍历；
先序遍历
若二叉树为空，则空操作；否则
（1）访问根节点；
(2)先序遍历左子树；
（3）先序遍历右子树；
先序遍历算法

status preordertraverse(bitree T){
if(T==NULL)return ok;//空二叉树；
else{
  visit(T);//访问根节点
  preordertraverse(T->lchild);//递归遍历左子树
  preordertraverse(T->rchild);//递归遍历右子树；
}
}

void pre(bitree*t){
if(T!=NULL){
cout<<t->data<<endl;
pre(t->lchild);
pre(t->rchild);
}
}

中序遍历
若二叉树为空，则空操作；否则
（1）中序遍历左子树；
（2）访问根节点；
（3）中序遍历右子树；

status inordertraverse(bitree T){
if(T==NULL)return ok;//空二叉树；
else{
  inordertraverse(T->lchild);//递归遍历左子树
    visit(T);//访问根节点
  inordertraverse(T->rchild);//递归遍历右子树；
}
}

后序遍历
若二叉树为空，则空操作；否则
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根节点；

status postordertraverse(bitree T){
if(T==NULL)return ok;//空二叉树；
else{
  postordertraverse(T->lchild);//递归遍历左子树
  postordertraverse(T->rchild);//递归遍历右子树；
   visit(T);//访问根节点
}
}

以下是上图的各种遍历顺序：
先序遍历：ABELDHMIJ;
中序遍历：ELBAMHIDJ
后序遍历：LEBMIHJDA
遍历算法分析
时间效率：O（n）//每个节点只访问一次；
空间效率：O（n）//栈占用的最大辅助空间；
非递归算法
中序遍历非递归算法
关键：在中序遍历过某节点的整个左子树后，如何找到该节点的根以及右子树。
基本思想：
（1）建立一个栈；
（2）根节点进栈，遍历左子树；
（3）根节点出栈，输出根节点，遍历右子树。
算法

stauts inordertraverse (bitreee T){
bitree p;initstack(s);p=T;
while(p||!stackempty(s))
{
if(p)
{push(s,p);p=p->lchild;}
eles{ pop(s,p);cout<<q->data<<endl;
p=q->rchild;}
}
return ok;
}

线索二叉树
为什么研究线索二叉树？
当用二叉链表作为二叉树的存储结构时，可以方便的找到某个结点的左右孩子；但一般情况下无法直接找到该节点在某种遍历序列中的前驱和后继结点；
结点结构：
lchild | ltag |data |rtag | rchild

typedef struct bithrnode{
 int data;
 int ltag,rtag;
 struct bithrnode *lchild,rchild;
 }bithrnide,*bithrtree;

其他的和这个类似，暂时没找到合适的作图软件，画图比较费劲。

树是n(n>=0)个结点的有限集。
若n=0,称为空树；
若n>0，则他满足如下两个条件：
（1）有且仅有一个特定的称为根的结点；
（2）其余结点可分为m（m>=0）个互不相交的有限集T1，T2，T3，，，，Tm,其中每一个集合本身又是一棵树，并称为根的子树。
森林：是m(m>=0)棵互不相交的树的集合。
将树转换成二叉树
（1）加线：兄弟之间加一连线；
（2）抹线：对每个结点，除左孩子外，去除其余
（3）旋转：以树的根结点为轴心，将整树顺时针转45度。

二叉树转换成树
（1）加线：若P结点是双亲结点的左孩子，则将P的右孩子，右孩子的右孩子……沿分支找到所有右孩子，都与P的双亲结点用线连起来；
（2）抹线：抹掉原二叉树中双亲与右孩子之间的连线。
（3）调整：将结点按参差排列，形成树结构；
森林转化成二叉树
（1）将各棵树分别转化成二叉树；
（2）将每棵树的根节点用线相连；
（3）以第一棵树根节点为二叉树的根，再以根节点为轴心，顺时针旋转构成二叉树型结构；
二叉树转换成森林
（1）抹线：；将二叉树中根节点与其右孩子连线，沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树；
（2）还原：将孤立的二叉树还原成二叉树；
森的遍历
先序遍历：
若森林不空，则：
1、访问森林的第一棵树的根节点；
2、先序遍历森林中的第一课树的子树森林；
3、先序遍历森林中（除第一棵树）的子树森林；
中序遍历：
若森林不空，则：
（1）中序遍历森林中得第一棵树的子树；
（2）访问森林中第一棵树的根节点；
（3）中序遍历森林中（除第一棵树之外）其余树构成的森林；

哈夫曼树的基本概念
路径：从树中的一个结点到另一个结点之间的分支构成这两个结点间的路径；
结点路径长度：两结点间路径上的分支数；
树的路径长度：从树根到每一个结点的路径长度之和，记作：TL；
权：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权；
结点的带权路径长度：从根节点到该节点之间的路径长度与该节点的权的乘积。
哈夫曼树：最优树 带权路径长度（WPL）最短的树。
注：“带权路径长度最短”是在“度相等”的树比较而得的结果，因此有最优二叉树，最优三叉树之称等等。
满二叉树不一定是哈夫曼树；
哈夫曼树中权越大的叶子离根越近；
具有相同带权结点的哈夫曼树不唯一；
哈夫曼树中权越大的叶子离根越近；
贪心算法：构造哈夫曼树中权越大的叶子离根越近、
哈夫曼算法（构造哈夫曼树的方法）
（1）根据n 个给定的权值（w1,w2,w3,…wn）构成n 棵二叉树的森林F=（T1,T2…Tn),其中T，只有一个带权为wi的的根节点。
构造森林的全是根
（2）在F中选取两棵根节点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。
在哈夫曼算法中，初始有n棵二叉树，要经过n-1次合并最终成为哈夫曼树。哈夫曼树共有2n-1个结点。
结点类型定义：

typedef struct{
int weight;
int parent,lch.rch;
}HTNode，*HuffmanTree;

void creathuffmantre(huffman HT,int n)//构造哈夫曼树
{
if(n<=1)return ;
m=2*n-1;//数组共2n-1个元素
HT=new HTNode[m+1];//0号单元未用，HT[m]表示根节点
for(i=1;i<=m;i++)//将2n-1个元素的lch,rch.parent置为0；
{
HT[i].lch=0;HT[i].rch=0;;HT[i].parent=0;
}
for(i=1;i<=n;i++)
cin>>HT[i].weight;//输入前n 个元素的weight的值初始化结束，下面建立哈夫曼树
for(i=n+1;i<=m;i++){//合并产生n-1个结点--构造Huffman树；
select(HT,i-1,s1,s2);//在HT[k](1<=k<=i-1)中选择两个其双亲域为零；且权值最小的结点，并返回他们在HT中的序号s1和s2;
HT[s1].parent=i;HT[s2].parent=i;//表示从F中删除申s1.s2;
HT[i].ch=s1;HT[i].rch=s2;//s1,s2分别为i的左右孩子；
HT[i].weight=HT[s1].weight+HT[s2].weight;}//i的权值左右孩子权值之和
i

哈夫曼树构造算法的实现
1.初始化HT[1…2n-1];lch=rch=parent=0;
2.输入初始n个叶子结点；置HT[1…n]的weight值；
3、进行以下n-1次合并，依次产生n-1个结点HT[i],i=n+1…2n-1;
(a)在HT[1…i-1]中选两个未被选过（从parent==0的节点上选）的weight最小的两个结点HT[s1]和HT[s2],s1,s2为两个最小结点下标；
（b）修改HT[s1]和HT[s2]的parent 值：HT[s1].parent=i;HT[s2].parent=i;
©修改新产生的HT[l]:
HT[i].weight=HT[s1].weight+HT[s2].weight;
HT[i].lch=s1;HT[i].rch=s2;
哈夫曼编码：
方法：1.统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）。
2、利用哈弗曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点路径越短。
3.在哈夫曼树的每个分支上标0或1；
结点的左分支标0，右1；
把从根到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码。
eg:下图是关于哈夫曼编码的例子：

A:00
B:01
C:10
D:110
E:111
"111100100110"表示的是ECBAD
哈夫曼编码算法

void creathuffmantree HT,huffmancode &HC,int n){//从叶子节点到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
HC=new char*[n+1];//分配n个字符编码的头指针矢量；
cd=new char[n];//分配临时存放编码的动态数组空间；
cd[n-1]='\0';//编码结束符
for(int i=1;i<=n;i++){//逐个字符求哈夫曼编码
start=n-1;c=i;f=HT[i].parent;
while(f!=0){//从叶子节点开始向上回溯，直到根节点；
--start;//回溯一次start向前一个位置；
if(HT[f].lchild==c)cd[start]='0';//节点c是f 的左孩子，则生成代码0；
else cd[start]='1';//节点c是f的右孩子，则生成代码1；
c=f;f=HT[f].parent;//继续向上回溯
}//求出第i个字符的编码
HC[i]=new char[n-start];//为第i个字符的编码分配空间；
strcpy(HC[i],&cd[start];//将求得的编码从临时空间cd复制到HC的当前行中；
}
delete cd;//释放空间
}

以上是树和二叉树的相关知识点，希望对大家有所帮助；