树及二叉树（数据结构）

淡淡的烟草味﹌ 2022-06-02 01:28 156阅读 0赞

\#\#\#\#一、 什么是树?  
**1，生活中的树 ：**  
![一][format_png]

我们知道，对于一棵树，无论大小， 都是由数根，树干，节点以及树叶构成，那么，在数据结构中，也存在树这种结构，与之不同的是，它是一棵倒立的树 ，模型如下所示：  
**2，数据结构中的树：**  
![图二][format_png 1]  
**3，树的基本概念：**

以上图中的树为例：

树：由N(N>=0)个结点构成的集合，N=0时是一棵空树 ，那么对N>1的树做出以下解释：

1、根节点：故名思义，根节点相当于一棵树的根，是树的基础，它是一个特殊的结点，根节点没有前驱结点，是本树所有结点的祖先。

如：A　就是该树的根节点

2、除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中：  
（1）每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以没有后继，也可以有多个后继。

B，C，D是A的子树，各自又是以自身为根节点的树 ；

`由此看出：树是递归定义的。`

3，结点：结点包括一个数据元素及若干指向其他子树的分支(指针(索引))。  
（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ）

４， 叶结点：度为0的结点称为叶结点，叶节点也称为终端节点。  
（Ｅ，Ｆ，Ｇ，Ｈ，Ｉ）

５， 分支结点：度不为0的结点称为分支结点，分支结点也称为非终端节点，一棵树中除叶节点外的所有节点都是分支结点。  
（Ａ，Ｂ，Ｃ，Ｄ）

６， 祖先结点：从根节点到该结点所经分支上的所有节点。  
（Ｅ的祖先结点是Ａ，Ｂ）  
（Ｆ的祖先结点是Ａ，Ｃ）

７，子孙结点：以某节点为根节点的子树中所有节点。  
（Ａ的子孙结点为Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ）

８，双亲结点：树中某节点有孩子结点，则这个结点称为它孩子结点的双亲结点，双亲结点也称为前驱结点。  
（Ｅ的双亲结点是Ｂ，Ｂ的双亲结点是Ａ）

９， 孩子结点：树中一个节点的子树的根节点称为该结点的孩子结点，孩子结点也称为后继结点。  
（Ａ的孩子节点是Ｂ，Ｃ，Ｄ）

１０，兄弟结点：具有相同双亲结点的结点称为兄弟结点。  
（Ａ为Ｂ，Ｃ，Ｄ的双亲结点，所以，Ｂ，Ｃ，Ｄ，互为兄弟结点）

１１， 结点的度：结点所拥有子树的个数称为该结点的度。  
（Ａ的度为３）

１２， 树的度：树中所有节点的度的最大值称为该树的度。  
（该树中，所有结点度的最大值为３，故树的度为３）

１３， 结点的层次：从根节点到树中某节点所经路径上的分支数称为该结点的层次，根节点的层次为1， 其他结点层次是其双亲结点层次加1.  
![图三Ｎ][format_png 2]

１４， 树的深度：树中所有节点的层次的最大值称为该树的深度。  
（该树的深度为３）

１５，有序树：树中结点的各棵子树T0、T1…是有序的，即为有序树。其中T1叫做根的第一棵子树，T2叫根的第二棵子树…

１６，无序树：树中结点的各棵子树之间的次序不重要，可以相互交换位置。

１７，森林：树m棵树的集合(m大于等于0)。在自然界中树和森林是两个不同的概念，但在数据结构中，它们之间的差别很小。删去一棵非空树的根节点，树就变成森林；反之若增加一个节点，让森林中每一棵树的根节点都变成他的子女，森林就变成一棵树。

**４，树的表示方法：**

（１）目录结构表示：  
（２）集合文示图表示：　  
![四][format_png 3]  
　示意图如下　：  
　![format_png 4][]

１，树的存储结构  
计算机中存储树的信息，要求既要存储结点的数据元素信息，又要存储结点之间的逻辑关系信息。  
![format_png 5][]

//最常用的是孩子表示法

![format_png 6][]  
\#\#\#\#二，什么是二叉树？　  
![format_png 7][]  
　　　　　　　　　　　　　　　　图一  
**１，二叉树：**  
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成。

