第三讲-树（上）

什么是树

一种层次结构，显示中有许多这样的结构，例如：企业部门，图书管理，国家机构，文件系统等。
那为什么选择树呢————一个基本的原因是树形结构有着高效率的查找（搜索/检索）操作，并且树的插入和删除操作也比较快。

定义和一些性质：

• 一个有限集合

• 有一个特殊的根节点
• 其余节点是互不相交的集合，并且也是一个树，子树。
• 除根节点外，每个节点有且只有一个父节点。
• n个节点的树，有n-1条边。
• 树是保证节点联通的最小连接方式。

树的一些术语：

image
image

查找（searching）

定义：给定关键字，在集合中找出与关键字相同（相关）的记录。

• 静态查找：集合是固定的，只有查找操作。
  • 顺序查找。从头开始，一次遍历，复杂度O(n)。
  • 二分查找。前提是元素经过排序。复杂度O(ln(n))。
• 动态查找：集合是不固定的，会删除增加数据。

树的表示

• 数组和链表都可以实现。
• 一种比较便利的表示，每个节点两个指针域：（儿子兄弟表示法）
  • 指向第一个孩子节点。
  • 指向下一个兄弟节点。

由儿子兄弟表示法，可以将任意一种树转化为二叉树。

二叉树

存储结构

• 顺序存储：对于完全二叉树，顺序存储可以较为方便的存储。对于一般的二叉树，可以补充成完全二叉树，但会造成空间的浪费。
• 链表存储：表示方便，每个节点三个域。

二叉树几个重要的性质

• 第i层最大节点数是：2^(i-1)
• 深度为k层的二叉树，总结点数最大：2^k-1.
• 对非空的二叉树，度为2的节点数n2，度为0的节点（叶子节点）n0：n0 = n2+1.

重要操作：遍历

• 先序————根—>左->右
• 中序————左->根->右

void InorderTraversal(BinTree bt)
{
    BinTree t = bt;
    Stact s = stack();
    while(t || !s.isEmpty())
    {
        //一直访问左子树
        while(t)
        {
            s.push(t);
            //对于先序将访问操作放在此处即可
            t = t->left;
        }
        //出栈
        if(!s.isEmpty())
        {
            t = s.pop();
            //访问
            cout<<t;
            //指向右子树
            t = t->right;
        }
    }
    
}

• 后序————左->右->根

后序遍历和前序中序写法不太相同

• 层次————从上到下，从左到右
  1. 首先，根节点入队列。
  2. 取出队头的一个节点，访问，将其左右孩子加入队列。
  3. 继续2。直到队列中元素为空。

不管遍历顺序怎么样，走过的路径都是一样的，只不过是访问的时机不同，每个节点都会走过三次。

两种遍历且必须有中序遍历，则可以唯一确定二叉树。

---