asp 网站开发教程,网站系统关键字,网站音乐播放器源码,wordpress网站的CDN设置目录 一、树概念及结构(了解)
1.1树的概念
1.2树的表示
二、二叉树概念及结构
2.1概念
2.2现实中的二叉树#xff1a;
2.3数据结构中的二叉树#xff1a;
2.4特殊的二叉树#xff1a; 2.5 二叉树的存储结构
2.51 顺序存储#xff1a;
2.5.2 链式存储…目录 一、树概念及结构(了解)
1.1树的概念
1.2树的表示
二、二叉树概念及结构
2.1概念
2.2现实中的二叉树
2.3数据结构中的二叉树
2.4特殊的二叉树 2.5 二叉树的存储结构
2.51 顺序存储
2.5.2 链式存储
三、二叉树性质相关选择题练习
四、二叉树的实现
4.1头文件
4.2Test.c
4.3前序中序后序(深度优先遍历) 4.4二叉树所有节点的个数
编辑
4.5叶节点的个数
4.6层序遍历(广度优先遍历使用队列) 一、树概念及结构(了解)
1.1树的概念 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它 叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。有一个特殊的结点称为根结点根节点没有前驱结点除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱可以有0个或多个后继因此树是递归定义的。 节点的度一个节点含有的子树的个数称为该节点的度 如下图A的为6 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I...等节点为叶节点 非终端节点或分支节点度不为0的节点 如上图D、E、F、G...等节点为分支节点 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B 的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节 点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4
关于树的高度还有一种看法就是把高度从0开始看此时树的高度为3。 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的多颗树的集合称为森林数据结构中的学习并查集本质就是 一个森林
1.2树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了实际中树有很多种表示方式 如双亲表示法孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子 兄弟表示法。 typedef int DataType; struct Node { struct Node* _firstChild1; // 第一个孩子结点 struct Node* _pNextBrother; // 指向其下一个兄弟结点 DataType _data; // 结点中的数据域 }; 另一种方式顺序表存孩子的指针不推荐使用 struct TreeNode { int data; vectorstruct TreeNode* childs; } 还有一种表示方式双亲表示法:
双亲表示法采用顺序表数组存储普通树其实现的核心思想是顺序存储各个节点的同时给各节点附加一个记录其父节点位置的变量 #define MAX_SIZE 100 // 宏定义树中结点的最大数量 typedef struct Snode{ char data; int parent; } PTNode; typedef struct{ PTNode tnode[MAX_SIZE]; // 存放树中所有结点 int n; // 结点数 } PTree; 1.3树在实际中的运用表示文件系统的目录树结构 二、二叉树概念及结构
2.1概念
一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子 树和右子树的二叉树组成。 二叉树的特点 1. 每个结点最多有两棵子树即二叉树不存在度大于2的结点。 2. 二叉树的子树有左右之分其子树的次序不能颠倒。 2.2现实中的二叉树 2.3数据结构中的二叉树 2.4特殊的二叉树
1. 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉 树。也就是说如果一个二叉树的层数为K且结点总数是(2^k) -1 则它就是满二叉树。 2. 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对 于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号 从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉 树。 2.5 二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。 二叉树的性质 1. 若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1) 个结点. 2. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h- 1. 3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0n2 1 4. 若规定根节点的层数为1具有n个结点的满二叉树的深度hlogN 1
2.51 顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树 会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的章节会专门讲 解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 2.5.2 链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的 方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩 子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链当前我们学习中一般都 是二叉链后面课程学到高阶数据结构如红黑树等会用到三叉链。 三、二叉树性质相关选择题练习 1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为 A ABDHECFG B ABCDEFGH C HDBEAFCG D HDEBFGCA 2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为 A E B F C G D H 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为____。 A adbce B decab C debac D abcde 1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199 2.在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 3.一棵完全二叉树的节点数位为531个那么这棵树的高度为 A 11 B 10 C 8 D 12 四、二叉树的实现 4.1头文件
#pragma once
#include stdio.h
#include stdbool.h
#include assert.h
#include stdlib.htypedef int BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
}BTNode;
4.2Test.c
int main()
{BTNode* A (BTNode*)malloc(sizeof(BTNode));A-data A;A-left NULL;A-right NULL;BTNode* B (BTNode*)malloc(sizeof(BTNode));B-data B;B-left NULL;B-right NULL;BTNode* C (BTNode*)malloc(sizeof(BTNode));C-data C;C-left NULL;C-right NULL;BTNode* D (BTNode*)malloc(sizeof(BTNode));D-data D;D-left NULL;D-right NULL;BTNode* E (BTNode*)malloc(sizeof(BTNode));E-data E;E-left NULL;E-right NULL;A-left B;A-right C;B-left D;B-right E;return 0;
}
4.3前序中序后序(深度优先遍历) void PrevOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%c , root-data);PrevOrder(root-left);PrevOrder(root-right);
}void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%c , root-data);InOrder(root-right);
}void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%c , root-data);} 4.4二叉树所有节点的个数 //方法一:定义全局变量(不推荐)
int size 0;
void TreeSize(BTNode* root)
{if (root NULL){return;}else {size;}TreeSize(root-left);TreeSize(root-right);return size;
}
方法二:传址调用
int TreeSize(BTNode* root,int* psize)
{if (root NULL){return;}else {(*psize);}TreeSize(root-left, psize);TreeSize(root-right, psize);return psize;
}
方法三:递归、分治思想: 否则返回左子树节点数 右子树节点数 1当前节点
int TreeSize(BTNode* root)
{// 如果树为空即根节点为NULL则返回0 // 否则返回左子树节点数 右子树节点数 1当前节点return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
} 4.5叶节点的个数
int LeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return TreeSize(root-left) TreeSize(root-right);} 4.6层序遍历(广度优先遍历使用队列) void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%c , front-data);if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}QueueDestory(q);
} 新年第一篇
祝大家新年快乐 看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注
你们的点赞就是博主更新最大的动力 有问题可以评论或者私信呢秒回哦。
