树 和 二叉树
1.树的概念
树 tree
是n(n>=0)个节点的有限集
在任意的一个非空树中
(1)有且仅有一个特定的被称为 根(root) 的节点
(2)当n>1时, 其余的节点可分为m(m>0)个互不相交的有限集T1, T2, T3, ....
其中每一个集合本身又是一棵树, 并且称为 根的子树 (Subtree)
树的节点
包含一个数据元素 以及 若干个指向子树的分支(保存的关系)
节点的度 degree
节点拥有子树的个数 称为 节点的度
度为0的节点, 称为 叶子节点 或者 终端节点
度不为0的节点, 称为 分支节点 或者 非终端节点
节点的层次 level
从 根 开始定义起的, 根为第一层, 根的子树为第二层, 以此类推 ...
树中节点最大层次 称为 树的高度 或者 深度 depth
2.二叉树 Binary
1)二叉树
是一种树形结构, 它的特点是 每一个节点至多有两个子树
(即二叉树中不存在 度大于2 的节点)
并且, 二叉树的子树有左右之分的, 其次序是不能颠倒
2)二叉树的5种形态 (见图示)
(1)空树
(2)只有一个根节点(没有子节点)
(3)只有一个左子节点
(4)只有一个右子节点
(5)有左右两个子节点
☆☆☆
3)二叉树的性质
(1)在二叉树中, 第i层 至多有 2^(i-1) 个节点 (i>=1)
证明: 数学归纳法
当 n == 1 时, 1
当 n == 2 时, 2
当 n == 3 时, 4
当 n == 4 时, 8
...
i ---> 2^(i-1)
(2)深度为k的二叉树中, 至多有 ( 2^k - 1 ) 个节点 (k>=1)
证明: 由性质(1)可得
1 + 2 + 4 + 8 + 16 + ... + 2^(k-1) = 2^k - 1
等比数列前n项和 : Sn = a1 * ( 1 - q^n ) / ( 1 - q )
(3)对于任意一颗二叉树中, 如果其 叶子节点(度为0的节点)的个数为 n0, 度为2的节点的个数为 n2,
则 n0 = n2 + 1
证明:
假设一个二叉树中的总的节点个数为N
度为0的节点个数为n0
度为1的节点个数为n1
度为2的节点个数为n2
N = n0 + n1 + n2 (I)
设这个二叉树的分支数为B
从下往上看, 每一个节点都有一个向上的分支(除了根节点没有)
B = N - 1 (II)
从上往下看, 一个节点如果有一个子节点,就会有一个向下的分支
如果有两个子节点,就会有2个向下的分支
如果没有子节点,就没有分支
B = 0 * n0 + 1 * n1 + 2 * n2
-->
B = n1 + 2 * n2 (III)
有(I)(II)(II)可得
B = N - 1
==> n1 + 2 * n2 = n0 + n1 + n2 - 1
==> n0 = n2 + 1
满二叉树:
一个深度为k 且 有 2^k - 1 个节点的二叉树, 称为 满二叉树
在不改变二叉树深度的情况下, 不能再额外的添加节点了
完全二叉树:
(1)除去最后一层, 为满二叉树
(2)最后一层的节点的排序, 要从左边开始(中间不能有空洞)
(4)如果对一个有n个节点的完全二叉树 从上至下,从左至右
给每一个节点进行编号, 从1开始编号
那么,如果一个节点的编号为i, 则
父节点的编号为 i/2
左子节点的编号为 2*i
右子节点的编号为 2*i + 1
证明:
假设编号为i的节点, 在第k层
那么第k层的第一个节点的编号为 2^(k-1)
i这个节点 距离它所在的层次的第一个节点 中间间隔多少个节点?
i - 2^(k-1)
i的子节点在第k+1层
左子节点的编号为 2^k + 2*( i - 2^(k-1) ) ==> 2*i
右子节点的编号为 2*i + 1
i的父节点在 第k-1层
父节点的编号为 2^(k-2) + ( i - 2^(k-1) )/2 ==> i/2
(5)具有n个节点的完全二叉树的深度为 log2(n)向下取整 +1
证明:
假设深度为k
2^(k-1) - 1 < n <= 2^k - 1
--> 2^(k-1) <= n < 2^k
3.二叉树的代码实现
如何保存二叉树的节点?
保存数据
保存数据之间的关系
对于数的节点来说, 父节点和子节点
1)顺序结构
用一组地址连续的空间 来保存二叉树 "数组"
如何去表示节点与节点之间的关系?
完全二叉树的性质, 如果一个节点的编号为i, 则
父节点的编号为 i/2
左子节点的编号为 2*i
右子节点的编号为 2*i + 1
用数组来保存一颗完全二叉树
#define MAX_LEN 1024
typedef int DataType; //数据的类型DataType SqBitree[MAX_LEN];
SqBitree[1] 保存根节点的数据
SqBitree[2] 保存编号为2的节点
SqBitree[3] 保存编号为3的节点
...
缺点:
数组的大小是固定的, 可能会造成空间的浪费,或者空间不足的情况
2)链式结构
用一组地址不连续的空间 来存储栈的一个二叉树
二叉树的节点:
数据域: 保存数据
指针域: 至少有两个, 保存左子和右子的指针
typedef int DataType; //数据的类型
typedef struct BitNode //二叉树节点的类型
{
DataType data; //数据域
struct BitNode * lchild; //指针域 , 左子节点的指针
struct BitNode * rchild; //右子节点的指针
} BitNode ;
☆☆☆
4.二叉树的遍历
如何按照某种搜索路径访问二叉树的每一个节点
使得每一个节点都能够被访问 且 仅访问一次
一般 左子节点的访问 在 右子节点的前面
根 左 右 : 先序遍历(先根遍历)
左 根 右 : 中序遍历
左 右 根 : 后序遍历
1)先序遍历(先根遍历)
(1)先访问根节点
(2)再按照先序遍历的方式去访问根的左子树
(3)再按照先序遍历的方式去访问根的右子树
F(t) --> F表示用先序遍历的方法, t表示这个二叉树的根节点
F(t) ==>
(1)判断这个树是否为空
(2)访问 根节点 printf
(3) F( t->lchild )
(4) F( t->rchild )
2)中序遍历
(1)先按照中序遍历的方式去访问根的左子树
(2)再访问根节点
(3)再按照中序遍历的方式去访问根的右子树
3)后序遍历
(1)先按照后序遍历的方式去访问根的左子树
(2)再按照后序遍历的方式去访问根的右子树
(3)最后访问根节点
练习:
1) 见图示
2) 已知一棵二叉树的先序和中序遍历,请画出这个树, 并写出其后序遍历
先序遍历: EBADCFHGIKJ
中序遍历: ABCDEFGHIJK
见图示
5.二叉排序树
二叉排序树具有以下的性质:
(1)如果它的左子树不为空, 则左子树上的所有节点的值 都是小于 根节点的值
(2)如果它的右子树不为空, 则右子树上的所有节点的值 都是大于 根节点的值
(3)它的左右子树 也分别是一棵二叉排序树
练习:
1)创建一个二叉排序树
实际上就是把一个节点加入到一个二叉排序树中,并保持其排序性
不断地 重复二叉排序树的插入操作
BinaryTree.c / BinaryTree.h
typedef char DataType; //数据的类型
typedef struct BitNode //二叉树节点的类型
{
DataType data; //数据域
struct BitNode * lchild; //指针域 , 左子节点的指针
struct BitNode * rchild; //右子节点的指针
} BitNode ;
//往一个二叉排序树中添加节点
//往一个二叉排序树中添加节点
BitNode * insert_node( BitNode *r , BitNode *pnew )
{
if( r == NULL ) //从无到有
{
return pnew;
}
//从少到多
//找到待插入的位置
BitNode * p = r; //遍历指针
while( 1 )
{
if( pnew->data > p->data ) //大于 往右
{
if( p->rchild == NULL ) //如果右子为空,那么就添加进来
{
p->rchild = pnew;
break;
}
p = p->rchild;
}
else if( pnew->data < p->data ) //小于 往左
{
if( p->lchild == NULL ) //如果左子为空, 那么就添加进来
{
p->lchild = pnew;
break;
}
p = p->lchild;
}
else
{
printf("data repetitive! \n");
break;
}
}
//返回根节点
return r;
}//创建一个二叉排序树
//创建一个二叉排序树
BitNode * create_sort_tree()
{
BitNode * r = NULL; //保存根节点的指针
//1.从键盘上获取输入的数据
char str[32] = {0};
scanf("%s", str );
int i = 0;
while( str[i] )
{
//2.创建一个新的数据节点空间, 并初始化
BitNode * pnew = (BitNode *)malloc( sizeof(BitNode) );
pnew->data = str[i];
pnew->lchild = NULL;
pnew->rchild = NULL;
//3.把新节点加入到二叉树中
r = insert_node( r , pnew );
i++;
}
//4.返回根节点
return r;
}2)用递归的方法, 实现二叉树的先序遍历\中序遍历\后序遍历
//先序遍历
void pre_order( BitNode * r )
{
if( r == NULL )
{
return ;
}
//(1)先访问根节点
printf("%c ", r->data );
//(2)再按照先序遍历的方式去访问根的左子树
pre_order( r->lchild );
//(3)再按照先序遍历的方式去访问根的右子树
pre_order( r->rchild );
}
//中序遍历
void mid_order( BitNode * r )
{
if( r == NULL )
{
return ;
}
//(1)先按照中序遍历的方式去访问根的左子树
mid_order( r->lchild );
//(2)再访问根节点
printf("%c ", r->data );
//(3)再按照中序遍历的方式去访问根的右子树
mid_order( r->rchild );
}
//后序遍历
void post_order( BitNode * r )
{
if( r == NULL )
{
return ;
}
//(1)先按照后序遍历的方式去访问根的左子树
post_order( r->lchild );
//(2)再按照后序遍历的方式去访问根的右子树
post_order( r->rchild );
//(3)最后访问根节点
printf("%c ", r->data );
}
3)求一棵二叉树的高度(深度)
//求一棵二叉树的高度(深度)
int TreeHeight( BitNode * t )
{
if( t == NULL )
{
return 0;
}
int l = TreeHeight( t->lchild );
int r = TreeHeight( t->rchild );
return l>r ? l+1 : r+1;
}4)删除二叉树中值为x的节点 (参考图示)
5)销毁一棵二叉树
//销毁一棵二叉树
void destroy_tree( BitNode * r )
{
while( r )
{
r = delete_node( r, r->data );
}
}6)层次遍历
//层次遍历
void level_order( BitNode * r )
{
if( r == NULL )
{
return ;
}
//1.初始化一个队列
CircleQueue *q = InitQueue();
//2.把根节点入队
EnQueue( q, r );
while( ! IsEmpty( q ) )
{
//3.出队, 访问
ElemType d; // BitNode * d;
DeQueue( q, &d );
printf("%c ", d->data );
//4.再把出队元素的左子和右子全部入队
if( d->lchild )
{
EnQueue( q, d->lchild );
}
if( d->rchild )
{
EnQueue( q, d->rchild );
}
}
putchar('\n');
//5.销毁队列
DestroyQueue( q );
}6.平衡二叉树
1)平衡二叉树 Balance Binary Tree (又称为 AVL树 )
它或者是一棵空树, 或者具有以下的性质:
它的左子树和右子树本身又是一棵平衡二叉树
且 左子树 和 右子树 的深度之差的绝对值不超过1
若平衡二叉树的节点的 平衡因子BF 的定义为
该节点的 左子树的深度 减去 右子树的深度
则 平衡二叉树上的所有节点的平衡因子的取值范围可能是 -1, 0, 1
只要有一个节点的平衡因子的绝对值大于1的,那么这棵树就是不平衡的
平衡二叉树 --> 平衡的二叉排序树 来实现
2)平衡操作
(1)单向右旋平衡处理 SingleRotateWithRight
在不平衡的节点的左子节点的左边新增一个节点
==>对不平衡的节点做 单向右旋平衡处理
AVLNode * SingleRotateWithRight( AVLNode *k2 )
{
AVLNode * k1 = k2->lchild;
//平衡处理
k2->lchild = k1->rchild;
k1->rchild = k2;
//更新树的深度
k2->h = MAX( Height(k2->lchild), Height(k2->rchild) ) + 1 ;
k1->h = MAX( Height(k1->lchild), Height(k1->rchild) ) + 1 ;
return k1;
} (2)单向左旋平衡处理 SingleRotateWithLeft
在不平衡的节点的右子节点的右边新增一个节点
==>对不平衡的节点做 单向左旋平衡处理
AVLNode * SingleRotateWithLeft( AVLNode *k2 )
{
AVLNode *k1 = k2->rchild;
//平衡处理
k2->rchild = k1->lchild;
k1->lchild = k2;
//更新树的深度
k2->h = MAX( Height(k2->lchild), Height(k2->rchild) ) + 1 ;
k1->h = MAX( Height(k1->lchild), Height(k1->rchild) ) + 1 ;
return k1;
} (3)双向旋转(先左后右)平衡处理 DoubleRotateLeftRight
在不平衡的节点的左子节点的右边新增一个节点
==> 先把 不平衡的节点的左子节点 做 单向左旋平衡处理
然后再对该 不平衡的节点 做 单向右旋平衡处理
AVLNode * DoubleRotateLeftRight( AVLNode * k3 )
{
k3->lchild = SingleRotateWithLeft( k3->lchild );
k3 = SingleRotateWithRight( k3 );
return k3;
}(4)双向旋转(先右后左)平衡处理 DoubleRotateRightLeft
在不平衡节点的右子节点的左边新增一个节点
==> 先把 不平衡的节点的右子节点 做 单向右旋平衡处理
然后再对该 不平衡的节点 做 单向左旋平衡处理
AVLNode * DoubleRotateRightLeft( AVLNode * k3 )
{
k3->rchild = SingleRotateWithRight( k3->rchild );
k3 = SingleRotateWithLeft( k3 );
return k3;
}
3)代码实现
typedef char DataType; //数据的类型
typedef struct AVLNode //平衡的二叉排序树的节点的数据类型
{
DataType data; //数据域: 保存数据
struct AVLNode * lchild; //指针域, 左子节点的指针
struct AVLNode * rchild; //右子节点的指针
int h; //保存树的深度
} AVLNode ;
练习:
1)创建一个平衡二叉排序树
其实就是把一个节点 加入到一个平衡二叉排序树中, 并保持其平衡性
AVL.c / AVL.h
//往一棵平衡二叉排序树t中 插入值为x的节点
AVLNode * insert_AVL_node( AVLNode *t, DataType x )
{
if( t == NULL ) //从无到有
{
//创建一个新节点, 并初始化
AVLNode *pnew = (AVLNode *)malloc( sizeof(AVLNode) );
pnew->data = x;
pnew->lchild = NULL;
pnew->rchild = NULL;
pnew->h = 1;
return pnew;
}
//从少到多
if( x > t->data ) //大于 往右
{
//大于, 把x插入到t的右子树中, 同时做平衡处理
t->rchild = insert_AVL_node( t->rchild, x );
//更新树的深度
t->h = MAX( Height( t->lchild ) , Height( t->rchild ) ) + 1 ;
//把x插入到右子树之后,如果不平衡, 需要做平衡处理
if( Height( t->rchild ) - Height( t->lchild ) > 1 )
{
if( x > t->rchild->data ) //右子树的右边
{
//单向左旋平衡处理
t = SingleRotateWithLeft( t );
}
else //右子树的左边
{
//双向旋转(先右后左)平衡处理
t = DoubleRotateRightLeft( t );
}
}
}
else if( x < t->data ) //小于 往左
{
//小于, 把x插入到t的左子树中, 同时做平衡处理
t->lchild = insert_AVL_node( t->lchild, x );
//更新树的深度
t->h = MAX( Height( t->lchild ) , Height( t->rchild ) ) + 1 ;
//把x插入到左子树之后, 如果不平衡, 需要做平衡处理
if( Height( t->lchild) - Height( t->rchild) > 1 )
{
if( x < t->lchild->data ) //左子节点的左边
{
//单向的右旋平衡处理
t = SingleRotateWithRight( t );
}
else //左子节点的右边
{
//双向旋转(先左后右)平衡处理
t = DoubleRotateLeftRight( t );
}
}
}
//返回树的根节点
return t;
}//创建一个平衡二叉排序树
AVLNode * create_AVL()
{
AVLNode * t = NULL; //保存根节点
//从键盘上获取输入数据
char str[32] = {0};
scanf("%s", str );
int i = 0;
while( str[i] )
{
//把新的节点 加入到 平衡二叉树中
t = insert_AVL_node( t, str[i] );
i++;
}
//返回 平衡二叉排序树的根节点
return t;
} 7.哈夫曼树 Huffman
1)哈夫曼树
又称为 最优二叉树
它是n个带权的叶子节点 构成的所有的二叉树中, 带权路径长度WPL最小的二叉树
(1)一棵树的带权路径长度的定义为 树中所有的叶子节点的带权路径长度之和
(2)节点的带权路径长度规定 从根节点 到 该节点之间的路径长度 与 该节点上的权值 的乘积
2)哈夫曼编码
在电报通信中, 电文是以二进制0/1序列形式去发送, 每一个字符对应着一个二进制编码
为了缩短 电文的长度,采用不等长的编码方式,把使用频率高的字符用短编码
使用频率低的字符用长编码
我们把使用频率作为权值, 把每一个字符作为叶子节点来构建哈夫曼树
每一个分支节点的左右分支分别用0和1进行编码, 这样就得到了每一个叶子节点的 哈夫曼编码
使用的是叶子节点的编码, 所以每一个字符的编码都不可能是其他字符编码的前缀
3)构建哈夫曼树
假设有n个带权的叶子节点 w1, w2, w3, w4, ... wn , 则构建哈夫曼树的步骤:
第一步: 构建森林
把每一个叶子节点 都当作是一棵独立的树(只有根结点)
这样就形成了森林
把这片森林存放到 有序队列中 , 方便取出最小的节点
第二步:
从 有序队列中, 取出两个最小的节点
然后再创建一个新的节点 作为它们的父节点
父节点的权值 就是这两个子节点的权值之和
第三步:
把新创建的父节点 加入到 有序队列中
重复 第二步和第三步, 直到这个有序队列中只剩下一个节点为止
最后剩下的这个节点 就是 哈夫曼树的根节点
4)代码实现
Huffman.c / Huffman.h + 链式队列
typedef struct HTnode //哈夫曼树的节点类型
{
int weight; //数据域: 权值
struct HTnode * left; //指针域: 左子节点的指针
struct HTnode * right; //右子节点的指针
} HTnode ;
LinkQueue.c
/*
入队 ---> 有序队列
返回值:
1 入队成功
0 入队失败
*/
int EnQueue( LinkQueue *q, ElemType d )
{
//不能入队的情况: 队列不存在
if( q == NULL )
{
return 0;
}
//创建一个新的数据节点空间, 并初始化
Node * pnew = (Node *)malloc( sizeof(Node) );
pnew->data = d;
pnew->next = NULL;
//入队 --> 插入有序
if( q->num == 0 ) //从无到有
{
q->front = pnew;
q->rear = pnew;
}
else //从少到多
{
//有序队列
Node * p = q->front; //遍历指针
Node * pre = NULL; //指向p的前一个
while( p )
{
//找到第一个比它大的数的前面 (比较二叉树节点里面的权值)
if( p->data->weight > pnew->data->weight )
{
break;
}
pre = p;
p = p->next;
}
if( p != NULL ) //找到了
{
if( p == q->front )
{
//头插
pnew->next = q->front;
q->front = pnew;
}
else
{
//中间插入
pre->next = pnew;
pnew->next = p;
}
}
else //没有找到
{
//尾插法
q->rear->next = pnew;
q->rear = pnew;
}
}
q->num ++;
return 1;
}/*
出队
返回值: 返回出队元素
*/
Node * DeQueue( LinkQueue *q )
{
//不能出队的情况: 队列不存在 || 队列为空
if( q == NULL || q->num == 0 )
{
return 0;
}
//出队
Node * p = q->front; //指向要出队的这个节点
q->front = q->front->next;
p->next = NULL;
q->num --;
if( q->num == 0 ) //仅剩的一个节点也被删除了,那么队尾rear也要被置NULL
{
q->rear = NULL;
}
return p;
}Huffman.c
HTnode * create_Huffman()
{
//从键盘上获取所有叶子节点的权值
int w[MAX_LEN] = {0};
int i;
for( i=0; i<MAX_LEN; i++ )
{
scanf("%d", &w[i] );
}
//定义指针 保存哈夫曼树的根节点
HTnode * r = NULL;
//初始化一个有序队列
LinkQueue * q = InitQueue();
//1.构建森林 (为每一个权值 创建一个叶子节点),并且加入到 有序队列中
HTnode * hfmnode = (HTnode*)malloc( sizeof(HTnode) * MAX_LEN );
for( i=0; i<MAX_LEN; i++ )
{
hfmnode[i].weight = w[i];
hfmnode[i].left = NULL;
hfmnode[i].right = NULL;
//入队
EnQueue( q, hfmnode+i );
}
while( QueueLength( q ) >= 2 )
{
//2.把最小的两个节点出队, 构建父节点
HTnode * p1 = DeQueue( q )->data;
HTnode * p2 = DeQueue( q )->data;
HTnode * parent = (HTnode*)malloc( sizeof(HTnode) );
parent->weight = p1->weight +p2->weight;
parent->left = p1;
parent->right = p2;
//3.把新创建的父节点 加入到有序队列中
EnQueue( q, parent );
}
//把最后剩下的节点出队, 该节点 就是 哈夫曼树的根节点
r = DeQueue( q )->data ;
//销毁队列
DestroyQueue( q );
//返回 哈夫曼树的根节点指针
return r;
}
打印出每一个叶子节点的哈夫曼编码
//打印出每一个叶子节点的哈夫曼编码
void print_Huffman_code( HTnode * t , int i )
{
static int arr[32]; //只初始化一次
HTnode * p = t;
if( p != NULL )
{
if( p->left == NULL && p->right == NULL ) //叶子节点
{
//打印编码
printf("%2d -- ", p->weight );
int j;
for( j=0; j<i; j++ )
{
printf("%d", arr[j] );
}
putchar('\n');
}
else
{
arr[i] = 0;
print_Huffman_code( p->left , i+1 );
arr[i] = 1;
print_Huffman_code( p->right , i+1 );
}
}
}
7.其他
1)树 转换成 二叉树 (参考图示)
(1)树中所有相邻的兄弟节点 进行连接
(2)只保留原树的第一个子节点的连线,删除与其他子节点的连线
2)森林 转换成 二叉树 (参考图示)
(1)树 转换成 二叉树
(2)第一棵树不动, 从第二棵树开始依次把当前二叉树 作为 前一个树的根节点的右子树 进行连接
