数据结构二叉树的建立与遍历

骑猪看日落 2022-05-26 12:46 166阅读 0赞

二叉树（Binary Tree）是n（n >= 0）个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不相交的，分别称为根节点的左子树和右子树的二叉树组成。

二叉嘛，也就是每个节点最多有两个分支。

图示：

![20180502204438617][]

二叉树具有五种基本形态：

1.空二叉树

2.只有一个根节点

3.根节点只有左子树

4.根节点只有右子树

5.根节点既有左子树又有右子树

特殊的二叉树：

1.斜树（只有左子树的称为左斜树，只有右子树的称为右斜树，两者统称为斜树）

2.满二叉树（所有的分支节点都存在左子树和右子树，并且所得树叶都在同一层上）

![20180502205405916][]

3.完全二叉树（对一颗具有n个节点的二叉树按层序编号，如果编号为i（1 <= i <= n）的节点与同样深度的满二叉树中编号为i的节点在二叉树中位值完全相同）

如果理解不了看下面的图，体会它们的共同特征

![20180502210058209][]

完全二叉树的特征：

1.叶子结点只能出现在最下两层

2.最下层的叶子一定集中在左部连续位置

3.倒数二层，若有叶子结点，一定都在右部连续位置

4.如果节点度为1（这里的度与离散数学中的度不一样，这里的度是指节点所拥有的子树数），则该节点只有左孩子，即不存在只有右子树的情况

5.同样节点数的二叉树，完全二叉树的深度最小

二叉树的性质：

性质1：在二叉树的第i层上至多有2^（i - 1）个节点（i >= 1）

性质2：深度为k的二叉树至多有2^k - 1个节点（k >= 1）

性质3：对任何一颗二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0 = n2 + 1

性质4：具有n个节点的完全二叉树的深度为\[log2n\] + 1（\[\]表示不大于x的最大整数）

性质5：如果对一颗有n个节点的完全二叉树（其深度为\[long2n\] + 1）的节点按层序编号（从第1层到第\[log2n\] + 1层，每层从左到右），对任一节点i（1 <= i <= n）有

①如果i = 1，则节点i是二叉树的根，无双亲；如果i > 1，则双亲是节点\[i / 2\]

②如果2i > n，则节点i无左孩子（节点i为叶子结点）；否则其左孩子是节点2i

③如果2i + 1 > n，则节点i无右孩子；否则其右孩子是节点2i + 1

二叉树的存储结构同样分为两种：

一种为二叉树顺序存储结构，另一种为二叉树的链式存储结构

一般顺序存储结构只用于完全二叉树

下面我们来介绍链式存储结构的二叉树，，，

二叉链表：有一个数据域和两个指针域

二叉链表的节点结构定义：

typedef struct BiTNode
    {
        TElemType data; //节点数据
        struct BiTNode *lchild, *rchild;    //左右孩子指针
    }BiTNode, *BiTree;

emmm，说下二叉树的建立吧，先输入根，再输入左子树，再输入右子树（左边优先）

void CreatBiTree(BiTree &T)
    {
        TElemType ch;
        cin >> ch;
        if(ch == '#')    //#代表为空
            T = BULL;
        else
        {
            T = new BiTNode;    //生成根节点
            if(!T)
                exit(1);
            CreatBiTree(T->lchild); //构造左子树
            CreatBiTree(T->rchild); //构造右子树
        }
    }

遍历二叉树（简单说下）

二叉树的的遍历主要分为4种：前序遍历，中序遍历，后序遍历，层序遍历

前序排序：若树为空返回，不为空先访问根节点，再访问左子树，再访问右子树（根左右）

递归法的前序排序：

void PreOrderTraverse(BiTree T)
    {
        if(!T)
            return ;
        else
        {
            cout << T->data;
            PreOrderTraverse(T->lchild);
            PreOrderTraverse(T->rchild);
        }
    }

中序排序：若树为空返回，不为空先访问左子树，再访问根节点，再访问右子树（左根右）

递归法的中序排序：

void InOrderTraverse(BiTree T)
    {
        if(!T)
            return ;
        else
        {
            InOrderTraverse(T->lchild);
            cout << T->data;
            InOrderTraverse(T->rchild);
        }
    }

后序排序：若树为空返回，不为空先访问左子树，再访问右子树，再访问根节点（左右根）

递归法的后序排序：

void PostOrderTraverse(BiTree T)
    {
        if(!T)
            return ;
        else
        {
            PostOrderTraverse(T->lchild);
            PostOrderTraverse(T->rchild);
            cout << T->data;
        }
    }

层序排序：若树为空，则空操作返回，否则从树的第一层开始从上到下，从左到右，依次按顺序循环遍历

以下面此图测试下，

![20180503165551824][]

如果节点为空，则用\#代替

依次输入ABDH\#K\#\#\#E\#\#CFI\#\#\#G\#J\#\#

代码部分：

#include <iostream>
    #include <cstdlib>
    using namespace std;
    
    
    //二叉树链表的存储结构
    typedef struct BiTNode
    {
        char data;   //节点数据
        struct BiTNode *lchild, *rchild;    //左右孩子指针
    }BiTNode, *BiTree;
    //二叉树的建立
    void CreatBiTree(BiTree &T)
    {
        char ch;
        cin >> ch;
        if(ch == '#')
            T = NULL;
        else
        {
            T = new BiTNode;    //生成根节点
            if(!T)
                exit(1);
            T->data = ch;
            CreatBiTree(T->lchild); //构造左子树
            CreatBiTree(T->rchild); //构造右子树
        }
    }
    //前序遍历
    void PreOrderTraverse(BiTree T)
    {
        if(!T)
            return;
        cout << T->data;    //显示节点数据
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    //中序遍历
    void InOrderTraverse(BiTree T)
    {
        if(!T)
            return;
        InOrderTraverse(T->lchild);
        cout << T->data;    //显示节点数据
        InOrderTraverse(T->rchild);
    }
    //后序遍历
    void PostOrderTraverse(BiTree T)
    {
        if(!T)
            return;
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout << T->data;    //显示节点数据
    }
    int main()
    {
        BiTree T;
        CreatBiTree(T);
        cout << "前序排序：";
        PreOrderTraverse(T);    //前序排序
        cout << endl;
        cout << "中序排序：";
        InOrderTraverse(T);     //中序排序
        cout << endl;
        cout << "后序排序：";
        PostOrderTraverse(T);   //后序排序
        cout << endl;
        return 0;
    }

运行结果：

![70][]

[20180502204438617]: /images/20220526/bc4423ad5bf64213851790a73fac2424.png
[20180502205405916]: /images/20220526/9247a50185814b51b96166e2bc057bdd.png
[20180502210058209]: /images/20220526/1295e8581d2e4bc8acafdbde8a7ad266.png
[20180503165551824]: /images/20220526/2ca684499a10476fac1b557245bc919b.png
[70]: /images/20220526/f42efdf828594183844fa3a51754f350.png