二叉树

二叉树数的节点结构:

struct BiNode 
{
    char data;
    BiNode *lchild, *rchild;
};

先序创建二叉树

在创建二叉树时,用先序的方式递归创建;并且要有终止条件,当节点无左右子树则不继续创建

如输入 ab##c##,实际创建的为:

代码实现创建:

void Create(BiNode* &T)
{
    char str;
    cout << "请输入一个字母作为树的值: ";
    cin >> str;

    if (str == '#') //若输入#,代表创建空树
    {
        T = NULL;
    }
    else
    {
        T = new BiNode;
        T->data = str;
        //递归创建左右孩子
        Create(T->lchild); 
        Create(T->rchild);
    }

}

四种遍历二叉树的方法

四种方法:先序遍历、中序遍历、后序遍历、层序遍历,其中先序遍历、中序遍历、后序遍历只需调换输出语句和遍历语句的次序即可

先序遍历

先访问根节点,再依次访问左孩子、右孩子

void PreTravers(BiNode* &T)
{
    if (T)
    {
        cout << T->data << " ";
        PreTravers(T->lchild);
        PreTravers(T->rchild);
    }
}

中序遍历

先访问左孩子,再依次访问根节点、右孩子

void MidTravers(BiNode* &T)
{
    if (T)
    {
        MidTravers(T->lchild);
        cout << T->data << " ";
        MidTravers(T->rchild);
    }
}

后序遍历

先访问左孩子,再依次访问右孩子、根节点

void FinTravers(BiNode* &T)
{
    if (T)
    {
        FinTravers(T->lchild);
        FinTravers(T->rchild);
        cout << T->data << " ";
    }
}

层序遍历

利用队列,从上到下,从左到右进行先进先出

根节点入队列,之后进行循环(若节点不为空):输出队首元素的值,再依次访问其左、右孩子,若存在并将其入队列,再将队首节点出队

int FloTravers(BiNode *T)
{
    if (!T) //若根节点为空,结束并返回0
    {
        return 0;
    }
    BiNode *temp; //定义temp指针保存当前队列的首部地址
    queue<BiNode*>Q; //定义模板类:队列Q
    Q.push(T); //树根节点入队
    while (!Q.empty()) //若队列不为空则循环执行并输出
    {
        temp = Q.front(); //队首地址赋值给temp并输出数据
        cout << temp->data;
        if (temp->lchild) //如果当前节点存在左孩子,则将左孩子入队
        {
            Q.push(temp->lchild);
        }
        if (temp->rchild) //如果当前节点存在右孩子,则将右孩子入队
        {
            Q.push(temp->rchild);
        }
        Q.pop(); //删除队首元素
    }

}

其中:
queue模板类需要两个模板参数,一个是元素类型,一个容器类型,元素类型是必要的,容器类型是可选的,默认为deque类型。

需要加上头文件

#include<queue>

定义queue对象的示例代码如下:

queue<int> q1;

queue<double> q2;

队列模板类使用方法:

1.size()       返回队列中元素的个数
2.empty()      如果队列空则返回真 
3.back()       返回最后一个元素引用即队尾。
4.front()      返回第一个元素引用即队首。
5.pop()        删除第一个元素,即队首元素。不返回 
6.push()       在末尾加入一个元素,即放置在队尾 。不返回