树结构是一种非常重要的非线性结构,改结构中一个元素可以有2个或2个以上的直接后驱,在层级关系中有很多应用。
一 树的基本概念
树是n(n>=0)个节点的有限集合,当n=0为空树,在任一非空树,只有一个根结点,其余结点都是互不相交的有限集合,这些集合又可以构成一个棵树,成为根结点的子树,树的定义是递归的,也就是说一棵树由若干个棵子树构成,而子树又是更小的子树构成。
1-1树的基本结构png
双亲，孩子和兄弟：例如 1-1 A 是树根,B,C,D 是A的孩子结点,B,C,D 互为兄弟;E,F互为兄弟,B是E和F的双亲。
结点的度:一个结点的子树的个数记为结点的度。例如 1-1 B的度为2,A是3。
叶子节点:也称为终端节点,也是度为0的结点,例如在1-1中 C,E,F,G都是叶子节点。
节点层级:根是第一层,根的孩子是第二层。
树的深度:一棵树最大层级为树的高度(深度),例如1-1中树的深度为3。
有序树:树中任意结点子结点有顺序关系(这种顺序关系不能互换),否则为无序树(自由树)。有序树典型应用就是操作的文件排序。比如在macos中同一级下文件拖动位置是无法交换的啊 !Σ(⊙⊙"a
二 二叉树
1 二叉树的性质
性质1 二叉树的第i(i >=0)层,最多有2^(i-1)个节点
性质2 深度为k的二叉树最多有2^k - 1个节点
性质3 二叉树的终端节点为n1,度为2的节点为n2,那么n1和n2的关系是 n1 = n2 +1
2 满二叉树和完全二叉树
深度为k,结点数为2^k -1的二叉树称为满二叉树
对于满二叉树从根结点,自上而下,从左到右依次编号,那么编号为i的结点,左孩子的编号为2i,右孩子为2i + 1,对于深度为k,有n个结点的二叉树,当且仅当每个结点都与深度为k的满二叉树中编号1-n的结点一一对应,成为完全二叉树,否则为非完全二叉树,所以这个满二叉树是个特殊的完全二叉树。
image.png
image.png
显然 n个结点的完全二叉树的深度为:
完全二叉树的深度
3 二叉树的存储
3.1 顺序存储
二叉树的顺序.png
使用顺序存储简单,又节省空间,但是对于一般的二叉树不适用顺序存储,因为在顺序存储中,以结点在存储单元的位置表示结点之间的关系,这样的话要添上一些虚结点,造成空间浪费。
3.2 链式存储
在二叉树中结点包含有数据元素,左子数根,右子树根等信息,可以使用二(三)叉链表来存储二叉树,链表的头指针执行二叉树的根结点。
// 二叉链表
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
二叉链表.png
// 三叉链表
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode,*BiTree;
三叉链表.png
注:结点的^指的的是:在节点数据域的左边表示左子树为空,右边同理
重点学习下 二叉链表和三叉链表的区别
相同点:
都有一个数据域和左右孩子指针域。
不同点
1 三叉链表多了一个指针域,这个指针域指向结点的双亲结点。
2 三叉链表更加容易找到结点的双亲,二叉链表只能往孩子方向查找。
3 三叉链表需要更多的存储单元
3.3 二叉树的遍历
二叉树的遍历有三种方式:先序,后序,中序。
先序: (1) 先访问更节点 (2)先序遍历根的左子树 (3)先序遍历根的右子树
中序:(1) 先中序遍历根的左子树 (2)访问根节点 (3) 中序遍历根的右子树
后序:(1)先后序遍历根的左子树 (2) 后序序遍历根的右子树 (3访问根节点
c程序演练 二叉树使用二叉链表创建,插入元素,遍历元素
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
struct TreeNode *lchild, *rchild;
int data;
}TreeNode,*BiTree;
// 二叉树中插入元素 有位置就插入 1 2 3 5 4 6 横向递增的树 左子树数值小于右子树
// 1
// 2
// 3
// 5
// 4 6
//
//
// 先序 : 1 2 3 5 4 6
// 中序: 1 2 3 4 5 6
// 后序 4 6 5 3 2 1
// 中序: A D F E G H M Z
// 后序 A F D E H Z M G
BiTree insetNode(BiTree root,int data){
BiTree newTree;
BiTree currentTree;
BiTree backTree;
newTree =(TreeNode *)malloc(sizeof(TreeNode));
if (newTree == NULL) exit(1);
newTree->data = data;
newTree->lchild = NULL;
newTree->rchild = NULL;
if(root == NULL) return newTree;
currentTree = root;
// printf("执行1\n");
while(currentTree != NULL){
backTree = currentTree;
if(currentTree->data > data){
currentTree = currentTree->lchild;
//printf("执行2\n");
}
else{
currentTree = currentTree->rchild;
//printf("执行2\n");
}
}
if(backTree->data > data) {
backTree->lchild = newTree;
// printf("执行3\n");
}else{
//printf("执行3\n");
backTree->rchild = newTree;
}
return root;
}
// 创建二叉树
BiTree createTree()
{
BiTree root=NULL;
int len;
int data;
int i;
printf("创建二叉树,请输入节点的总数量: ");
scanf("%d",&len);
printf("请连续输入%d个节点的数据: ",len);
for(i=0;i<len;i++)
{
scanf("%d",&data);
root=insetNode(root,data);
}
return root;
}
// 先序遍历
void preOrder(BiTree root){
if (root == NULL) {
//printf("执行\n");
return;
}
printf("%d ",root->data);
preOrder(root->lchild);
preOrder(root->rchild);
}
// 中序
void centerOrder(BiTree root){
if (root == NULL) {
return;
}
centerOrder(root ->lchild);
printf("%d ",root->data);
centerOrder(root ->rchild);
}
// 后序
void inOrder(BiTree root){
if (root == NULL) {
return;
}
inOrder(root ->lchild);
inOrder(root ->rchild);
printf("%d ",root->data);
}
int main(int argc, char *argv[]){
BiTree tree = NULL;
tree = createTree();
printf("\n前序遍历序列:");
preOrder(tree);
printf("\n中序遍历序列: ");
centerOrder(tree);
printf("\n后序遍历序列: ");
inOrder(tree);
return 0;
}
3.4 最优二叉树
最优二叉树也叫哈夫曼树,是指全职为w1,w2..... n个叶子结点的二叉树带权路径长度最小的二叉树.
构造最优二叉树的方法叫哈夫曼方法.
最优二叉树的一个应用是通信过程中的编码和译码.
3.5 二叉排序树
对于二叉树来说,如果左子树所有结点的值都小于根结点,右子树结点值都大于根结点,左子树和右子树内部也是这种规律,把这种二叉数叫做二叉排序树. 中序遍历将会得到一个递增的序列.
网友评论