数据结构06 树与二叉树

树及其相关概念

树是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。

例如我们生活中的家族族谱、公司组织结构图等都是树结构。如下图所示，即为一棵树 。

下面我们根据上图来了解一下树的相关概念：

• 树的结点：使用树结构存储的每一个数据元素都被称为“结点”。例如，图中，数据元素 A 就是一个结点；
• 父结点（双亲结点）、子结点和兄弟结点：对于图中的结点 A、B、C、D 来说，A 是 B、C、D 结点的父结点（也称为“双亲结点”），而 B、C、D 都是 A 结点的子结点（也称“孩子结点”）。对于 B、C、D 来说，它们都有相同的父结点，所以它们互为兄弟结点。
• 子树：如图中，整棵树的根结点为结点 A，而如果单看结点 B、E、F、K、L 组成的部分来说，也是棵树，而且节点 B 为这棵树的根结点。

所以称 B、E、F、K、L 这几个结点组成的树为整棵树的子树；同样，结点 E、K、L 构成的也是一棵子树，根结点为 E。

• 结点的度：拥有的子树数（结点有多少分支）称为结点的度。例如，图中，根结点 A 下分出了 3 个子树，所以，结点 A 的度为 3。一棵树的度是树内各结点的度的最大值。
• 结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推。对于上图来说，A 结点在第一层，B、C、D 为第二层，E、F、G、H、I、J 在第三层，K、L、M 在第四层。一棵树的深度（高度）是树中结点所在的最大的层次。上图树的深度为 4。

二叉树及其特点

二叉树是一种特殊的树。二叉树的特点是每个结点最多有两个儿子。根据这一特点，可以总结出二叉树的五种基本形态。

树及其相关概念

满二叉树是一棵满足两个条件的树(如下图)：

(1)所有的节点都同时具有左子树和右子树。

(2)所有的叶子节点都在同一层上。

在同样深度的二叉树中，满二叉树的节点数目是最多的，叶子数也是最多的。

完全二叉树

在一棵二叉树中，只有最下两层的度可以小于2，并且最下一层的叶子节点集中出现在靠左的若干位置上，这样的树称为完全二叉树(如下图)。

从定义可以看出： 满二叉树一定是完全二叉树；完全二叉树不一定是满二叉树。

二叉树的性质

性质一：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。

性质二：深度为k的二叉树至多有2^k-1个结点。

性质三：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层开始到最下一层，每一层从左到右编号），对任一结点i有：

(1)如果i=1,则结点为根结点，没有双亲。

(2)如果2*i>n ,则结点i没有左孩子;否则其左孩子结点为2*i(n为结点总数)。

(3)如果2*i+1>n,则结点i没有右孩子；否则其右孩子结点为2*1+1。

二叉树的遍历

遍历一棵二叉树，有四种方式，分别是先序遍历、中序遍历、后序遍历以及层次遍历，接下来我们一一介绍这四种方式（以下图所示二叉树为例）。

二叉树的先序遍历

二叉树先序遍历的实现思想是：

1、访问根结点；

2、访问当前结点的左子树；

3、若当前结点无左子树，则访问当前结点的右子树；

由此，上图中二叉树采用先序遍历得到的序列为：1 2 4 5 3 6 7

二叉树的中序遍历

二叉树中序遍历的实现思想是：

1、访问当前结点的左子树；

2、访问根结点；

3、访问当前结点的右子树；

由此，上图中二叉树采用中序遍历得到的序列为：

4 2 5 1 6 3 7

二叉树的后序遍历

二叉树中序遍历的实现思想是：

1、访问当前结点的左子树；

2、访问当前结点的右子树；

3、访问根结点；

由此，上图中二叉树采用后序遍历得到的序列为：4 5 2 6 7 3 1

二叉树的层次遍历

二叉树层次遍历的实现思想是：

按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。

由此，上图中二叉树采用层次遍历得到的序列为：1 2 3 4 5 6 7

建立二叉树

建立一个二叉树，我们需要记录每个结点的左孩子和右孩子，同时需要记录结点的信息。二叉树存储方式分为顺序存储和链式存储。顺序存储我们可以通过数组下标来记录结点信息的，通过前面的学习我们可以知道根节点与左右子树下标规律如下：

二叉树的遍历完整代码

#include <iostream>
using namespace std;

char h[1005];
string s;
int n;
int j;
void Fcreate(int i) {     //先序建树
    if(i>n) return;
    else{
        h[i]=s[j++];     //存放结点数据
        Fcreate(i*2);    //建立左子树
        Fcreate(i*2+1);  //建立右子树
    }
}

void zx(int i) //中序遍历
{
    if(i>n) return ;
    zx(i*2);    //遍历左子树
    cout<<h[i];   //输出父节点
    zx(i*2+1);     //遍历右子树
}  

void hx(int i) //后序遍历
{
    if(i>n) return ;
    hx(i*2);    //遍历左子树
    hx(i*2+1);     //遍历右子树
    cout<<h[i];   //输出父节点
}

int main()
{
    cin>>s;
    n=s.size();
    Fcreate(1);   
    //cout<<"中序遍历结果为:\n";
    //zx(1);
    cout<<"后序遍历结果为:\n";
    hx(1);
    return 0;
}