**２，二叉树的五种形态：**

![format_png 8][]  
**３，二叉树的特点：**  
（1）每个结点最多有两棵子树，即二叉树不存在度大于2的结点

（2）二叉树的子树有左右子树之分，其子树的次序不能颠倒  
　  
**４，满二叉树：**  
在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子节点都在同一层上。

**５，完全二叉树：**  
如果一棵具有N个结点的二叉树的结构与满二叉树的前N个结点的结构相同，称为完全二叉树。

**６，二叉树的性质：**　（以图一为例）

1、若规定根节在点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点  
其中(i>=1)  
（如第三层，最多有２^（３－１）＝４个结点）

2、若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是  
2^k-1，其中(k>=0)  
（２^4-1=15个结点）

3、对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则具有n个结点的完全二叉树的深度k为log2(n+1)上取整。

（floor()……向下取整函数，ceil()……向上取整函数

４、对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

a：如果i>0，则序号为i结点的双亲结点的序号为(i-1)/2；如果i=0，则序号为i的结点为根节点，无双亲结点b：

ｂ：如果2i+1<n，则序号为i的结点的左孩子结点的序号为2i+1；如果2i+1>=n，则序号为i结点无右孩子结点

ｃ：如果2i+2<n，则序号为i结点的右孩子结点的序号为2i+2；如果2i+2>=n，则序号为i结点无右孩子结点

//举个例子：
    //如果一棵完全二叉树总共有１０００个节点，求它的度为２的结点，度为１的结点，以及叶子结点　共有多少个？　
    //设度为０，为１，为２的结点分别有：Ｎ０，Ｎ１，Ｎ２个，则有：
    //Ｎ０＋Ｎ１＋Ｎ２＝１０００；
    //已知度为０的结点永远比度为２的结点多一个，也就是Ｎ０＝Ｎ２＋１；
    //则Ｎ１＋２Ｎ２＋１＝１０００；
    //又因为总的结点个数为１０００，是偶数，所以，度为１的结点只有一个
    //也就是说：１＋２Ｎ２＋１＝１０００?
    //化简得：Ｎ２＝９９８／２＝４９９；
    //故而：Ｎ０＝Ｎ２＋１＝４９９＋１＝５００；
    //Ｎ０＋Ｎ１＋Ｎ２＝５００＋１＋４９９＝１０００；与题意相符，说明计算正确；

**７，二叉树的存储结构**

二叉树的存储结构主要有三种：顺序存储、链式存储和仿真指针(静态链表)存储结构。

（１）树的遍历：

//前序遍历(根结点＋左子树＋右子树)
    //中序遍历（左子树＋根结点＋右子树）
    //后序遍历（左子树＋右子树＋根结点）
    //前，中，后指的是遍历根结点的次序

（２）【顺序存储】

![format_png 9][]

设有一棵二叉树(最好完全二叉树)，对它所有的结点按照层次次序自顶向下，同一层自左向右顺序编号，就得到一个节点的顺序序列。对于一般的二叉树，为了能找到某一结点的上下左右关系，也必须仿照完全二叉树的方式来存储，遇到空树，在顺序表中应该将该位置空出来。  
（如下将空树用＃表示）  
![format_png 10][]

![format_png 11][]

\#\#\#\#三,树的基本操作:

1.二叉树的实现：

#include<stdio.h>
    #include<queue>
    #include<stack>
    #include<list>
    #include<iostream>
    using namespace std;
    
    //二叉树节点
    template<class T>
    struct BinaryTreeNode
    {
        BinaryTreeNode()
            :_pLeft(NULL)
            ,_pRight(NULL)
        {}
        T _data;//数据
        BinaryTreeNode<T>* _pLeft;//左孩子
        BinaryTreeNode<T>* _pRight;//右孩子
    };
    
    //二叉树
    template<class T>
    class BinaryTree
    {
    public:
    typedef BinaryTreeNode<T> Node;
    private:
    Node* _pRoot;//根节点
    }

![format_png 12][]  
2.二叉树的基本操作：

1).二叉树的创建：

