树和二叉树的概念与介绍

树和二叉树的概念与介绍

树

树的概念

• 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个结有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树 。
• 树是一种非线性结构，它与线性结构是不相同的，线性结构具有一对一的特性，元素具有唯一的前驱以及唯一的后继(除了第一个结点以及最后一个结点外),树的这种非线性结构，使得其具有一对多的结构特性
• 树的结点时有限的，每个结点具有0个或者多个子节点
• 根节点时没有父亲结点的
• 树是一个有层次的集合，树同时也是递归定义的
• 树不可以相交，也就是说集合和集合之间是不可以相交的。
  

名词概念

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
• 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点
• 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点
• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
• 森林：由m（m>=0）棵互不相交的树的集合称为森林；
  

树的表示方法(树的表示方法一共有三种)

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

树的双亲表示法、孩子表示法和孩子兄弟表示法

• 双亲表示法—取一块连续的内存空间，在存储每个结点的同时，各自都附加一个记录其父结点位置的变量。
• 在树结构中，除了树根外，每个结点都只有一个父结点（又叫“双亲结点”）。

#define tree_size 100　　//宏定义树中结点的最大数量
#define TElemType int　　//宏定义树结构中数据类型
typedef struct PTNode{
　　TElemType data;　　//树中结点的数据类型
　　int parent;　　　　 //结点的父结点在数组中的位置下标
}PTNode;
typedef struct {
　　PTNode nodes[tree_size];　　//存放树中所有结点
　　int r, n;　　//根的位置下标和结点数
}PTree;

• 孩子表示法—将树中的每个结点的孩子结点排列成一个线性表，用链表存储起来。对于含有 n 个结点的树来说，就会有 n 个单链表，将 n 个单链表的头指针存储在一个线性表中，这样的表示方法就是孩子表示法(如果结点没有孩子（例如叶子结点），那么它的单链表为空表。)

#define TElemType int
#define Tree_Size 100
//孩子表示法
typedef struct CTNode{
　　int child;　　//链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标
　　struct CTNode *next;
}*ChildPtr;
typedef struct {
　　TElemType data;　　//结点的数据类型
　　ChildPtr firstchild;　　//孩子链表的头指针
}CTBox;
typedef struct{
　　CTBox nodes[Tree_Size];　　//存储结点的数组
　　int n, r;　　//结点数量和树根的位置
}CTree;

• 孩子兄弟表示法—使用链式存储结构存储普通树。链表中每个结点由 3 部分组成：
  

#define ElemType int
typedef struct CSNode
{
　　ElemType data;
　　struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

• 通过孩子兄弟表示法，普通树转化为了二叉树，所以孩子兄弟表示法又被称为“二叉树表示法”或者“二叉链表表示法”。
  

树在实际中的应用

• 最简单直接来说，其实就是目录结构
• 下为Linux下的目录结构
  

二叉树

二叉树的概念

• 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
• 空树也是二叉树
  

二叉树的特点

1. 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，其子树的次序不能颠倒。
   
   

两个比较特殊的二叉树(满二叉树和完全二叉树)

• 满二叉树—每一层结点的个数都达到了最大值
  
  
  满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
  说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
• 完全二叉树
  
  
  完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。
  对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
  

完全二叉树和满二叉树的关系

• 满二叉树是一个特殊的完全二叉树，但是完全二叉树不一定是满二叉树
  

二叉树的性质

树的存储方式

顺序存储：

• 顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
  
• 完全二叉树按照下面的顺序存储的存储方式是完全没有任何问题的
  
  
• 但是，对于普通的二叉树来说，如果还是按照顺序存储的存储方式来进行存储的话，就会出现一些错误了，就像下面这样，往回还原的时候就会有错误
  
• 如果仍然想使用顺序存储的存储方式来进行存储的话，可以使用下面的方式来进行修改，其实就是把普通的二叉树补成完全二叉树，就可以还原回去了
  
  
• 上面的这种修改方式对于结点不是很多的二叉树来说，是可以的，但是如果结点的个数很多，或者说这是一棵单支树的话，仍然使用顺序存储的存储方式就会显得有些浪费空间了。对于下面的右单支来说，空余的空间就太多了，所以空间利用率太低了
  
• 所以顺序结构的存储方式还是比较适用于完全二叉树以及满二叉树的存储，不适用于普通的二叉树的存储，普通的二叉树适用于链式存储的存储方式。

链式存储