科技企业网站模板,wordpress和seo权重,深圳口碑较好的装修公司,杭州市做网站专栏#xff1a;数据结构 个人主页#xff1a;HaiFan. 专栏简介#xff1a;这里是HaiFan.的数据结构专栏#xff0c;今天的内容是二叉树。 二叉树树的概念及结构二叉树概念及结构二叉树的概念二叉树的存储结构二叉树的顺序结构及实现大根堆和小根堆堆的实现及其各个接口堆的… 专栏数据结构 个人主页HaiFan. 专栏简介这里是HaiFan.的数据结构专栏今天的内容是二叉树。 二叉树树的概念及结构二叉树概念及结构二叉树的概念二叉树的存储结构二叉树的顺序结构及实现大根堆和小根堆堆的实现及其各个接口堆的初始化和空间销毁入堆删除堆顶元素返回堆顶元素返回堆的大小判断堆是否为空二叉树的链式实现二叉树的初始化二叉树的创建前序遍历中序遍历后序遍历二叉树的销毁二叉树的大小二叉树第k层的大小二叉树查找数据树的概念及结构
树是一种非线性的数据结构是由n个有限结点组成的具有一个层次关系的集合把称为树是因为把它倒着看很像一颗树。
有一个特殊的结点称为根节点根节点没有前驱结点除根结点之后其余的结点都是互不相交的集合每一个集合都是一颗结构与树类似的子树。树是递归定义的 像这样就被称为树。
子树一旦相交就不再叫做树而是另一种特殊的数据结构—图 除此之外树还有一些性质。 节点的度一个节点含有的子树的个数称为该节点的度如1的度为2 叶节点或终端节点度为0的节点称为叶节点如4567都是叶节点 非终端节点或分支节点度不为0的节点 如123 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如1是2的父节点 孩子节点或子节点一个节点含有的子树的根节点如2是1的孩子节点 兄弟结点具有同一个父节点的子树如2和3就互为兄弟结点 树的度树最大的节点的度称为树的度如树的度为2 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为3 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图4和6 节点的祖先从根到该节点所经分支上的所有节点如上图1是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是1的子孙 森林由mm0棵互不相交的树的集合称为森林 那么树是怎么表示的呢
树的结构就有点复杂了用线性表定义树的话呢会面临一个问题就是一个节点可能有n个子树那么定义多少个接口来存储该节点和子树的关系呢这个不太好解决。于是有大佬相出了解决办法孩子兄弟表示法孩子表示法等等在这里讲解一下孩子兄弟表示法。
struct Node
{struct Node* left_child; //左孩子struct Node* right_child;//右兄弟int data;//数据
}就比如上图中的树 这样存不管有多少个子树都可以存储left存左二子right存兄弟。 二叉树概念及结构
二叉树的概念
二叉树是一种特殊的树形结构它有一个根节点以及每个节点最多有两个子节点(一个左孩子一个右孩子)
性质
因为每个节点最多两个孩子所以二叉树的最大的度不超过2左儿子是左儿子右儿子是右儿子有顺序之分叶子节点没有子节点每一层上的节点数目都不超过2的n - 1次方根节点为第一层对于深度为k的二叉树来说最多有2的n次方-1个节点最少有k个节点对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2则有n0 n2 1若规定根节点的层数为1具有n个结点的满二叉树的深度****h log(n 1). (ps 是log以2为底n1为对数)
特殊的二叉树
满二叉树深度为k且有2的k次方-1个节点的二叉树称为满二叉树
完全二叉树对于深度为k的二叉树来说除了第k层节点从左到右连续排列外其余层节点都连续的排列
二叉树的存储结构
提到存储结构肯定是顺序结构和链式结构。 二叉树的顺序结构就是利用数组去存储一般使用数组只适合完全二叉树因为不是完全二叉树会有空间的浪费(完全二叉树会使得数组中的每一个位置都存的有元素而非完全二叉树会造成空间的浪费想一想为什么) 链式存储定义一个结构体结构体中 有两个结构体指针一个存数据一个指针用来指向左二子一个指针用来指向右儿子。 typedef char TreeDataType;
typedef struct BinaryTreeNode
{TreeDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;二叉树的顺序结构及实现
普通的二叉树不适合用数组来存储数据因为可能会造成大量的空间浪费而完全二叉树比较适合使用顺序结构存储。
提到完全二叉树就不得不提到堆这一概念堆是一个数据结构而不是管理内存的一块区域分段。
大根堆和小根堆
大根堆就是每个节点的值都大于等于父节点的值根节点的值最大 小根堆就是每个节点的值都小于等于父节点的值根节点的值最小 堆的实现及其各个接口
实现堆还是结构体那一套。
typedef struct Heap
{int capacity;HeapDataType* val;int count;
}Heap;void HeapInit(Heap* ps);//初始化
void HeapDestory(Heap* ps);//销毁空间void HeapPush(Heap* ps, HeapDataType x);//入堆
void HeapPop(Heap* ps);//出堆HeapDataType HeapTop(Heap* ps);//返回堆顶元素int HeapSize(Heap* ps);//堆的大小
bool HeapEmpty(Heap* ps);//堆是否为空堆的初始化和空间销毁
之前的链表顺序表双链表等数据结构会的话相信堆的初始化和销毁难不倒各位。
void HeapInit(Heap* ps)
{ps-capacity 4;ps-count 0;ps-val (HeapDataType*)malloc(sizeof(HeapDataType) * ps-capacity);
}void HeapDestory(Heap* ps)
{ps-capacity ps-count 0;free(ps-val);ps-val NULL;
}入堆
入堆之前要检查数组的空间是否够用够用则直接加入数据不够则扩容。
void HeapPush(Heap* ps, HeapDataType x)
{assert(ps);if (ps-capacity ps-count){ps-capacity * 2;HeapDataType* tmp (HeapDataType*)realloc(ps-val, sizeof(HeapDataType) * ps-capacity);if (tmp NULL){perror(malloc fail);exit(-1);}}ps-val[ps-count] x;HeapJustUp(ps-val, ps-count);
}
但是光加入数据可不行要进行向上调整把数据调整成小根堆或者大根堆但是调整是有前提的左右子树必须是一个堆才不会导致堆内数据乱。所以我们每加入一个数据调整一次即可做到堆是一个大堆或者小堆。 void HeapJustUp(HeapDataType* a, int n)
{int parent n - 2 1;int child n - 1;while (parent 0){if (child 1 n a[child 1] a[child]){child;}if (a[parent] a[child]){std::swap(a[parent], a[child]);child parent;parent child - 1 1;}else{break;}}}向上调整堆要找到父亲和孩子父亲就是元素的总个数-2之后在/2孩子就是元素总个数-1.
因为是向上调整父亲节点的下标会慢慢变小所以循环条件可以设置成parent0有了循环条件还要比较左右孩子哪个大然后在让孩子和父亲比较最后更新父亲下标和孩子下标即可。
删除堆顶元素
删除堆顶元素就是让堆顶元素和堆底元素进行一个交换然后元素个数-1.交换完成之后要进行向下调整向下调整要求左右子树是大根堆或者小根堆在入堆这一步我们已经完成了这个操作所以可以直接调整。
void HeapPop(Heap* ps)
{assert(ps);assert(ps-count);std::swap(ps-val[0], ps-val[ps-count--]);HeapJustDown(ps-val, 0, ps-count);
}那么向下调整是怎么调的呢
因为要把堆顶元素调到下面所以从下标为0的位置开始向下调整。
0的位置就是父亲节点然后要找到儿子节点child parent * 2 1然后判断左右孩子哪个大在判断父亲节点和孩子节点的大小关系更新下标即可。
void HeapJustDown(HeapDataType* a, int parent, int n)
{int child parent * 2 1;while (child n){if (child 1 n a[child] a[child 1]){child;}if (a[parent] a[child]){std::swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}返回堆顶元素
HeapDataType HeapTop(Heap* ps)
{assert(ps);return ps-val[0];
}
返回堆的大小
int HeapSize(Heap* ps)
{assert(ps);return ps-count;
}
判断堆是否为空
bool HeapEmpty(Heap* ps)
{assert(ps);return ps-count 0;
}二叉树的链式实现
typedef char TreeDataType;typedef struct BinaryTreeNode
{TreeDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* TreeInit();//初始化BTNode* BinaryTreeCreate();//创建二叉树void BinaryTreeDestory(BTNode* root);//销毁二叉树int BinaryTreeSize(BTNode* root);//二叉树的大小int BinaryTreeLeveKSize(BTNode* root, int k);//第k层有多少个元素BTNode* BinaryTreeFind(BTNode* root, TreeDataType x);//查找数据void PrevOrder(BTNode* root);//前序遍历void InOrder(BTNode* root);//中序遍历void PosOrder(BTNode* root);//后序遍历二叉树的初始化
BTNode* TreeInit()
{BTNode* root (BTNode*)malloc(sizeof(BTNode));root-val 0;root-left NULL;root-right NULL;return root;
}二叉树的创建
BTNode* Creat(BTNode* t)
{TreeDataType ch;cin ch;if (ch -1){t NULL;}else{t-val ch;Creat(t-left);Creat(t-right);}
}
----------------------------------------------------------BTNode* BuyNode(TreeDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-left NULL;newnode-right NULL;return newnode;
}BTNode* BinaryTreeCreate()
{BTNode* newnode1 BuyNode(A);BTNode* newnode2 BuyNode(B);BTNode* newnode3 BuyNode(C);BTNode* newnode4 BuyNode(D);BTNode* newnode5 BuyNode(E);BTNode* newnode6 BuyNode(F);BTNode* newnode7 BuyNode(G);newnode1-left newnode2;newnode1-right newnode3;newnode2-left newnode4;newnode4-left newnode7;newnode3-left newnode5;newnode3-right newnode6;return newnode1;
}两种方法创建二叉树第一种方法是用前序遍历的方法创建二叉树第二种是自己手动创建一个二叉树。
前序遍历
二叉树的前序遍历是先访问根节点在访问左子树在访问右子树是以递归的形式进行的
void PrevOrder(BTNode* root)
{if (root NULL){cout NULL ;return;}cout root-val ;PrevOrder(root-left);PrevOrder(root-right);
} 中序遍历
二叉树的中序遍历是先访问左子树在访问根节点然后右子树同样是以递归的形式进行的。
void PrevOrder(BTNode* root)
{if (root NULL){cout NULL ;return;}cout root-val ;PrevOrder(root-left);PrevOrder(root-right);
}后序遍历
先左子树在右子树最后根节点
void InOrder(BTNode* root)
{if (root NULL){cout NULL ;return;}InOrder(root-left);cout root-val ;InOrder(root-right);
}二叉树的销毁
二叉树的创建是用的先序遍历而二叉树的销毁则用的是后续遍历
void BinaryTreeDestory(BTNode* root)
{if (!root){return;}BinaryTreeDestory(root-left);BinaryTreeDestory(root-right);free(root);
}二叉树的大小
二叉树的大小很好判断想一想一个树很深很多叶子每个子树上都有一个小领导小领导来查他管理的地区的叶子然后层层向上汇报直到汇报给最大的领导就可以完成了。
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}int l BinaryTreeSize(root-left);int r BinaryTreeSize(root-right);return l r 1;}二叉树第k层的大小
第k层的大小该怎么判断呢还是用上面的办法找到第k层的小领导让他把第k层的情况汇报给你即可
int BinaryTreeLeveKSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1){return 1;}int l BinaryTreeLeveKSize(root-left, k - 1);int r BinaryTreeLeveKSize(root-right, k - 1);return l r;}二叉树查找数据
查找数据从左子树找从右子树找依次递归即可
BTNode* BinaryTreeFind(BTNode* root, TreeDataType x)
{if (root NULL){return NULL;}if (root-val x){return root;}BTNode* l BinaryTreeFind(root-left, x);if (l){return l;}BTNode* r BinaryTreeFind(root-right, x);if (r){return r;}return NULL;}
