二叉树的概念、存储、实现

比眉伴天荒 2022-12-06 15:13 132阅读 0赞

**树**是有n个节点的**有限集合**，并且有且**只有一个根节点** （其实小编觉得这个和病毒的传播有一定的相似之处，想象一下 一种病毒 只能传播有限个个体，如下图所示）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center]

这就是祖父节点能够传播三个个体的树，而子节点只能传播两个个体的树  
其中的一些概念也可以用病毒的传播来解释  
**结点**：每一个携带病毒的个体  
**结点的度**：每一个个体可以感染其他个体的数量  
**树的度**：一个群体中感染人最多的个体的度即为这个群体的度  
**叶子**：没有感染其他个体，但自己确实病毒携带体的个体  
**非终端结点**：感染过其他个体的个体  
**双亲和孩子**：将个体感染的个体叫做这个个体的双亲 ， 而个体感染的个体叫孩子  
**兄弟**：同一个感染源的个体叫兄弟  
**祖先**：一条感染的线路中，所有的个体都是这条感染线路的祖先  
**子孙**：感染线路中的每一个个体都是初代体的子孙  
**层次**：第几代被感染的就是层次  
**堂兄弟**：双亲在同一层的个体即为堂兄弟  
**树的深度**：一个群里感染了多少代就是这个群体的深度

## 下面是课本中的定义 ##

**结点**：树中的每一个独立的单元  
**结点的度**：节点拥有的子树的数目成为节点的度  
**树的度**：树内各个节点的度的最大值  
**叶子**：度为0的结点成为叶子结点  
**非终端结点**：度不为0的结点  
**双亲和孩子**：结点的子树成为节点的孩子，相应的，该节点成为孩子的双亲  
**兄弟**：同一个双亲的孩子节点  
**祖先**：从根到该节点所经过的分支上的所有结点  
**子孙**：以某结点为根的子树中的所有结点都称之为该节点的子孙  
**层次**：结点的层次从根开始定义，根为第一层，根的孩子称为第二层，以此类推  
**堂兄弟**：双亲在同一层的结点即为堂兄弟  
**树的深度**：树中节点的最大层次称为树的深度或者高度

## 相应的二叉树就是每一个个体可以传播两个个体的树 ##

## 二叉树有如下性质 ##

**1**.在二叉树的第i层上最多有2的i-1次方个结点  
**2**.深度为k的二叉树最多有2的k次方减1个结点  
**3**.如果终端结点的个数为n，度为2的结点数为n1 则 n = n1+1

**几种特殊形式的二叉树**  
满二叉树  
每一层上的结点都是最大值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 1]  
**完全二叉树**  
深度为k的时候，有n个结点的二叉树，当且仅当每一个结点都与深度为k 的满二叉树中编号从1-n的结点一一对应的时候，称之为完全二叉树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 2]**4**.具有n个结点的完全二叉树的深度为以2为底n的对数向下取整再+1  
**5**.如果对一棵具有n个结点的完全二叉树的结点按照层次进行编号则对任意一个结点都有  
（1）如果编号为1则为根节点  
（2）如果编号大于1，则其双亲为i/2向下取整数  
（3）如果2i>n则结点i没有做盖子，否则2i为其左孩子，2i+1也是同样，为其右孩子。

## 存储结构 ##

与前面的存储结构相似，具有链式存储结构和顺序存储结构  
**顺序存储结构**

#define MAXSIZE 100
    typedef ubt sqBiTree[MAXSIZE];
    sqBiTree  bt;

**链式存储结构**

typedef struct biTNode{
        
    	int data;       //每一个结点所存储的真实数据 
    	biTNode *lchild,*rchild;    //定义每一个结点的左右指针 
    }*biTree;

以下的代码实现是基于链式存储结构的实现  
**初始化一棵树的方法（与单链表的初始化相同）**

