一、概念
1.1 树的定义
树是 n (n ≥ 0)个结点的有限集。n=0时称为空树。
在任意一棵非空树中:(1)有且仅有一个特定的成为根(Root)的结点;(2)当 n > 1 时,其余结点可分为m(m > 0)个互不相交的有限集 T1、 T2、…… Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree),如下图所示:
子树如下图所示:
1.2 树的其他特性
- 度(Degree):结点拥有的子树数成为结点的度。
- 度为0的结点成为叶子结点(Leaf)或终端结点
- 度不为0的结点成为非终端结点或分枝结点。
- 层次(Level):指从根开始定义起,结点所在的楼层。(按照根结点为1开始依次算起)
- 深度(Depth):树中结点的最大层次成为树的深度或高度。
- 子结点、双亲结点:结点的子树的根成为该结点的孩子(Child),相应地,该结点成为孩子的双亲结点(Parent)
1.3 二叉树的定义
二叉树(Binary Tree) 是 n (n ≥ 0)个结点的有限集合,该集合或为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
因为二叉树最多只能由左结点和右结点,一个普遍的二叉树如图
1.4 二叉树的基本特点
1.4.1 特点
- 每个结点最多有两棵子树,所以二叉树中不存在度大于2度结点。
- 左子树和右子树顺序不可颠倒。
- 即使树中某结点只有一棵子树,也要区分他是左子树还是右子树。
1.4.2 基本形态
- 空二叉树
- 只有一个根结点
- 根结点只有左子树
- 根结点只有右子树
- 根结点既有左子树也有右子树
1.5 特殊的二叉树
1.5.1 斜树
顾名思义,所有的结点都只有左子树或右子树。所有结点只有左子树的叫左斜树,只有右子树的成为右斜树,两者统称为斜树。
1.5.2 满二叉树
在一棵树中,如果所有的分支结点都存在左子树和右子树,并且所有的叶子都在同一层上,这样的二叉树称为满二叉树。
1.5.3 完全二叉树
对一颗具有n个结点的二叉树按层序编号,如果编号为i(1≤ i ≤ n)的结点与同样深度的满二叉树中编号为i 的结点在二叉树中的位置完全相同,这棵二叉树称为完全二叉树。
如下图所示,完全二叉树并不要求所有子结点全部填满,只需要子树树按顺序排列。
换句通俗的话说,哥哥一家没生满二胎,弟弟一家不允许要孩子……🐶,否则就不是完全二叉树。
如下图中,11节点丢失的情况下,不可以称为完全二叉树
二、二叉树的存储结构
2.1 顺序存储结构
通常用数组来存储二叉树,先看看存储完全二叉树的情况
可以看到,二叉树中的元素按照顺序依次放入开辟好的数组内存空间里。
但是,凡事都有但是,在某些极端情况下,某一棵树,缺胳膊少腿儿,导致空间大大浪费,比如下图:
这棵树只有4个有效的结点,但是却不得不开辟从A~M一共13个结点的内存空间,这种情况的树,使用数组结构来存储,对内存空间是一种浪费。
2.2 二叉链表
鉴于上文中数组结构无法更高效的表述二叉树,引入了链表的结构进行表述。
由于二叉树结构最多有两个孩子,所以引入的链表结点,结构分别为数据域、左孩子指针、右孩子指针
结点结构如下
左孩子 | 数据 | 右孩子 |
---|---|---|
lChild | data | rChild |
用代码来表述可以是这样的
struct BiTreeNode{
int data;
BiTreeNode *lChild;
BITreeNode *rChild;
}BiTreeNode, *BiTree
把上文中较特殊的二叉树,用这样的结点表述的二叉树结构如下:
三、二叉树的遍历
二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。
二叉树的遍历方法,主要有四种:
3.1 前序遍历
遍历的规则是若二叉树为空,空操作返回;否则先访问根结点,然后前序遍历左子树,再前序遍历右子树
如图示:
3.2 中序遍历
遍历的规则是若二叉树为空,空操作返回;否则从根结点开始(但此时并不遍历根结点),先前序遍历左子树,先遍历访问根结点,再前序遍历右子树。
如图示:
3.3 后序遍历
遍历的规则是若二叉树为空,空操作返回;否则从左到右先叶子后结点的方式遍历访问左右子树,最后访问根结点。
如图示
3.4 层序遍历
遍历的规则是若二叉树为空,空操作返回;否则从树的第一层——也就是根结点开始访问,从上往下,在同一层时从左至右对结点逐个访问。
访问顺序如图示:
三、顺序存储下的实现
3.1 顺序存储的实现
3.1.1 二叉树基本操作
初始化环境
创建结点结构
typedef struct { int level; //结点层 int order; //本层的序号(按照满二叉树给定序号规则) }Position;
以及其他辅助条件
#define MAXSIZE 100 /* 存储空间初始分配量 */ #define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef int CElemType; /* 树结点的数据类型,目前暂定为整型 */ typedef CElemType SqBiTree[MAX_TREE_SIZE]; /* 0号单元存储根结点 */ CElemType Nil = 0; /*设整型以0为空 或者以 INT_MAX(65535)*/
初始化一个二叉树T
Status InitBiTree(SqBiTree T){ for (int i = 0; i < MAX_TREE_SIZE; i++) { //将二叉树初始化值置空 T[i] = Nil; } return OK; }
创建二叉树(放入数据)
Status CreateBiTree(SqBiTree T){ int i = 0; //printf("按层序输入结点的值(整型),0表示空结点, 输入999结束.结点数<=%d\n",MAX_TREE_SIZE); /* 1 -->1 2 3 -->2 4 5 6 7 -->3 8 9 10 -->4 1 2 3 4 5 6 7 8 9 10 Nil Nil Nil */ while (i < 10) { T[i] = i+1; printf("%d ",T[i]); //结点不为空,且无双亲结点 if (i != 0 && T[(i+1)/2-1] == Nil && T[i] != Nil) { printf("出现无双亲的非根结点%d\n",T[i]); exit(ERROR); } i++; } //将空赋值给T的后面的结点 while (i < MAX_TREE_SIZE) { T[i] = Nil; i++; } return OK; }
清空二叉树
清空一棵二叉树,与构造一棵二傻树一样,只需将每个结点值置空即可。
可以直接定义一个新函数,将两个函数对等。
#define ClearBiTree InitBiTree
判断二叉树是否为空
只需判断根结点是否为空
Status BiTreeEmpty(SqBiTree T){ //根结点为空,则二叉树为空 return T[0] == Nil; }
获取二叉树的深度
计算深度,需要看从当前结点,到根结点经历的路径条数
int BiTreeDepth(SqBiTree T){ int j = -1; int i; //找到最后一个结点 //MAX_TREE_SIZE -> 100 -> 10 目的找到最后一个结点10的位置 for (i = MAX_TREE_SIZE-1 ; i>=0; i--) { if (T[i] != Nil) break; } do { j++; } while ( powl(2, j) <= i); //计算2的次幂 return j; }
3.1.2 结点操作
获取二叉树根结点的值
只需计算数组T 首结点的值即可
Status Root(SqBiTree T,CElemType *e){ if (BiTreeEmpty(T)) { return ERROR; } *e = T[0]; return OK; }
返回结点位置为e 的值
CElemType Value(SqBiTree T,Position e){ /* Position.level -> 结点层.表示第几层; Position.order -> 本层的序号(按照满二叉树给定序号规则) */ //pow(2,e.level-1) 找到层序 printf("%d\n",(int)pow(2,e.level-1)); //e.order printf("%d\n",e.order); //4+2-2; return T[(int)pow(2, e.level-1)+e.order-2]; }
修改结点位置e 的值
Status Assign(SqBiTree T,Position e,CElemType value){ //找到当前e在数组中的具体位置索引 int i = (int)powl(2, e.level-1)+e.order -2; //叶子结点的双亲为空 if (value != Nil && T[(i+1)/2-1] == Nil) { return ERROR; } //给双亲赋空值但是有叶子结点 if (value == Nil && (T[i*2+1] != Nil || T[i*2+2] != Nil)) { return ERROR; } T[i] = value; return OK; }
获取结点位置e 的双亲
CElemType Parent(SqBiTree T, CElemType e){ //空树 if (T[0] == Nil) { return Nil; } for (int i = 1 ; i < MAX_TREE_SIZE; i++) { //找到e if (T[i] == e) { return T[(i+1)/2 - 1]; } } //没有找到 return Nil; }
获取某结点的左孩子
步骤为当前结点的
CElemType LeftChild(SqBiTree T,CElemType e){ //空树 if (T[0] == Nil) { return Nil; } for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) { //找到e if (T[i] == e) { return T[i*2+1]; } } //没有找到 return Nil; }
获取某结点的右孩子
CElemType RightChild(SqBiTree T,CElemType e){ //空树 if (T[0] == Nil) { return Nil; } for (int i = 0 ; i < MAX_TREE_SIZE-1; i++) { //找到e if (T[i] == e) { return T[i*2+2]; } } //没有找到 return Nil; }
获取某结点的左兄弟
CElemType LeftSibling(SqBiTree T,CElemType e) { /* 空树 */ if(T[0]==Nil) return Nil; for(int i=1;i<=MAX_TREE_SIZE-1;i++) /* 找到e且其序号为偶数(是右孩子) */ if(T[i]==e&&i%2==0) return T[i-1]; return Nil; /* 没找到e */ }
获取某结点的右兄弟
CElemType RightSibling(SqBiTree T,CElemType e) { /* 空树 */ if(T[0]==Nil) return Nil; for(int i=1;i<=MAX_TREE_SIZE-1;i++) /* 找到e且其序号为奇数(是左孩子) */ if(T[i]==e&&i%2==1) return T[i+1]; return Nil; /* 没找到e */ }
3.1.3 遍历二叉树
前序遍历
void PreTraverse(SqBiTree T,int e){ //打印结点数据 visit(T[e]); //先序遍历左子树 if (T[2 * e + 1] != Nil) { PreTraverse(T, 2*e+1); } //最后先序遍历右子树 if (T[2 * e + 2] != Nil) { PreTraverse(T, 2*e+2); } } Status PreOrderTraverse(SqBiTree T){ //树不为空 if (!BiTreeEmpty(T)) { PreTraverse(T, 0); } printf("\n"); return OK; }
中序遍历
void InTraverse(SqBiTree T, int e){ /* 左子树不空 */ if (T[2*e+1] != Nil) InTraverse(T, 2*e+1); visit(T[e]); /* 右子树不空 */ if (T[2*e+2] != Nil) InTraverse(T, 2*e+2); } Status InOrderTraverse(SqBiTree T){ /* 树不空 */ if (!BiTreeEmpty(T)) { InTraverse(T, 0); } printf("\n"); return OK; }
后序遍历
void PostTraverse(SqBiTree T,int e) { /* 左子树不空 */ if(T[2*e+1]!=Nil) PostTraverse(T,2*e+1); /* 右子树不空 */ if(T[2*e+2]!=Nil) PostTraverse(T,2*e+2); visit(T[e]); } Status PostOrderTraverse(SqBiTree T) { if(!BiTreeEmpty(T)) /* 树不空 */ PostTraverse(T,0); printf("\n"); return OK; }
层序遍历
void LevelOrderTraverse(SqBiTree T){ int i = MAX_TREE_SIZE-1; //找到最后一个非空结点的序号 while (T[i] == Nil) i--; //从根结点起,按层序遍历二叉树 for (int j = 0; j <= i; j++) //只遍历非空结点 if (T[j] != Nil) visit(T[j]); printf("\n"); }
3.2 链式存储的实现
3.2.1 二叉树的基本操作
数据类型及结点结构如下:
typedef char CElemType; CElemType Nil=' '; /* 字符型以空格符为空 */ typedef struct BiTNode /* 结点结构 */ { CElemType data; /* 结点数据 */ struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ }BiTNode,*BiTree;
初始化二叉树
只需对当前二叉树赋值为空即可。
Status InitBiTree(BiTree *T) { *T=NULL; return OK; }
创建二叉树
void CreateBiTree(BiTree *T){ CElemType ch; //获取字符 ch = str[indexs++]; //判断当前字符是否为'#' if (ch == '#') { *T = NULL; }else { //创建新的结点 *T = (BiTree)malloc(sizeof(BiTNode)); //是否创建成功 if (!*T) { exit(OVERFLOW); } /* 生成根结点 */ (*T)->data = ch; /* 构造左子树 */ CreateBiTree(&(*T)->lchild); /* 构造右子树 */ CreateBiTree(&(*T)->rchild); } }
清空二叉树
这里的逻辑与数组存储树一样的,逻辑等于初始化二叉树,用新函数来等同于它。
#define ClearBiTree DestroyBiTree
销毁二叉树
void DestroyBiTree(BiTree *T) { if(*T) { /* 有左孩子 */ if((*T)->lchild) DestroyBiTree(&(*T)->lchild); /* 销毁左孩子子树 */ /* 有右孩子 */ if((*T)->rchild) DestroyBiTree(&(*T)->rchild); /* 销毁右孩子子树 */ free(*T); /* 释放根结点 */ *T=NULL; /* 空指针赋0 */ } }
判断二叉树是否为空
Status BiTreeEmpty(BiTree T) { if(T) return FALSE; else return TRUE; }
获取二叉树的深度
int BiTreeDepth(BiTree T){ int i,j; if(!T) return 0; //计算左孩子的深度 if(T->lchild) i=BiTreeDepth(T->lchild); else i=0; //计算右孩子的深度 if(T->rchild) j=BiTreeDepth(T->rchild); else j=0; //比较i和j return i>j?i+1:j+1; }
3.2.2 结点操作
获取二叉树根结点的值
CElemType Root(BiTree T){ if (BiTreeEmpty(T)) return Nil; return T->data; }
获取指针p 指向的结点的值
CElemType Value(BiTree p){ return p->data; }
给p 指向的结点赋值
void Assign(BiTree p,CElemType value) { p->data=value; }
3.2.3 遍历操作
前序遍历
void PreOrderTraverse(BiTree T) { if(T==NULL) return; printf("%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */ PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */ PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */ }
中序遍历
void InOrderTraverse(BiTree T) { if(T==NULL) return ; InOrderTraverse(T->lchild); /* 中序遍历左子树 */ printf("%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */ InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */ }
后序遍历
void PostOrderTraverse(BiTree T) { if(T==NULL) return; PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */ PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */ printf("%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */ }