文章目录
- 树
- 1 树的基本概念
- 1.1 树的定义
- 1.2 基本术语
- 1.3 数的性质
- 2 二叉树的概念
- 2.1 二叉树的定义与特性
- 2.1.1 定义
- 2.1.2 二叉树的性质
- 2.2 几种特殊的二叉树
- 2.2.1 满二叉树
- 2.2.2 完全二叉树
- 2.3 二叉树的存储结构
- 2.3.1 顺序存储
- 2.3.2 链式存储
- 3 二叉树的遍历和线索二叉树
- 3.1 二叉树的遍历
- 3.1.1 先序遍历（根左右）
- 3.1.2 中序遍历（左根右）
- 3.1.3 后续遍历（左右根）
- 3.1.4 二叉树的层次遍历
- 3.1.5 由遍历序列构造二叉树
- 3.2 线索二叉树
树
1 树的基本概念
1.1 树的定义
树是n（n>=0）个结点的有限集，树除了根节点外，任何一个结点都有且仅有一个前驱
- 空树：结点数为0的树
- 非空树的特性：
- 有且仅有一个根节点
- 没有后继的结点称为“叶子结点”（或终端结点）
- 有后继的结点称为“分支结点”（或非终端结点）
- 子树：在互不相交的有限集合中，每个集合本身又是一棵树，称为根结点的子树（如上图A有三颗子树B、C、D）
1.2 基本术语
- 结点之间的关系描述
- 祖先、子孙、双亲、兄弟…结点
- 路径、路径长度
- 结点、树的属性描述
- 结点的层次（深度）——从上往下
- 结点的高度——从下往上
- 树的高度——总共多少层
- 结点的度——有几个孩子
- 树的度——各结点的度的最大值
- 有序树、无序树
- 森林：是m（m>=0）棵互不相交的树的集合
1.3 数的性质
- 树中的结点数等于所有结点的度数之和加1。
- 度为m的树第i层上至多有m^i-1个结点
- 度为m的数、m叉数的区别
2 二叉树的概念
2.1 二叉树的定义与特性
2.1.1 定义
二叉树是n(n>=0)个结点的有限集，它或者是空集（n=0），或者由一个根结点及两颗互不相交的分别称作这个根的左子树和右子树的二叉树组成。
特点：1.每个结点最多有俩孩子（二叉树中不存在度大于2的结点）。
2. 二叉树可以是空集合，根可以有空的左子树和空的右子树。
3. 二叉树有左右之分，次序不能颠倒。
2.1.2 二叉树的性质
- 在二叉树的第i层上至多有2^（i-1）个结点（i>1）。
- 深度为k的二叉树至多有2^k-1个结点（k>=1）。
- 对任何一颗二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1.
- 具有n个结点的完全二叉树的深度为(log2N)+1。
- 如果对一棵有n个结点的完全二叉树（深度为log2n+1）的结点按层序编号（从第1层到第log2n+1层，每层从左到右），则对任一结点i(1<=i<=n)，有：
- 如果i=1，则结点i是二叉树的根，无双亲；
如果i>1，则其双亲是结点i/2.- 如果2i>n，则结点i为叶子结点，无左孩子；
否则，其左孩子是结点2i。- 如果2i+1>n，则结点i无右孩子;
否则，其右孩子是结点2i+1。
注意：二叉树不是树的特殊情况，它们是两个概念。
2.2 几种特殊的二叉树
2.2.1 满二叉树
一颗深度为k且有2^k-1个结点的二叉树称为满二叉树。每一层上的结点数都达到最大。叶子全部在最低层。
特点：1. 只有最后一层有叶子结点
2. 不存在度为1的结点
3. 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父亲结点为i/2（如果有的话）
2.2.2 完全二叉树
深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一 一对应时，称之为完全二叉树。
特点：1. 只有最后两层可能有叶子结点
2. 最多只有一个度为1的结点
3. 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父亲结点为i/2（如果有的话）
4. i<=n/2为分支结点，i>n/2为叶子结点
- 二叉排序树
- 平衡二叉树
2.3 二叉树的存储结构
2.3.1 顺序存储
二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来；
#define MaxSize 100struct TreeNode{ElemType value; //结点中的数据元素bool isEmpty; //结点是否为空
}main(){TreeNode t[MaxSize];for (int i=0; i<MaxSize; i++){t[i].isEmpty = true;}
}
2.3.2 链式存储
//二叉树的结点
struct ElemType{int value;
};typedef struct BiTnode{ElemType data; //数据域struct BiTNode *lchild, *rchild; //左、右孩子指针
}BiTNode, *BiTree;//定义一棵空树
BiTree root = NULL;//插入根节点
root = (BiTree) malloc (sizeof(BiTNode));
root -> data = {1};
root -> lchild = NULL;
root -> rchild = NULL;//插入新结点
BiTNode *p = (BiTree) malloc (sizeof(BiTNode));
p -> data = {2};
p -> lchild = NULL;
p -> rchild = NULL;
root -> lchild = p; //作为根节点的左孩子
3 二叉树的遍历和线索二叉树
3.1 二叉树的遍历
3.1.1 先序遍历（根左右）
- 若二叉树为空，不用操作
- 若二叉树非空：
- 访问根节点
- 先序遍历左子树
- 先序遍历右子树
typedef struct BiTnode{ElemType data; struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;void PreOrder(BiTree T){if(T!=NULL){visit(T); //访问根结点PreOrder(T->lchild); //递归遍历左子树PreOrder(T->rchild); //递归遍历右子树}
}
3.1.2 中序遍历（左根右）
- 若二叉树为空，不用操作
- 若二叉树非空：
- 先序遍历左子树
- 访问根节点
- 先序遍历右子树
typedef struct BiTnode{ElemType data; struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;void InOrder(BiTree T){if(T!=NULL){InOrder(T->lchild); //递归遍历左子树visit(T); //访问根结点InOrder(T->rchild); //递归遍历右子树}
}
3.1.3 后续遍历（左右根）
- 若二叉树为空，不用操作
- 若二叉树非空：
- 先序遍历左子树
- 先序遍历右子树
- 访问根节点
typedef struct BiTnode{ElemType data; struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;void PostOrder(BiTree T){if(T!=NULL){PostOrder(T->lchild); //递归遍历左子树 PostOrder(T->rchild); //递归遍历右子树visit(T); //访问根结点}
}
3.1.4 二叉树的层次遍历
算法思想
- 初始化一个辅助队列
- 根节点入队
- 若队列非空，则队头结点出队，访问该结点，依次将其左、右孩子插入队尾（如果有的话）
- 重复以上操作直至队列为空
//二叉树的结点(链式存储)
typedef struct BiTnode{ElemType data; struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;//链式队列结点
typedef struct LinkNode{BiTNode * data;typedef LinkNode *next;
}LinkNode;typedef struct{LinkNode *front, *rear;
}LinkQueue;//层序遍历
void LevelOrder(BiTree T){LinkQueue Q;InitQueue (Q); //初始化辅助队列BiTree p;EnQueue(Q,T); //将根节点入队while(!isEmpty(Q)){ //队列不空则循环DeQueue(Q,p); //队头结点出队visit(p); //访问出队结点if(p->lchild != NULL)EnQueue(Q,p->lchild); //左孩子入队if(p->rchild != NULL)EnQueue(Q,p->rchild); //右孩子入队}
}
3.1.5 由遍历序列构造二叉树
- 先序序列 + 中序序列
- 后序序列 + 中序序列
- 层序序列 + 中序序列
key: 找到树的根节点，并根据中序序列划分左右子树，再找到左右子树根节点
3.2 线索二叉树
- 线索二叉树的概念与作用
在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
