如何建设网站使用,河北省石家庄市裕华区,网站设计这个专业怎么样,红酒手机网站模板文章目录 文章目录 一、什么是树 树的定义 树的种类 树的深度 树的基本术语 二、满二叉树 定义 满二叉树的特点 三、完全二叉树 定义 特点 四、二叉树的性质 五、二叉树的存储结构 顺序存储结构 链式存储结构 六、二叉树的基本操作 七、二叉树的创建 八、二叉树…文章目录 文章目录 一、什么是树 树的定义 树的种类 树的深度 树的基本术语 二、满二叉树 定义 满二叉树的特点 三、完全二叉树 定义 特点 四、二叉树的性质 五、二叉树的存储结构 顺序存储结构 链式存储结构 六、二叉树的基本操作 七、二叉树的创建 八、二叉树的遍历 前序遍历 中序遍历 后序遍历 九、二叉树的销毁 十、二叉树中节点的查找 欢迎阅读新一期的c语言数据结构模块————二叉树 ✒️个人主页-_Joker_- ️专栏C语言数据结构 代码仓库c_code 欢迎大佬们的阅读和三连关注顺着评论回访 一、什么是树
1.树的定义 树是nn0个结点的有限集。当n 0时称为空树。在任意一棵非空树中应满足 有且仅有一个特定的称为根的结点。当n1时其余节点可分为mm0个互不相交的有限集T1,T2,…,Tm其中每个集合本身又是一棵树并且称为根的子树。 2.树的种类 树的种类可以分为以下几种 无序树树中任意节点的子结点之间没有顺序关系这种树称为无序树,也称为自由树有序树树中任意节点的子结点之间有顺序关系这种树称为有序树二叉树每个节点最多含有两个子树的树称为二叉树满二叉树叶节点除外的所有节点均含有两个子树的树被称为满二叉树完全二叉树除最后一层外所有层都是满节点且最后一层缺右边连续节点的二叉树称为完全二叉树哈夫曼树最优二叉树带权路径最短的二叉树称为哈夫曼树或最优二叉树。 3.树的深度 定义一棵树的根结点层次为1其他结点的层次是其父节点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度。例如 如图图中的树的深度为3 4.树的基本术语 结点的度结点拥有的子树数目叶子终端结点度为0的结点分支非终端结点度不为0的结点树的度树的各结点度的最大值内部结点除根结点之外的分支结点双亲与孩子结点结点的子树的根称为该结点的孩子该结点称为孩子的双亲兄弟属于同一双亲的孩子结点的祖先从根到该结点所经分支上的所有结点结点的子孙该结点为根的子树中的任一结点结点的层次表示该结点在树中的相对位置。根为第一层其他的结点依次下推若结点在第L层上则其孩子在第L1层上兄弟节点双亲在同一层的结点互为兄弟节点树的深高度树中结点的最大层次有序树树中各结点的子树从左至右是有次序的不能互换。否则称为无序树路径长度从树中某结点Ni出发能够“自上而下”通过树中结点到达结点Nj则称Ni到Nj存在一条路径路径长度等于这两个结点之间的分支数树的路径长度从根到每个结点的路径长度之和。森林是mm≥0棵互不相交的树的集合 由于二叉树的使用在数据结构中更加广泛所以我们以二叉树为主来进行讲解下面介绍一下关于二叉树的基本知识。 二、满二叉树
定义 二叉树中如果所有分支结点都存在左子树和右子树并且所有叶子节点都在同一层上这样的二叉树称为满二叉树。 如图为一颗满二叉树 满二叉树的特点 满二叉树的特点有 叶子节点只能出现在最下一层。非叶子结点的度一定是2。在同样深度的二叉树中满二叉树的结点个数最多叶子数最多。设树的深度为i则总结点数为 2^i -1满二叉树是一种特殊的完全二叉树若有双亲则其双亲为i / 2若有左孩子则左孩子为2i 若有右孩子则右孩子为2i 1 。 三、完全二叉树
定义 对二叉树节点由左至右由上至下的编号如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同则这棵二叉树称为完全二叉树。 如图为一颗完全二叉树 特点 叶子结点只能出现在最下层和次下层。最下层的叶子结点集中在树的左部。倒数第二层若存在叶子结点一定在右部连续位置。如果结点度为1则该结点只有左孩子即没有右子树。同样结点数目的二叉树完全二叉树深度最小。满二叉树一定是完全二叉树但反过来不一定成立。 四、二叉树的性质 二叉树的第i层上至多有2^(i-1) (i≥1)个结点深度为k的二叉树至多有2^k-1个结点(k≥1)对任何一棵二叉树T如果其终端结点数为N0度为2的结点数为N2则N0N21具有n个结点的完全二叉树的深度为[log2(n)]1一棵具有n个结点的完全二叉树又称顺序二叉树对其结点按层从上至下每层从左至右进行1-n的编号则对任一结点i1≤i≤n有若i1则i的双亲是[i/2]若i1则i是根无双亲。若2i≤n则i的左孩子是2i否则i无左孩子若2i1≤n则i的右孩子是2i1否则i无右孩子 五、二叉树的储存结构
二叉树的储存结构分为顺序存储结构和链式存储结构
顺序存储结构 二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素即将完全二叉树上编号为i ii的结点元素存储在一维数组下标为 i − 1的分量中。 依据二叉树的性质完全二叉树和满二叉树采用顺序存储比较合适树中结点的序号可以唯一地反映结点之间的逻辑关系这样既能最大可能地节省存储空间又能利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系。 但对于一般的二叉树为了让数组下标能反映二叉树中结点之间的逻辑关系只能添加一些并不存在的空结点让其每个结点与完全二叉树上的结点相对照再存储到一维数组的相应分量中。然而在最坏情况下一个高度为h 且只有h 个结点的单支树却需要占据近2h-1个存储单元。二叉树的顺序存储结构如图所示其中0表示并不存在的空结点。 链式存储结构 由于顺序储存结构非常不便所以我们通常采用链式存储结构实现二叉树。链式存储结构通过开辟一块空间节点通过指针储存左孩子、右孩子节点以及数据。 由于顺序结构操作起来并不方便所以我们通常都以链式存储结构通过递归来实现二叉树定义如下
typedef struct BinaryTree
{int val;struct BinaryTree *left;struct BinaryTree *right;
}BT; 六、二叉树的基本操作 CreateTree() 创建二叉树PreOrder(BT* root)二叉树的前序遍历InOrder(BT* root) 二叉树的中序遍历BackOrder(BT* root) 二叉树的后序遍历DestoryTree(BT* root)销毁二叉树FindTree(BT* root, int x)查找二叉树中值为x的节点 七、二叉树的创建
如下是对二叉树进行创建的算法
BTNode* CreatNode(int x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);exit(-1);}node-val x;node-left NULL;node-right NULL;return node;
} 八、二叉树的遍历
前序遍历 二叉树的前序遍历顺序为根 - 左 - 右 即先访问根节点 然后访问其左孩子节点 最后访问其右孩子节点 例如上图前序遍历顺序为A - B - D - E - C - F 算法如下
void PreOrder(BT* root)
{if (root NULL){return;}printf(%d,root-val);PreOrder(root-left);PreOrder(root-right);
} 中序遍历 二叉树的前序遍历顺序为左 - 根 - 右 即先访问左孩子节点 然后访问其根节点 最后访问其右孩子节点 例如上图前序遍历顺序为D - B - E - A - F - C 算法如下
void InOrder(BT* root)
{if (root NULL){return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
} 后序遍历 二叉树的前序遍历顺序为左 - 右 - 根 即先访问左孩子节点 然后访问其根节点 最后访问其右孩子节点 例如上图前序遍历顺序为D - E - B - F - C - A 算法如下
void BackOrder(BT* root)
{if (root NULL){return;}BackOrder(root-left);BackOrder(root-right);printf(%d , root-val);
} 九、二叉树的销毁
二叉树的销毁同样通过递归来实现
void DestoryTree(BT* root)
{if (root NULL){return;}DestoryTree(root-left);DestoryTree(root-right);free(root);
}十、二叉树中节点的查找
BT* FindTree(BT* root, int x)
{if (root NULL){return;}if (root-val x)return root;FindTree(root-left, x);FindTree(root-right, x);return NULL;
} 以上就是对二叉树的介绍以及基本操作的实现各位老爷别忘了给个支持三连
