树的概念与二叉树基础内容

港控/mmm° 2023-07-25 14:15 13阅读 0赞

## 一、树和二叉树的定义 ##

### 1、树的定义 ###

**树**是n（n≥0）个结点的有限集，n=0时称为空树；  
对于非空树（n≠0）而言：  
（1）有且仅有一个称为根的结点；  
（2）除根节点以外的其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个集合本身又是一棵树，并称为根的子树；

### 2、树的基本术语 ###

（1）**结点的度：** 结点拥有的子树数称为结点的度；  
（2）**树的度：** 树的度是树内结点度的最大值；  
（3）**叶子结点：** 度为0的结点，也叫做终端结点；  
（4）**双亲和孩子：** 结点的子树的根称为该结点的孩子，相应的，该结点  
称为孩子的双亲；  
（5）**层次：** 结点的层次从根开始定义起，根为第一层，根的孩子为第二层  
（6）**树的深度：** 树中结点的最大层次称为树的深度或高度；

### 3、二叉树的定义 ###

**二叉树**是n(n≥0)个结点所构成的集合，n=0时称为空树；  
对于非空树（n≠0）而言：  
（1）有且仅有一个称为根的结点；  
（2）除根节点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树。且T1和T2本身又都是二叉树；  
**注意：** 二叉树与树的区别：  
二叉树不是树的特例，他们是两个不同的数据结构；  
（1）二叉树每个结点至多有两个子树（即二叉树中不存在度大于2的结点）  
（2）二叉树的子树有左右之分，其次序不能颠倒。

## 二、二叉树的性质 ##

**性质1：** 在二叉树的第i层上至多2^(i-1)个结点（i>=1)。  
**性质2：** 深度为k的二叉树结点至多有2^k-1个结点（k>=1)。  
**性质3：** 对任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2,则n0=n2+1;（度为0的结点比度为2的结点个数多一个）  
**推广：**![在这里插入图片描述][20200506170732624.png]

**性质4：** 具有n个结点的完全二叉树的深度为：\[以2为底n的对数\]+1。  
**性质5** 如果对一棵有n个结点的完全二叉树的结点按层序编号（每层从左到右），则对任意结点i(1<=i<=n)有：  
（1）如果i=1,则结点i是二叉树的根，无双亲；如果i>1,其双亲PARENT(I)是结点\[i/2\];  
(2)如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(I)是结点2i；  
（3）如果2i+1>n,则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。

## 三、满二叉树和完全二叉树 ##

**1、满二叉树：** 深度为k且含有2^k-1个结点的二叉树  
形如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]  
**满二叉树的特点：**  
每一层上的结点数都是最大的结点数，，即每一层i的结点数都具有最大值2^(i-1)。所有叶子结点都在最大层上。

**2、完全二叉树：** 深度为k的，有n个结点的二叉树，当且仅当其每一个结点深度都与深度为k的满二叉树中编号从1至n的结点一一对应，称之为完全二叉树  
形如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]  
**完全二叉树的特点：**  
（1）叶子结点只可能在层次最大的两层上出现；  
（2）对任一结点，若其右分支下的子孙最大层次为 l，则其左分支下的子孙最大层次必为 l 或者 l+1。

## 四、二叉树的存储结构 ##

**1、顺序存储结构**

#define MAXTSIZE 100
    typedef TElemType SqBiTree[MAXTSIZE];
    SqBiTree bt;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]  
由上图可知，顺序存储结构存在存储空间浪费，因此顺序存储结构仅适用于完全二叉树，对于一般的二叉树，更适合采用链式存储结构  
**2、链式存储结构**

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

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

## 五、创建二叉树（先序遍历的顺序） ##

BiTree CreateBiTree()
    {
        
    	BiTree T;
    	char ch;
    	if ((ch = getchar()) == '#')T = NULL;
    	else
    	{
        
    		T = (BiTNode*)malloc(sizeof(BiTNode));
    		T->data = ch;
    		T->lchild = CreateBiTree();
    		T->rchild = CreateBiTree();
    	}
    	return T;
    }

[20200506170732624.png]: /images/20230528/535d62bd243a4d6abf9b460f2bf77672.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70]: /images/20230528/bc227eddd05841fd81cd199ff5db570d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 1]: /images/20230528/856ee9ffd59d40b3a2f9eda7360a76e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 2]: /images/20230528/750f0024ae8941c68a2ba60748750e79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dldHNfcw_size_16_color_FFFFFF_t_70 3]: /images/20230528/6c98ea770f9a490a96c6ff85475c8fe8.png