一：树

树是n个节点的有限集合，当n=0时，为空树；当n>0时，为非空树。任意一颗非空树都满足：（1）有且仅有一个被称作根的节点。（2）除根节点外的其余节点可分为m个互不相交的有限集T1,T2…Tm。其中每个集合本身又是一棵树，被称为根的子树（subtree）

名词解释

节点：节点包含数据元素及若干指向子树的分支信息
节点的度：节点拥有的子树个数
树的度：树中节点的最大度数
终端节点：度为0的节点，又被称为叶子
分支节点：度大于0的节点，也就是除了叶子都是分支节点
内部节点：除了树根和叶子，都是内部节点
节点的层次：从树到节点的层数（根节点是第一层）
树的深度（高度）：所有节点中最大的层数
路径：树中两个节点之间所经过的节点序列
路径长度：两个节点之间路径上经过的边数
当把树看做族谱时，又有如下名词
双亲，孩子：节点的子树的根被称为该节点的孩子，反之，该节点为其孩子的双亲
兄弟：双亲相同的节点互称兄弟
堂兄弟：双亲是兄弟的节点互称堂兄弟。
祖先：即从该节点到树根经过的所有节点，称为该节点的祖先
子孙：节点的子树中的所有节点被称为该节点的子孙
有序树：节点的各子树从左到右有序，不能互换位置
无序树：节点的各子树可以互换位置
森林：由m棵不相交的树构成的集合。
1.树的存储
树形结构是一对多的关系，除了树根，每个节点都有唯一的直接前驱，除了叶子，每个节点都有一个或多个直接后继。与其他数据结构一样，仍可以采用顺序存储和连输存储
以下图为例，分别讲述三种存储方法：双亲表示法，孩子表示法，双亲孩子表示法。

链式存储：
两种存储方法：（1）邻接表思路：将所有孩子存储在一个单链表中，也就是孩子链表表示法。（2）二叉链表思路：左指针存储第一个孩子，右指针存储右兄弟，称之为孩子兄弟表示法。（一个技巧：把长子当做左孩子，将兄弟关系向右斜）

2.树，森林和二叉树的转换

见视频讲解。

二：二叉树

1.性质

1.在二叉树的i层上至多有2^（i-1）个节点
2.深度为k的二叉树至多有2^k-1个节点。
3.对于任何一个二叉树，若叶子数为n0，度为2的节点数为n2，则n0=n2+1.
4.具有n个节点的完全二叉树深度必为log（2）n+1
5.对于完全二叉树，若从上至下，从左向右编号，则编号为i的节点，其左孩子编号必为2i，右孩子即2i+1；双亲编号即i/2。

2.存储结构

typedef struct Bnode{
ElemType data;
    struct Bnode *lchild,*rchild,*parent;
}Bnode,*Btree;

3.创建

1.询问法；

#include <iostream>
using namespace std;
typedef struct Bnode    /*定义二叉树存储结构*/
{ char data;
  struct Bnode *lchild,*rchild;
}Bnode,*Btree;
void Createtree(Btree &T)    /*创建二叉树函数*/
{
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
    char ch;
    cin >> ch;
    if(ch=='#')
        T=NULL;            //递归结束，建空树
    else{
        T=new Bnode;
        T->data=ch;                    //生成根结点
        Createtree(T->lchild);    //递归创建左子树
        Createtree(T->rchild);    //递归创建右子树
    }
}
int Depth(Btree T)//求二叉树的深度
{
    int m,n;
    if(T==NULL)//如果为空树，深度为0
        return 0;
    else
    {
       m=Depth(T->lchild);//递归计算左子树深度
       n=Depth(T->rchild);//递归计算左子树深度
       if(m>n)
          return m+1;//返回左右子树最大值加1
       else
          return n+1;
    }
}
int main()
{
    Btree mytree;
    cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl;
    //ABD##E##CF#G###
    Createtree(mytree);//创建二叉树
    cout<<endl;
    cout<<"二叉树的深度为："<<Depth(mytree)<<endl;
    return 0;
}

2.补空法；

