2022.1.17

2022.1.17 树：不包含回路的连通无向图。或者说：任意两个结点间有且只有一条路径的无向图。

（在《大话数据结构》上对树有更详细的解释）

树：树（Tree）是n个结点的有限集。当n=0时称为空树。在任意一颗非空树中：1.有且加油一个特定的称为根（Root）的结点；2.当n>1时，其余结点可分为m个互不相交的有限集T1，T2，...。Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

由”树不包含回路“赋予的树的特性：

一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点，那么它一定恰好有n-1条边。在一棵树中加一条边将构成一个回路。

与树有关的概念：

 根结点（没有父结点）叶结点（没有子结点）子结点（儿子结点）父结点（父亲结点）内部结点（即不是根结点也不是叶结点的结点）深度Depth（从根到该结点的层数，其中根为第一层）度Degree（该结点的子树个数，注意与深度区分）

 

特别需要注意的就是：1.根结点是唯一的。2.子树之间互不相交。 

 

对树的储存结构表示有三种表示方法：

1.双亲表示法

2.孩子表示法

3.孩子兄弟表示法

通过灵活的融合又可以有双亲孩子表示法. 

(还没具体实践过，理解是好理解的，运用就感觉有点迷，还得靠日后做题来加深理解)

二叉树

二叉树（Binary Tree）是n个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两个互不相交的、分别称为根结点的左子树和右子树的二叉树组成。（递归定义）

二叉树的特点概况 

每个结点最多两颗子树。左子树和右子树是有顺序，次序不能任意颠倒。即使只有一棵子树也要区分左右。 

特殊二叉树的分类： 

斜树满二叉树完全二叉树 

二叉树的储存结构 

顺序存储结构（一般只储存完全二叉树）二叉链表  重点也是常用点：遍历二叉树

前序遍历（根左右）中序遍历（左根右）后序遍历（左右根）

已知前序遍历和中序遍历序列，可以唯一确定一棵二叉树。 

已知后序遍历和中序遍历序列，可以唯一确定一棵二叉树。 

但是已知前序和后序遍历，是不能确定一棵二叉树的。

三种方法的代码仅 *** 作顺序的不同

//二叉树的前序遍历递归算法
//初始条件：二叉树T存在
// *** 作结果：前序递归遍历
void PreOrderTraverse(BiTree T)
{
    if(T == NULL)
        return;
    printf("%c",T->data);       //显示结点数据，可以更改为其他对结点的 *** 作
    PreOrderTraverse(T->lchild);//先序遍历左子树
    PreOrderTraverse(T->rchild);//先序遍历右子树
}

//二叉树的中序遍历递归算法
//初始条件：二叉树T存在
// *** 作结果：中序递归遍历
void InOrderTraverse(BiTree T)
{
    if(T == NULL)
        return;
    InOrderTraverse(T->lchild);//中序遍历左子树
    printf("%c",T->data);       //显示结点数据，可以更改为其他对结点的 *** 作
    InOrderTraverse(T->rchild);//中序遍历右子树
}

//二叉树的后序遍历递归算法
//初始条件：二叉树T存在
// *** 作结果：后序递归遍历
void PostOrderTraverse(BiTree T)
{
    if(T == NULL)
        return;
    PostOrderTraverse(T->lchild);//后序遍历左子树
    PostOrderTraverse(T->rchild);//后序遍历右子树
    printf("%c",T->data);       //显示结点数据，可以更改为其他对结点的 *** 作
}

想遍历二叉树，那得先有二叉树，所以我们要学会如何建立二叉树 

(利用递归的原理） 

//按前序输入二叉树中结点的值
//#表示空树，构造二叉链表表示二叉树T
void CreateBiTree(BiTree * T)
{
    TElemType ch;
    
    scanf("%c",&ch);
    ch=str[index++];
    
    if(ch == '#')
        *T=NULL;
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));
        if(!*T)
            exit(OVERFLOW);
        (*T)->data=ch;              //生成根结点
        CreateBiTree(&(*T)->lchild);//构造左子树
        CreateBiTree(&(*T)->rchild);//构造右子树
    }
}

(有一说一，这样子的代码我有点看不懂，好难看啊呜呜，还得靠做题了，可能做着做着就理解了吧，这个是在原本打印结点的地方，改成了生产结点，给结点赋值的 *** 作。) 

（后面的内容(线索二叉树，树，森林与二叉树的转换，哈夫曼树及其应用，哈夫曼编码)也看了，但是看不太明白......）

堆——神奇的优先队列

 （今天也看书学习了堆排序和并查集，随读笔记都写在书上，不想打字了emmm）

今天主要就是在看书，通过《啊哈算法》，《大话数据结构》，还有若干个bilibili上的视频学习了树，二叉树，堆，并查集。

继续在b站上看视频学习c++，马上就学到容器了。

计划明天开始做题目吧，希望能顺顺利利！！不要搞我心态就行emmmmmmm！！