biTNode *initTree(){
        
    	biTree b = new biTNode;     //使用c++的new进行分配空间 也可以使用malloc函数进行分配 
    	b->rchild = NULL;     //初始化领左右指针指向空 
    	b->lchild = NULL;
    	b->data = 0;    //初始化根节点的数据为0   也可以使用其他值  或者使用参数进行传入 
    	return b;    //返回创建好的根节点 
    }

**插入左孩子**

//插入一个左结点
    bool insertLeftChild(biTree b,int ldata){
        
    	biTNode *l = new biTNode;    //申请一个新的结点 
    	l->data = ldata;    //填入数据   
    	l->lchild = NULL;   //初始化左右指针 
    	l->rchild = NULL;     
    	b->lchild = l;//   根节点的左指针指向  新创建的结点 
    }

**插入右孩子**

//插入一个右结点
    bool insertRightChild(biTree b,int rdata){
        
    	biTNode *r = new biTNode;
    	r->data = rdata;
    	r->lchild = NULL;
    	r->rchild = NULL;
    	b->rchild = r;
    }

**遍历二叉树**

//中序遍历二叉树（可以理解为 输出语句在上为先序遍历，输出语句在中间为中序遍历，输出语句在后面 即为后序遍历） 
    void printTree(biTree &bt){
        
    	if(bt){
            //判断树是否为空，  若不为空  输出数据   递归调用自身 
    	printTree(bt->lchild);  
    	cout<<bt->data<<endl;
    	printTree(bt->rchild);
    	}
    }

**完整测试代码**

/**
    二叉树的代码实现以及各种遍历的算法 
    **/
    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    typedef struct biTNode{
        
    	int data;       //每一个结点所存储的真实数据 
    	biTNode *lchild,*rchild;    //定义每一个结点的左右指针 
    }*biTree;
    //初始化并且建立一个二叉树的根节点 
    biTNode *initTree(){
        
    	biTree b = new biTNode;     //使用c++的new进行分配空间 也可以使用malloc函数进行分配 
    	b->rchild = NULL;     //初始化领左右指针指向空 
    	b->lchild = NULL;
    	b->data = 0;    //初始化根节点的数据为0   也可以使用其他值  或者使用参数进行传入 
    	return b;    //返回创建好的根节点 
    }
    //插入一个左结点
    bool insertLeftChild(biTree b,int ldata){
        
    	biTNode *l = new biTNode;    //申请一个新的结点 
    	l->data = ldata;    //填入数据   
    	l->lchild = NULL;   //初始化左右指针 
    	l->rchild = NULL;     
    	b->lchild = l;//   根节点的左指针指向  新创建的结点 
    } 
    
    //插入一个右结点
    bool insertRightChild(biTree b,int rdata){
        
    	biTNode *r = new biTNode;
    	r->data = rdata;
    	r->lchild = NULL;
    	r->rchild = NULL;
    	b->rchild = r;
    } 
    //中序遍历二叉树（可以理解为 输出语句在上为先序遍历，输出语句在中间为中序遍历，输出语句在后面 即为后序遍历） 
    void printTree(biTree &bt){
        
    	if(bt){
            //判断树是否为空，  若不为空  输出数据   递归调用自身 
    	printTree(bt->lchild);  
    	cout<<bt->data<<endl;
    	printTree(bt->rchild);
    	}
    } 
    int main(){
            //测试方法 
    	biTree bt = initTree();
    	insertLeftChild(bt,1);
    	insertRightChild(bt,2);
    	insertLeftChild(bt->lchild,3);
    	insertRightChild(bt->lchild,4);
    	insertLeftChild(bt->rchild,5);
    	insertRightChild(bt->rchild,6);
    	printTree(bt);
    	return 0;
    }

测试代码中建立的二叉树如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/91f6bb3c0a5a490fba4bc96e72e4f402.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/db50cd3e347643cdb9f8b22e0b17b0c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/7b3184219f1d4dadaa5e5d617e8d4745.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/a91ee89777c04a969c1d8f6b48bfbcc8.png