#include <iostream>
using namespace std;
typedef struct Bnode    /*定义二叉树存储结构*/
{ char data;
  struct Bnode *lchild,*rchild;
}Bnode,*Btree;
void Createtree(Btree &T)    /*创建二叉树函数*/
{
    //按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
    char ch;
    cin >> ch;
    if(ch=='#')
        T=NULL;            //递归结束，建空树
    else{
        T=new Bnode;
        T->data=ch;                    //生成根结点
        Createtree(T->lchild);    //递归创建左子树
        Createtree(T->rchild);    //递归创建右子树
    }
}
int LeafCount(Btree T)//求二叉树的叶子数
{
    if(T==NULL)//如果为空树，深度为0
        return 0;
    else
        if(T->lchild==NULL&&T->rchild==NULL)//左右子树均为空，则叶子数为1
           return 1;
        else
           return LeafCount(T->lchild)+LeafCount(T->rchild);//递归计算左子树和右子树的叶子数之和
}
int NodeCount(Btree T)//求二叉树的结点数
{
    if(T==NULL)//如果为空树，深度为0
        return 0;
    else
        return NodeCount(T->lchild)+NodeCount(T->rchild)+1;//递归计算左子树和右子树的结点数之和加1
}
int main()
{
    Btree mytree;
    cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<<endl;
    //ABD##E##CF#G###
    Createtree(mytree);//创建二叉树
    cout<<endl;
    cout<<"二叉树的结点数为："<<NodeCount(mytree)<<endl;
    cout<<"二叉树的叶子数为："<<LeafCount(mytree)<<endl;
    return 0;
}

三：二叉树遍历

1.先序遍历

void Preorder(Btree T){
    if(T)
    {
    cout<<T->data<<" ";
    Preorder(T->lchild);
    Preorder(T->rchild);
    }
}

2.中序遍历

3.后序遍历

4.层次遍历

5.遍历序列还原树

#include <iostream>
#include<cstdlib>
using namespace std;
typedef struct node
{
    char data;
    struct node *lchild,*rchild;
}BiTNode,*BiTree;

BiTree pre_mid_createBiTree(char *pre,char *mid,int len) //前序中序还原建立二叉树
{
    if(len==0)
        return NULL;
    char ch=pre[0];  //找到先序中的第一个结点
    int index=0;
    while(mid[index]!=ch)//在中序中找到的根结点的左边为该结点的左子树，右边为右子树
    {
        index++;
    }
    BiTree T=new BiTNode;//创建根结点
    T->data=ch;
    T->lchild=pre_mid_createBiTree(pre+1,mid,index);//建立左子树
    T->rchild=pre_mid_createBiTree(pre+index+1,mid+index+1,len-index-1);//建立右子树
    return T;
}

BiTree pro_mid_createBiTree(char *last,char *mid,int len)//后序中序还原建立二叉树
{
    if(len==0)
       return NULL;
    char ch=last[len-1]; //取得后序遍历顺序中最后一个结点
    int index=0;//在中序序列中找根结点，并用index记录长度
    while(mid[index]!=ch)//在中序中找到根结点，左边为该结点的左子树，右边为右子树
       index++;
    BiTree T=new BiTNode;//创建根结点
    T->data=ch;
    T->lchild=pro_mid_createBiTree(last,mid,index);//建立左子树
    T->rchild=pro_mid_createBiTree(last+index,mid+index+1,len-index-1);//建立右子树
    return T;
}

void pre_order(BiTree T)//前序递归遍历二叉树
{
    if(T)
    {
        cout<<T->data;
        pre_order(T->lchild);
        pre_order(T->rchild);
    }
}

void pro_order(BiTree T)//后序递归遍历二叉树
{
    if(T)
    {
        pro_order(T->lchild);
        pro_order(T->rchild);
        cout<<T->data;
    }
}
int main()
{
    BiTree T;
    int n;
    char pre[100],mid[100],last[100];
    cout<<"1. 前序中序还原二叉树\n";
    cout<<"2. 后序中序还原二叉树\n";
    cout<<"0. 退出\n";
    int choose=-1;
    while(choose!=0)
    {
        cout<<"请选择:";
        cin>>choose;

        switch (choose)
        {
            case 1://前序中序还原二叉树
                cout<<"请输入结点的个数:"<<endl;
                cin>>n;
                cout<<"请输入前序序列:"<<endl;
                for(int i=0;i<n;i++)
                    cin>>pre[i];
                cout<<"请输入中序序列:"<<endl;
                for(int i=0;i<n;i++)
                    cin>>mid[i];
                T=pre_mid_createBiTree(pre,mid,n);
                cout<<endl;
                cout<<"二叉树还原成功，输出其后序序列:"<<endl;
                pro_order(T);
                cout<<endl<<endl;
                break;
            case 2://后序中序还原二叉树
                cout<<"请输入结点的个数:"<<endl;
                cin>>n;
                cout<<"请输入后序序列:"<<endl;
                for(int i=0 ;i<n;i++)
                    cin>>last[i];
                cout<<"请输入中序序列:"<<endl;
                for(int i=0 ;i<n;i++)
                    cin>>mid[i];
                T=pro_mid_createBiTree(last,mid,n);
                cout<<endl;
                cout<<"二叉树还原成功，输出其先序序列:"<<endl;
                pre_order(T);
                cout<<endl<<endl;
                break;
        }
    }
    system("pause");
    return 0;
}

