树和二叉树基础

发表于 | 分类于 | | 浏览 次
字数统计: 839 字 | 阅读时长 ≈ 4 分钟

树的逻辑结构

  1. 树的定义：树是 n （n >= 0）个节结点的有限集合。n = 0 时称之为 空树； 任意非空树满足以下条件：
    • 有且仅有一个特定的成为 根（root）的结点
    • n > 0 时，除根结点外的其余结点被分成 m (m > 0)互不相交的有限集合，每个集合又是一棵树，成为根结点的子树

  1. 属的基本术语：

    • 节点的度：结点子树的个数
    • 树的度：树种各结点度的最大值
    • 叶子结点（终端结点）：度为零的结点
    • 分支结点：叶子结点外的结点
    • 孩子结点、双亲结点、兄弟结点：
    • 路径、路径长度：由某祖先节点到其某一子孙结点的的线路，该线路唯一，路径中的边数和为路径长度
    • 祖先、子孙：自行体会
    • 树的深度：树中节点的最大层数。

  2. 树的遍历

    • 前序遍历：根左右
    • 后序遍历：左右根
    • 层序遍历：上层至下层的从左往右遍历

  3. 树的存储结构：略

二叉树的逻辑结构

template <class DataType>
struct BiNode 
{
    DataType data;
    BiNode<DataType> * lchild, *rchild;
}

  1. 前序遍历

    template<class DataType>
void BitTree<DataType>::PreOrder(BiNode<DataType> *bt)
{
    if(bt ==  null)
        return;                 // 递归调用的结束条件
    else 
    {
        cout << bt->data;       // 访问根节结点数据
        PreOrder(bt->lchild);   // 遍历bt 左子树
        PreOrder(bt->rchild);   // 遍历bt 右子树
    }
}

  2. 中序遍历

    template<class DataType>
void BitTree<DataType>::InOrder(BiNode<DataType> *bt)
{
    if(bt == NULL)
        return;                 // 递归调用的结束条件
    else 
    {
        PreOrder(bt->lchild);   // 遍历bt 左子树
        cout << bt->data;       // 访问根节结点数据
        PreOrder(bt->rchild);   // 遍历bt 右子树
    }
}

  1. 后序遍历：

    template<class DataType>
void BitTree<DataType>::PostOrder(BiNode<DataType> *bt)
{
    if(bt == NULL)
        return;                 // 递归调用的结束条件
    else 
    {

        PreOrder(bt->lchild);   // 遍历bt 左子树
        PreOrder(bt->rchild);   // 遍历bt 右子树
        cout << bt->data;       // 访问根节结点数据
    }
}

  2. 层序遍历： 

    template<class DataType>
void BitTree<DataType>::LevelOrder()
{
    front = rear = -1;
    if (root == NULL)
        return;
    Q[++rear] = root;
    while(front != rear)
    {
        q = Q[++ front];
        cout << q->date;
        if (q->lchild != null)
            Q[++rear] = q->lchild;
        if (q->rchild != null)
            Q[++rear] = q->rchild;
    }
}

  1. 二叉树前序遍历非递归算法

    template <class DataType>
void BiTree<DataType>::PreOrder(BiNode<DataType> * bt)
{
    top = -1;                           // 采用顺序栈
    while (bt =! NULL || top != -1)     // 两个条件都不成立才退出循环
    {
        while (bt != NULL)
        {
            cout << bt->data;
            s[++top] = bt;              // 根据指针 bt 入栈
            bt = bt->lchild;
        }

        if (top != -1)                  // 栈非空
        {
            bt = s[--top];
            bt = bt->rchild;
        }
    }
}

  1. 二叉树中序遍历非递归算法

    template <class DataType>
void BiTree<DataType>::InOrder(BiNode<DataType> * bt)
{
    top = -1;                           // 采用顺序栈
    while (bt =! NULL || top != -1)     // 两个条件都不成立才退出循环
    {
        while (bt != NULL)
        {
            s[++top] = bt;              // 根据指针 bt 入栈
            bt = bt->lchild;
        }

        if (top != -1)                  // 栈非空
        {
            bt = s[--top];
            cout << bt->data;
            bt = bt->rchild;
        }
    }
}

  1. 二叉树后序遍历非递归算法

    template <class DataType>
void BiTree<DataType>::InOrder(BiNode<DataType> * bt)
{
    top = -1;                           // 采用顺序栈
    while (bt =! NULL || top != -1)     // 两个条件都不成立才退出循环
    {
        while (bt != NULL)
        {
            s[++top] = bt;              // 根据指针 bt 入栈
            bt = bt->lchild;
        }

        if (top != -1)                  // 栈非空
        {
            bt = s[--top];
            bt = bt->rchild;
        }
    }
}

  1. 后序遍历非递归算法

    template <class DataType>
struct element 
{
    BiNode<DataType> * pre;
    int flag;
}

template <class DataType>
void BiTree<DataType>::PostOrder(BiNode<DataType> * bt)
{
    top = -1;
    while (bt != NULL || top != -1)
    {
        while ( top != NULL)
        {
            top++;
            // root 连同标志 flag 入栈
            s[top].pre = bt;
            s[top].flag = 1;
            bt = bt->lchild;
        }

        while (top != -1 && s[top].flag == 2)
        {
            bt = s[top--].pre;
            cout << bt->data;
        }

        if (top != -1)
        {
            s[top].flag = 2;
            bt = s[top].pre->rchild;
        }
    }
}
—— 结束 ——