亲宝软件园·资讯

展开

C语言 二叉树

雪芙花 人气:0

树概念及结构

树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合
把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的

注意:

如图:

在这里插入图片描述

注意:

相关概念

如图:

在这里插入图片描述

树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间
的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法
等。我们这里就简单的了解其中最常用的 孩子兄弟表示法

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

如图:

在这里插入图片描述

树在实际中的运用(表示文件系统的目录树结构)

在这里插入图片描述

二叉树概念及结构

概念

在这里插入图片描述

需要注意的特殊二叉树

满二叉树:

一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树
也就是说,如果一个二叉树的层数为K,且结点总数是2^k-1,则它就是满二叉树

完全二叉树:

完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的(特殊的完全二叉树)
对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树

二叉树的性质

二叉树的存储结构

存储结构类型:

顺序存储

顺序结构存储就是使用 数组来存储 ,一般使用数组只适合表示完全二叉树(不完全二叉树有空间的浪费)而现实中使用中只有堆才会使用数组来存储

注:二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树

如图:

在这里插入图片描述

链式存储

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是
链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所
在的链结点的存储地址 。

例:

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
 struct BinTreeNode* _pParent; // 指向当前节点的双亲
 struct BinTreeNode* _pLeft; // 指向当前节点左孩子
 struct BinTreeNode* _pRight; // 指向当前节点右孩子
 BTDataType _data; // 当前节点值域
};

总结

这只是二叉树的基本知识,之后我们还会详细解析二叉数的递归实现和有关题目。

加载全部内容

相关教程
猜你喜欢
用户评论