二叉树的形态、分类、存储、以及遍历和计数

一.  前言

数据结构终于学到了树这一章，一直觉得这章很有意思，各种树非常好玩，上周刚学完二叉树，特意将二叉树的相关知识整理如下：

二.  二叉树的定义

在计算机科学中，二叉树（Binary tree）是每个节点最多只有两个分支(不存度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序，不能颠倒。

二叉树的定义一般由递归形式给出：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成

三.  二叉树的五种不同的形态

根据二叉树的定义和特点，可以将二叉树分为五种不同的形态，如下图：

1.  空二叉树：如图(1)

2.  只有一个根结点的二叉树：如图(2)

3.  只有左子树：如图(3)

4.  只有右子树，如图(4)

5.  完全二叉树：如图(5)

四.  二叉树的性质

1.  在非空二叉树中，二叉树的第i( i>=1)层最多有2^(i-1)个结点

2.  深度为k(k>=0)的二叉树最多有(2^k ) – 1，最少有k个结点；

3.  对于任意一棵非空二叉树如果其叶结点数为n0，而度数为2的非叶结点总数为n2，则n0=n2+1；

4.  具有n个结点的完全二叉树的深度为⌈ log2(n+1) ⌉（ ⌈  向上取整的意思  ⌉ ）

5.  给定N个节点，能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。

6.  设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i[4]

7.  如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,3，…，n，然后按此结点编号将树中各节点顺序地存放于一个一维数组中，并简称编号为i的结点为结点i(1 <= i <=n)，则有以下关系：

a：若i = 1，则结点i为根，无父结点；若 i > 1，则结点i的父结点为结点 ⌊  (i / 2)  ⌋ （ ⌊  向下取整的意思  ⌋ ）

b：若2 * i <= n ，则结点i的左子女为结点 2 * i，若2 * i >n，则 i 无左子

c：若2 * i + 1 <= n，则结点i的右子女为结点2 * i+ 1，若2 * I+1>n，则i无右子。

d：若结点编号i为奇数，且 i != 1，它处于右兄弟位置，则它的左兄弟为结点 i – 1

e：若结点编号i为偶数，且 i != n，它处于左兄弟位置，则它的右兄弟为结点 i + 1

f：结点i所在层次为： ⌊   (log2 i)   ⌋  + 1（ ⌊  向下取整的意思  ⌋ ）

 

8.  如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0,1,2，…，n – 1，然后按此结点编号将树中各节点顺序地存放于一个一维数组中，并简称编号为i的结点为结点i(0 <= i <=n – 1)，则有以下关系：

a：若i = 0，则结点i为根，无父结点；若 i > 0，则结点i的父结点为结点 ⌊ ((i – 1) / 2) ⌋（ ⌊  向下取整的意思  ⌋ ）

b：若2 * i  + 1 <=  n – 1，则结点i的左子女为结点 2 * i + 1，若2 * i  + 1 > n – 1 ，则 i 无左子

c：若2 * i  + 2 <=  n – 1，则结点i的右子女为结点2 * i+ 2，2 * i  + 2 >  n – 1，则i无右子

d：若结点编号i为奇数，且 i != n – 1，它处于左兄弟位置，则它的右兄弟为结点 i + 1

e：若结点编号i为偶数，且 i != 0，它处于右兄弟位置，则它的左兄弟为结点 i – 1

f：结点i所在层次为： ⌊ (log2(i + 1) ) ⌋ + 1 （ ⌊  向下取整的意思  ⌋ ）

9.  完全二叉树有n个结点，则有⌈ (n/2) ⌉个叶节点（ ⌈  向上取整的意思  ⌉ ）

10.完全二叉树有n个结点，则最后一个分支节点下标：（n – 2）/ 2

五.  二叉树的分类

1.  满二叉树

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树，如下图：

2.  完全二叉树

如果一棵二叉树有n个结点，深度为k，它的每一个结点都与高度为k的满二叉树中编号为1~n的结点一一对应，则称该树为完全二叉树。如下图：

3.  平衡二叉树

平衡二叉树又称AVL树，平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树

，如下图：

六.  二叉树存储表示

1.  用数组存储表示

1.1 完全二叉树的数组存储表示

将数组从下标为1的元素按照性质7开始存储，但是这样会浪费下标为0的这个元素空间，所以也可以

将数组从下表为0的元素按照性质8开始存储，存储的时候自顶向下，从左向右的顺序依次存储，这种存储方式是完全二叉树最简单最省存储的存储方式，下图以性质7为例

1.2  一般的二叉树数组存储表示

在存储的时候，如果遇到空子树，应该把相应的位置留空，如下图：

通过该图可以看到，一般的二叉树用数组存储是非常浪费空间，所以一般二叉树一般用下面的链表存储表示

2.  用链表存储表示

我们可以看到，二叉树中每个节点都有三个域构成：结点数据，左子，右子，所以我们用链表存储二叉树的时候，应该至少包括三个域，如下图：

为了方便查找每个节点的父节点，也可以在结点中增加父指针域，称之为：三叉链表

七.  二叉树的遍历

1.  前序遍历

前序遍历的顺序为：父 —> 左 —> 右

代码实现：

void PreOrder(Node* node)//前序遍历
{
    if(node == NULL) return;
    cout << " " << node -> data;
    PreOrder(node -> left);
    PreOrder(node -> right);
}

2.  中序遍历

中序遍历的顺序为：左 —> 父 —> 右

代码实现：

void InOrder(Node* node)//中序遍历
{
    if(node == NULL) return;
    InOrder(node -> left);
    cout << " " << node -> data;
    InOrder(node -> right);
}

3.  后序遍历

后序遍历的顺序为：左 —> 右 —> 父

void PostOrder(Node* node)//后序遍历
{
    if(node == NULL) return;
    PostOrder(node -> left);
    PostOrder(node -> right);
    cout << " " << node -> data;
}

4. 举例

举一个例子加深理解，用二叉树表示下述表达式：a+b*(c-d)-e/f

前序遍历的序列是：-  +  a  *  b  –  c  d  /  e  f

中序遍历的序列是：a  +  b  *  c  –  d  –  e  /  f

后序遍历的序列是：a  b  c  d  –  *  +  e  f  /  –

八.  二叉树的计数

给定前序序列和中序序列能够唯一地确定一棵二叉树

举例：给定一棵二叉树的前序序列（ABHFDECKG）和中序序列（HBDFAEKCG），如何唯一的确定一棵二叉树？

解题步骤：

1.  首先确定根结点，前序序列的第一个结点，肯定为根结点，所以该树的根结点为A，如下图：

2.  中序遍历的顺序为：左 —> 父 —> 右，也就是在中序序列中

将根结点A作为父结点将一棵二叉树一分为二（（HBDF）A（EKCG）），如下图：

3.  前序遍历的顺序为：父 —> 左 —> 右，所以取前序序列中的第二个元素B，这个B就是根结点A的左子，如下图：

4.  同时B又是一个父节点，和第2步一样，再次将中序序列剩下的元素一分为二（（H）B（DF）），如下图：

5.  此时H为叶节点，同时又是B的左子，那么前序序列中H后面的元素F一定为B的右子

同时F又是一个父节点，和第2步一样，再次将中序序列剩下的元素一分为二（（D）F（）），所以F没有右子，如下图：

6.  此时根结点A左边的序列（HBDF）各个元素位置已经确定，再看右边的序列（EKCG）

7.  第5步的D为叶节点，所以前序序列中D后面的元素E，一定为A的右子，如下图：

8.  E作为A的右子，同时又是父结点，和第2步一样，再次将中序序列剩下的元素一分为二（（）E（KCG）），所以E没有左子，如下图：

9.  E既然没有左子，那么前序序列中E后面的元素C一定为E的右子，如下图：

10.  C作为E的右子，同时又是父结点，和第2步一样，再次将中序序列剩下的元素一分为二（（K）C（G）），则K为C的左子，G为C的右子，K和G又分别是叶节点，则确定了唯一的二叉树，如下图：

11.  可以看到，整个过程都是前序—>中序—>前序—>中序—>前序—>中序……的顺序进行判断

九.  代码实现

用链表的方式存储二叉树，并实现前序，中序，后序，求和，求结点数

#include <iostream>
using namespace std;
/*
 *static int node = 0;//用构造方法统计结点个数,不推荐
 *static int num = 0;//用构造方法统计结点数据总和,不推荐
 */
class Node //二叉树的节点类
{
public:
    int data;//数据域
    Node* left;//左子链域，指向该结点的左子
    Node* right;//右子链域，指向该结点的右子
    Node()  //无参构造函数
    {
        data = 0;
        left = right = NULL;
    }
    Node(Node* l,int d, Node* r)  //带参构造函数，初始化数据
    {
        //node++;//用构造方法统计结点个数,不推荐
        this -> left = l;
        this -> data = d;
        this -> right = r;
        //num += data;//用构造方法统计结点数据总和,不推荐
    }

/*
 *  int nodes()//用构造方法统计结点个数,不推荐
 *   {
 *       return node;
 *   }
 *   int sumData()//用构造方法统计结点数据总和,不推荐
 *   {
 *       return num;
 *   }
 */   
};

class BinTree//二叉树类
{
public:
    Node* root;//表头指针，指向二叉树的根结点，当做树的访问点
    BinTree()
    {
        root = NULL;
    }
    void PreOrder(Node* node);//前序遍历
    void PreOrder()
    {
        PreOrder(root);
    }
    void InOrder(Node* node);//中序遍历
    void InOrder()
    {
        InOrder(root);
    }

    void PostOrder(Node* node);//后序遍历
    void PostOrder()
    {
        PostOrder(root);
    }

    int CountNode (Node* node);
    int SumData(Node* node);

};
int BinTree :: CountNode(Node* node)
 {
        if(node == NULL)
        {
            return 0;
        }
        else
        {
        return 1 + (CountNode(node -> left) +  CountNode(node -> right));
        }
 }
int BinTree :: SumData(Node* node)
 {
        if(node == NULL)
        {
            return 0;
        }
        else
        {
        return node -> data + (SumData(node -> left) +  SumData(node -> right ));

        }
 }
void BinTree :: PreOrder(Node* node)//前序遍历
{
    if(node == NULL) return;
    cout << " " << node -> data;
    PreOrder(node -> left);
    PreOrder(node -> right);
}

void BinTree :: InOrder(Node* node)//中序遍历
{
    if(node == NULL) return;
    InOrder(node -> left);
    cout << " " << node -> data;
    InOrder(node -> right);
}
void BinTree :: PostOrder(Node* node)//后序遍历
{
    if(node == NULL) return;
    PostOrder(node -> left);
    PostOrder(node -> right);
    cout << " " << node -> data;
}

int main()
{
    BinTree b;//创建一个二叉树类b
    b.root =  new Node(NULL,6,NULL);//将二叉树b的根结点数据设置为6
    Node* a = new Node(new Node(NULL,4,NULL),3,new Node(NULL,5,NULL));
    Node* c = new Node(new Node(NULL,7,NULL),2,NULL);
    b.root -> left = a;
    b.root -> right = c;
    /* 
     * b.root =  new Node(new Node(new Node(NULL,4,NULL),3,new Node(NULL,5,NULL)),
     *                     6,//将上面5行代码整合为1行，更简洁的写法
     *                     new Node(new Node(NULL,7,NULL),2,NULL));
     */
    cout << "前序遍历：";
    b.PreOrder();
    cout << endl;
    cout << "中序遍历：";
    b.InOrder();
    cout << endl;
    cout << "后序遍历：";
    b.PostOrder();
    cout << endl;
    cout << "结点总数：";
    cout << b.CountNode(b.root);
    cout << endl;
    cout << "所有结点数据和：";
    cout << b.SumData(b.root);
    return 0;
}