脚本宝典收集整理的这篇文章主要介绍了【数据结构&算法】11-树基础&二叉树遍历,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
主要描述二叉树。
李柱明博客:https://www.cnblogs.com/lizhuming/p/15487394.html
树:
结点:
结点的度:结点拥有的子树数。
叶结点或终结点:度为 0 的结点。
非终结点或分支结点:度不为 0 的结点。
内部结点:除根结点外,分支结点也称为内部结点。
树的度:树内各结点的度的最大值。
结点关系:
树的其它相关概念:
简单的顺序存储结构无法直接反映逻辑关系,不能满足树的实现要求。
故充分利用顺序存储和链式存储结构的特点,介绍三种不同的表示法:
引入:除根节点外,其余每个结点,不一定有孩子,但一定有且仅有一个双亲 定义:设以一组连续空间存储树的结点,同时在每个结点中,附设一个指示器指示其双亲结点到链表中的位置。
缺点:
上述第一个缺点引发的思考:
需要关注什么数据域就在数据结构中添加什么数据域。如双亲域、长子域、兄弟域等等。
参考代码:
/* 树的双亲表示法结点数据结构 */
#define MAX_TREE_SIZE 100
typedef int tree_elem_type;
/* 结点结构 */
typedef struct tree_node
{
int parent; // 双亲位置
// int firstchild; // 长子位置
// int rightsib; // 右兄弟位置
tree_elem_type data; // 数据
}tree_node_t;
/* 树结构 */
typedef struct tree
{
int root; // 根节点位置
int num; // 当前节点数
tree_node_t nodes[MAX_TREE_SIZE];
}tree_t;
多重链表表示法:
方案 1:
方案 2:
孩子表示法:
把每个结点的孩子结点排列起来,以单链表作存储结构,则 n 个结点有 n 个孩子链表,如果是叶子结点,则此单链表为空。然后 n 个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中。
孩子表示法的两种结点数据结构:
缺点:找双亲需要遍历树。
参考代码:
/* 树的孩子表示法结点数据结构 */
#define MAX_TREE_SIZE 100
typedef int tree_elem_type;
/* 孩子结点结构 */
typedef struct c_tree_node
{
int child; // 孩子下标
struct c_tree_node *next; // 下一个
}c_tree_node_t;
/* 表头结构 */
typedef struct tree_top
{
c_tree_node_t *firstchild; // 头结点
tree_elem_type data; // 数据
}tree_top_t;
/* 树结构 */
typedef struct tree
{
int root; // 根节点位置
int num; // 当前节点数
tree_top_t nodes[MAX_TREE_SIZE];
}tree_t;
引入:
参考代码:
/* 树的孩子兄弟表示法结点数据结构 */
typedef int tree_elem_type;
typedef struct tree_node
{
struct tree_node *firstchild; // 长子域
struct tree_node *rightsib; // 右兄域
tree_elem_type data; // 数据
}tree_node_t;
二叉树的定义:
二叉树特点:
二叉树的五种基本形态:
左斜树&右斜树:
满二叉树:
定义:所有分支结点都存在左右子树,并且所有叶子都在同一层。
特点:
完全二叉树:
定义:对一棵具有 n 个结点的二叉树按层序编号,如果编号 i(1<=i<=n)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同,则此二叉树为完全二叉树。
特点:
判断方法:给每个结点按满二叉树的结构逐层排序,如果编号出现空档,就不是,否则就是。
性质 1:在二叉树的第 i 层上至多有 2i-1 个结点(i>=1)。
性质 2:深度为 k 的二叉树至多有 2k-1 个结点(k>=1)。
性质 3:对任何一棵二叉树 T,如果其终端结点数为 n0,度为 2 的结点数为 n2,则 n0 = n2+1。
性质 4:具有 n 个结点的完全二叉树的深度为[log2n ] + 1([X]表示不大于 X 的最大整数)。
性质 5:如果对一颗有 n 个结点的完全二叉树(其深度为[log2n ] + 1)的结点按层序编号(从第 1 层到第[log2n ] + 1 层,每层从左到右),对任一结点 i(1<=i<=n)有:
有顺序存储结构和链式存储结构。
二叉树的顺序存储结构:
二叉树的链式存储结构:
链表每个结点包含一个数据域和两个指针域:
遍历是二叉树中非常重要的操作。
二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点都被访问 1 次。
四种遍历方法:
前、中、后序表示的是节点与它的左右子树节点遍历打印的先后顺序。
实现思路:递归。
前序遍历是指,对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。
代码实现思路:
中-> 左 -> 右。使用栈辅助实现。
参考代码(递归):
/* 顺序存储结构 */
void pre_order_traverse(bi_tree tree,int e)
{
visit(tree[e]); // 打印父节点
if(tree[2*e+1]!=nil) /* 左子树不空 */
pre_traverse(tree,2*e+1); // 递归
if(tree[2*e+2]!=nil) /* 右子树不空 */
pre_traverse(tree,2*e+2); // 递归
}
/* 链式存储结构 */
void pre_order_traverse(bi_tree *tree)
{
if(tree==NULL)
return;
printf("%c",tree->data);/* 显示结点数据,可以更改为其它对结点操作 */
pre_order_traverse(tree->lchild); /* 再先序遍历左子树 */
pre_order_traverse(tree->rchild); /* 最后先序遍历右子树 */
}
中序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树
代码实现思路:
左-> 中 -> 右。使用栈辅助实现。
参考代码(递归):
/* 顺序存储结构 */
void in_order_traverse(bi_tree tree,int e)
{
if(tree[2*e+1]!=nil) /* 左子树不空 */
in_traverse(tree,2*e+1); // 递归
visit(tree[e]); // 打印父节点
if(tree[2*e+2]!=nil) /* 右子树不空 */
in_traverse(tree,2*e+2); // 递归
}
/* 链式存储结构 */
void in_order_traverse(bi_tree *tree)
{
if(tree==NULL)
return;
in_order_traverse(tree->lchild); /* 再先序遍历左子树 */
printf("%c",tree->data);/* 显示结点数据,可以更改为其它对结点操作 */
in_order_traverse(tree->rchild); /* 最后先序遍历右子树 */
}
后序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点本身。
代码实现思路:
左-> 右 -> 中。
参考代码(递归):
/* 顺序存储结构 */
void post_order_traverse(bi_tree tree,int e)
{
if(tree[2*e+1]!=nil) /* 左子树不空 */
post_traverse(tree,2*e+1); // 递归
if(tree[2*e+2]!=nil) /* 右子树不空 */
post_traverse(tree,2*e+2); // 递归
visit(tree[e]); // 打印父节点
}
/* 链式存储结构 */
void post_order_traverse(bi_tree *tree)
{
if(tree==NULL)
return;
post_order_traverse(tree->lchild); /* 再先序遍历左子树 */
post_order_traverse(tree->rchild); /* 最后先序遍历右子树 */
printf("%c",tree->data);/* 显示结点数据,可以更改为其它对结点操作 */
}
根起,从上而下,从左至右。
对于顺序存储,只需要按下标顺序输出即可。
但是对于链式存储结构就复杂点,思路如下:借助队列的方式实现:
/* 顺序存储结构:直接打印数组 */
void level_order_traverse(bi_tree tree)
{
int i=MAX_TREE_SIZE-1;
int j=0;
while(tree[i]==nil)
i--; /* 找到最后一个非空结点的序号 */
for(j=0;j<=i;j++) /* 从根结点起,按层序遍历二叉树 */
if(tree[j]!=nil)
visit(tree[j]); /* 只遍历非空的结点 */
printf("n");
}
/* 链式存储结构:借助队列 */
void level_order_traverse(bi_tree_node* tree)
{
bi_tree_node* temp = NULL;
queue_push(tree); // 跟节点入队
while (!queue_empty())
{
temp = queue_pop();
printf("%d ", temp->data); //输出队首结点
if (temp->left) //把Pop掉的结点的左子结点加入队列
queue_push(temp->left);
if (temp->right) // 把Pop掉的结点的右子结点加入队列
queue_push(temp->right);
}
}
二叉树的扩展二叉树:
二叉树除了根节点,其余节点最多有三条线:
树转换为二叉树的步骤:
加线:所有兄弟结点之间加一条线。
去线:对树中每个结点,只保留与第一个孩子的线。删除与其它孩子的线。
层次调整:
森林转换为二叉树的步骤:
二叉树转为树的步骤:
二叉树的根节点有右孩子,则说明该二叉树可以就可以转换为森林。
二叉树转换为森林的步骤:
树的遍历有两种:
森林的遍历也有两种:
以上是脚本宝典为你收集整理的【数据结构&算法】11-树基础&二叉树遍历全部内容,希望文章能够帮你解决【数据结构&算法】11-树基础&二叉树遍历所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。