树与二叉树
树的定义
- 树是n个结点的有限集合
- 若n等于0，称为空树
- 若n>0，满足一下条件
- 有且仅有一个根（root）
- 其余结点可分为m个互不相交的有限集T1，T2……，其中每一个集合本身又是一棵树，称为根的子树。
树的基本术语
- 根结点：没有前驱的结点
- 结点的度：结点拥有的子树
- 树的度：树内各节点度的最大值
- 度为0的结点称为叶子结点或者终端结点
- 度不等于0,为分支结点。
- 分支结点中除了根结点外其他结点称为内部结点
- 结点子的树的根称为该结点孩子，该结点称为孩子的双亲
- 拥有共同双亲结点的，称为兄弟结点
- 在同一层次上，双亲不同的结点称为堂兄弟
- 结点的祖先：从根到该结点所经分支上的所有结点
- 结点的子孙：从某结点为根的子树中任一结点
- 树的深度：树中节点的最大层次
- 有序树：树中节点的子树从左到右有次序
- 无序树：树中节点各子树无次序
- 森林：m棵树互不相交的树的集合
二叉树的定义
- 每个结点最多有俩个孩子
- 子树有左右之分，期中次序不能颠倒
- 二叉树可以是空集合
二叉树的性质
- 第i层上最多有2^（i-1）个结点
- 深度为k为二叉树最多有2^k - 1个结点
- 叶子数n0 度为2 的结点为n2 ，则 n0 = n2 + 1（分支的个数角度考虑）
满二叉树：深度为k且有2^ - 1 个结点的二叉树
特点
- 每一层结点数都达到最大
- 叶子结点全部在最底层
- 每一位置都有元素
完全二叉树
定义：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1 ~n的节点一一对应
特点：
- 叶子结点只能分布在层次最大的俩层上
- 对任一结点，如果其右子树的最大层次为i，则其左子树最大层次最大层次必为 i 或者 i + 1
性质
- 具有n个结点的完全二叉树的深度为[log?n] + 1
- 如果结点i > 1 ,则双亲结点为[i / 2]
- 若2i > n ，则为叶子结点，否则左孩子结点为2i
- 若2i + 1 > n ，则无右孩子，否则右孩子结点为2i + 1
顺序存储
实现：按照满二叉树的结点层次编号，依次存放二叉树中的数据元素
链式存储
二叉链表的结点形式
typedef struct node
{
int data;
struct node *lchild , *rchild;
}Node , * BiTree;
二叉链表存储特点：n个结点的二叉链表，有n+1个空指针域
三叉链表
typedef struct node
{
int data;
struct node *lchild , *rchild , *father;
}Node , * BiTree;
遍历二叉树
递归前序遍历
void PreTraversal (BiTree t){
if (t == NULL) return;
printf("%c ",t->data);
PreTraversal(t->lchild);
PreTraversal(t->rchild);
}
非递归前序遍历
用栈来实现二叉树的前序遍历
void PreTraversal (BiTree t){
stack<BiTree>temp;
while (t || temp.size()){
if (t){
printf("%c ",t->data);
temp.push(t);
t = t->lchild;
}
else{
t = temp.top();
temp.pop();
t = t->rchild;
}
}
}
递归实现中序遍历
void MidTraversal (BiTree T){
if (!T) return;
MidTraversal(T->lchild);
printf("%c ",T->data);
MidTraversal(T->rchild);
}
非递归实现中序遍历
void MidTraversal(BiTree t){
stack<BiTree>temp;
//if (t == NULL) return;
while (t || temp.size()){
if (t) {
temp.push(t);
t = t->lchild;
}
else {
t = temp.top();
temp.pop();
printf("%c",t->data);
t = t->rchild;
}
}
}
递归实现后序遍历
特点：遵循 右子树 -> 根结点 ->左子树 的遍历顺序
递归实现后序遍历
void PostTraversal (Bitree T){
if (!T);
PostTraversal(T->lchild);
PostTraversal(T->rchild);
printf("%c",T->data);
}
非递归后序遍历二叉树
二叉树的层次遍历
二叉树实现层次遍历，与bfs（宽度优先搜索）的思路是一致的。用队列来实现功能。
void LevTraversal(BiTree t){
queue<BiTree>q;
BiTree f;
q.push(t);
while (q.size()){
f = q.front();
q.pop();
printf("%c ",f->data);
if (f->lchild) q.push(f->lchild);
if (f->rchild) q.push(f->rchild);
}
}
建立二叉树
前序递归建立
void CreateBitree (BiTree * T){
char ch ;
scanf("%c",&ch);
if (ch == '.'){
*T = NULL;
}
else {
*T = (BiTree)malloc(sizeof(Node));
(*T)->data = ch;
(*T)->lchild = NULL;
(*T)->rchild = NULL;
CreateBitree(&((*T)->lchild));
CreateBitree(&((*T)->rchild));
}
return ;
}
- 建立二叉树的思路与遍历二叉树的思路是相同的
- 特别要注意的是，二叉树有多少指针域，只有将指针域全部赋值完后，递归才会结束，因为我们建立的是拓展二叉树，所以指针域都需要赋值
二叉树的复制
int CopyTree(BiTree t , BiTree *newT){
if (!t) return 0;
*newT = (BiTree)malloc(sizeof(Node));
(*newT)->data = t->data;
CopyTree(t->lchild ,(&(*newT)->lchild));
CopyTree(t->rchild,(&(*newT)->rchild));
}
树的深度的计算
基本思路是分别计算左右子树的深度，返回较大的深度。因为二叉树具有递归的结构，所以说用递归来计算深度
int TreeDeep(BiTree t){
int n ,m;
if (!t) return 0;
m = TreeDeep(t->lchild);
n = TreeDeep(t->rchild);
if (n > m) return n + 1;
else return m + 1;
}
树的结点数的计算
int nodeNumber(BiTree t){
if (!t) return 0;
return nodeNumber(t->lchild) + nodeNumber(t->rchild) + 1;
}
计算叶子结点数
int leafNode (BiTree t){
if (!t) return 0;
else if (t->lchild == NULL && t->rchild == NULL) return 1;
else return leafNode(t->lchild) + leafNode(t->rchild);
}
return nodeNumber(t->lchild) + nodeNumber(t->rchild) + 1;
}
##### 计算叶子结点数
int leafNode (BiTree t){
if (!t) return 0;
else if (t->lchild == NULL && t->rchild == NULL) return 1;
else return leafNode(t->lchild) + leafNode(t->rchild);
}
|