树的定义

1.树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
（1）有且只有一个称为根的节点。
（2）有若干个互不相交的树，这些子树本也是一颗树 。树由节点和边构成（指针域） ，每个节点只有一个父节点但可以有多个子节点，但有一个节点例外，该节点没有根节点，此节点称为根节点

二叉树

专业术语

节点 父节点 子节点 子孙 堂兄弟
深度：从根节点到最底层节点的层数称之为深度,上图有4层。
叶子节点：没有子节点的节点，如上图中的#节点。
非终端节点：非叶子节点。
度：子节点的个数（树内所有节点度的最大值）。

树的分类

一般树 二叉树 森林
一般树：任意一个节点的子节点的个数都不受限制
二叉树：任意一个节点的子节点的个数最多两个，且子节点的位置不可更改（有序，从上到下，从左到右）。（上图为二叉树）
森林 ：n个互补相交的树的集合

二叉树的分类

一般二叉树：。。。。。
满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树。
完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干个节点，这样形成的二叉树就是完全二叉树。
完全二叉树包含满二叉树

树的存储(重点)

二叉树的存储：连续存储【完全二叉树】和链式存储

（1）连续存储【完全二叉树（用贴的方法）】：为什么要转换为完全而二叉树的原因：树为非线性二连续存储为线性，且如果只存取有效节点则无法还原以前二叉树的本来面目。无法确定关系.
优点：查找某个节点的父节点和子节点（也包括判断有咩有）速度很快
缺点：耗用内存空间过大
(2)链式存储（指针）

一般树的存储（非线性结构用线性结构来存储）

（1）双亲表示法(求父节点方便)
（2）孩子表示法（求子节点方便）
（3）双亲孩子表示法（求父节点和子节点）
（4）二叉树表示法 把一个普通书转化为二叉树来存储。
转换方法为：设法保证任意一个节点的左指针域指向它的第一个孩子，右指针域指向它的下一个兄弟。只要能满足此条件，就可以把一个普通树转化成二叉树。一个普通树转化成的二叉树一定没有右子树（是根节点 视频p65 22：33）

森林的存储

先把森林转化为二叉树，再存储二叉树，具体方式为：根节点之间可以当成是兄弟来看待

构造二叉树代码

typedef struct NODE//定义节点 
{
    int data;//数据域
    struct NODE * Left;//左指针 （左孩子） 
    struct NODE * Right; //右指针 （右孩子） 
}BTree,*PBTree;

void Creat_BTree(PBTree &T)//先输入根，再输入左子树，再输入右子树（左边优先
{
    int val;
    cin>>val;
    if(val==-1) T=NULL;//节点指向空 ,输入-1结束。 
    else
    {
        T=(PBTree)malloc(sizeof(BTree));
        T->data=val;
        Creat_BTree(T->Left);//递归
        Creat_BTree(T->Right);
    }   
}

输入值要有一些操作

若想得到图中的二叉树要这样输入：

1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1

**例1**

先序遍历

递归版
例1的结果为 1 2 4 5 3 6

过程

void preoder(PBTree &T)
{
    if(T!=NULL)
    {
        cout<<T->data<<" ";
        preoder(T->Left);
        preoder(T->Right);
    }
    return;
} 

非递归版
非递归的前序遍历需要用到栈的性质，也就是先进后出。在这里偷些懒，直接使用#include<stack>，直接使用栈的头文件。

偷些懒，直接使用#include<stack>，直接使用栈的头文件。
 void preoder(PBTree &T)//先序遍历。
{
    PBTree temp=T;//临时指针 
    stack<PBTree>s ;//创建一个新的栈来存储节点。
    while(temp||!s.empty())//当temp!=NULL或者栈s为空时 
    {
        while(temp)//控制左节点，只有当左节点为空时，才会想起他的右孩子。当节点不为空时，一定要向左孩子看一下。 
        {
            cout<<temp->data<<" ";
            s.push(temp);//将节点压入栈，方便回溯
            temp=temp->Left;//左节点 
        }
        // 当空节点时，跳出循环
        temp = s.top();
        s.pop();
        //  找到右孩子
        temp = temp->Right;
    }
     return ;
}

中序遍历

递归版
例1的结果为4 2 5 1 3 6

过程

void inoder(PBTree &T)
{
        if(T!=NULL)
    {
        inoder(T->Left);
        cout<<T->data<<" ";
        inoder(T->Right);
    }
    return;
}

非递归版

void inorder(PBTree &T)
{
    //  用于储存遍历的元素
    stack<node*> s;
    while( T ||  !s.empty() )
    {
        if ( T!= NULL )
        {
            s.push(T);
            T= T->Left;
        }
        else
        {
           T= s.top();
           s.pop();
           cout << T->data << " ";
            T = T->Right;
        }
    }
}

后序遍历

递归版
例1的结果为 4 5 2 6 3 1

过程

void postoder(PBTree &T)
{
        if(T!=NULL)
    {
        postoder(T->Left);
        postoder(T->Right);
        cout<<T->data<<" ";
    }
    return;
} 

层次遍历

递归版
例1的结果为