BinaryTree()//空二叉树的构造函数
            :_pRoot(NULL)
        {}
        //带参数二叉树的构造函数，arr为前序遍历得到的一组序列
        BinaryTree(const T arr[],size_t size,T& invalid)
        {
            size_t index = 0;
        }
    
    //封装的底层函数       
    _CreateBinaryTree(_pRoot,arr,size,index,invalid);//创建二叉树  
    {
      void _CreateBinaryTree(Node*& pRoot,const T arr[],size_t size,size_t& index,T& invalid)//创建二叉树
        {
         if(arr==NULL || size<=0 || index<0 || index>size+2)//判断参数合法性
         return;
     if(arr[index]!=invalid)
       {
          pRoot = new Node;
          pRoot->_data = arr[index];
     _CreateBinaryTree(pRoot->_pLeft,arr,size,++index,invalid);
     //注意index是不断加一的，不能用index+1或者index++来替换++index,因为在回退的过程中index也会回退
     _CreateBinaryTree(pRoot->_pRight,arr,size,++index,invalid);//同时也要注意index做参数要用引用接收，也是为了避免这个问题
       }
      }
     }

![format_png 13][]

2).二叉树的拷贝构造函数

BinaryTree(const BinaryTree<T> & t)//二叉树的拷贝构造函数
        {
            _pRoot = _CopyBinaryTree(t._pRoot);
        }
    
    Node* _CopyBinaryTree(Node* pRoot)//拷贝二叉树
        {
            Node* pCur = NULL;
            if(pRoot != NULL)
            {
                pCur = new Node;
                pCur->_data = pRoot->_data;
                pCur->_pLeft = _CopyBinaryTree(pRoot->_pLeft);
                pCur->_pRight = _CopyBinaryTree(pRoot->_pRight);
            }
            return pCur;
        }

![format_png 14][]

3).二叉树的赋值运算符重载

BinaryTree<T>& operator=(const BinaryTree<T>& t)//二叉树的赋值运算符重载
        {
            if(this != &t)
            {
                _DestoryBinaryTree(_pRoot);//先析构*this
                _pRoot = _CopyBinaryTree(t._pRoot);//再用t拷贝构造*this
            }
            return *this;
        }

![format_png 15][]  
4).二叉树的析构函数

~BinaryTree()//析构二叉树
        {
            _DestoryBinaryTree(_pRoot);
        }
    
    void _DestoryBinaryTree(Node* &pRoot)//销毁二叉树(利用后序遍历，先删除左节点，再删除右节点，最后删除根节点)
        {
            if(pRoot != NULL)
            {
                _DestoryBinaryTree(pRoot->_pLeft);
                _DestoryBinaryTree(pRoot->_pRight);
                delete pRoot;
                pRoot = NULL;
            }
        }

[format_png]: /images/20220602/fc477a17828646fcabf7676a730772af.png
[format_png 1]: /images/20220602/37e45e5665754acd98b99c4c7d4d2f5f.png
[format_png 2]: /images/20220602/28a909db615648999035711eb9abcbf5.png
[format_png 3]: /images/20220602/758b3b7d08b4401d9e0d95c3e7f336e9.png
[format_png 4]: /images/20220602/b5b5f7f5fbe24f15be179a17aa94afa4.png
[format_png 5]: /images/20220602/c387c53938704b38888c4e6b1455a691.png
[format_png 6]: /images/20220602/6757ea332fad40b8ac6af18265216570.png
[format_png 7]: /images/20220602/44d80a48079441f580bf0dfcf69a5c8f.png
[format_png 8]: /images/20220602/aa4e29146fbd41748ba842b19d727001.png
[format_png 9]: /images/20220602/c059d37499544f129012fc714586ec8c.png
[format_png 10]: /images/20220602/b186cd51ea7d492fb3c5ce5206256b89.png
[format_png 11]: /images/20220602/136b2ec280d1463b927e6bd75b61a43a.png
[format_png 12]: /images/20220602/b0878bb6a24c4d0cba73d468288028ea.png
[format_png 13]: /images/20220602/d984e9c562da44bbad4a4363c4219056.png
[format_png 14]: /images/20220602/b93a89e0fc3c4bdab12e96fa00de0530.png
[format_png 15]: /images/20220602/95d4f047475745d68db72ad4a55d2626.png