四：哈夫曼树

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXBIT    100
#define MAXVALUE  10000
#define MAXLEAF   30
#define MAXNODE   MAXLEAF*2 -1

typedef struct
{
    double weight;
    int parent;
    int lchild;
    int rchild;
    char value;
} HNodeType;        /* 结点结构体 */

typedef struct
{
    int bit[MAXBIT];
    int start;
} HCodeType;        /* 编码结构体 */
HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */
HCodeType HuffCode[MAXLEAF];/* 定义一个编码结构体数组*/
/* 构造哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n){
    /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
       x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
    int i, j, x1, x2;
    double m1,m2;
    /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
    for (i=0; i<2*n-1;i++)
    {
        HuffNode[i].weight=0;//权值
        HuffNode[i].parent=-1;
        HuffNode[i].lchild=-1;
        HuffNode[i].rchild=-1;
    }
    /* 输入 n 个叶子结点的权值 */
    for (i=0; i<n; i++)
    {
        cout<<"Please input value and weight of leaf node "<<i+1<<endl;
        cin>>HuffNode[i].value>>HuffNode[i].weight;
    }
    /* 构造 Huffman 树 */
    for (i=0; i<n-1; i++)
    {//执行n-1次合并
         m1=m2=MAXVALUE;
         /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
        x1=x2=0;
        /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一棵二叉树 */
        for (j=0;j<n+i;j++)
        {
            if (HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
            {
                m2 = m1;
                x2 = x1;
                m1 = HuffNode[j].weight;
                x1 = j;
            }
            else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
            {
                m2=HuffNode[j].weight;
                x2=j;
            }
        }
        /* 设置找到的两个子结点 x1、x2 的父结点信息 */
        HuffNode[x1].parent  = n+i;
        HuffNode[x2].parent  = n+i;
        HuffNode[n+i].weight = m1+m2;
        HuffNode[n+i].lchild = x1;
        HuffNode[n+i].rchild = x2;
        cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<HuffNode[x1].weight<<"\t"<<HuffNode[x2].weight<<endl; /* 用于测试 */
    }
}
/* 哈夫曼树编码 */
void HuffmanCode(HCodeType HuffCode[MAXLEAF],  int n){
    HCodeType cd;       /* 定义一个临时变量来存放求解编码时的信息 */
    int i,j,c,p;
    for(i=0;i<n;i++)
    {
        cd.start=n-1;
        c=i;
        p=HuffNode[c].parent;
        while(p!=-1)
        {
            if(HuffNode[p].lchild==c)
                cd.bit[cd.start]=0;
            else
                cd.bit[cd.start]=1;
            cd.start--;        /*前移一位 */
            c=p;
            p=HuffNode[c].parent;    /* 设置下一循环条件 */
        }
        /* 把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组 */
        for (j=cd.start+1; j<n; j++)
           HuffCode[i].bit[j]=cd.bit[j];
        HuffCode[i].start=cd.start;
    }
}
int main()
{
    int i,j,n;
    cout<<"Please input n:"<<endl;
    cin>>n;
    HuffmanTree(HuffNode,n);  //构造哈夫曼树
    HuffmanCode(HuffCode,n);  // 哈夫曼树编码
    //输出已保存好的所有存在编码的哈夫曼编码
    for(i=0;i<n;i++)
    {
        cout<<HuffNode[i].value<<": Huffman code is: ";
        for(j=HuffCode[i].start+1;j<n;j++)
            cout<<HuffCode[i].bit[j];
        cout<<endl;
    }
    return 0;
}

算法入门

树的应用

一：树