平面设计师长逛的网站有哪些,网页设计与网站开发的区别,常州网站建设找思创,wordpress 如何修改域名文章目录 1. 前言2. 树的概念及结构2.1 树的概念2.2 树的相关概念2.3 树的表示 3. 二叉树的概念3.1 特殊二叉树3.2 二叉树的性质 4. 二叉树的顺序存储4.1 堆的概念4.2 堆的实现4.2.1 堆的结点定义4.2.2 堆的打印和销毁4.2.3 堆的插入4.2.4 堆的删除4.2.5 取堆顶数据4.2.6 堆的判… 文章目录 1. 前言2. 树的概念及结构2.1 树的概念2.2 树的相关概念2.3 树的表示 3. 二叉树的概念3.1 特殊二叉树3.2 二叉树的性质 4. 二叉树的顺序存储4.1 堆的概念4.2 堆的实现4.2.1 堆的结点定义4.2.2 堆的打印和销毁4.2.3 堆的插入4.2.4 堆的删除4.2.5 取堆顶数据4.2.6 堆的判空4.2.7 堆的数据个数 4.3 堆的应用4.3.1 堆排序4.3.2 TOP-K问题 5. 二叉树的链式存储5.1 链式二叉树的结点定义5.2 结点创建5.3 模拟创建二叉树5.4 二叉树的遍历5.4.1 前序遍历5.4.2 中序遍历5.4.3 后序遍历5.4.4 层序遍历 5.5 二叉树结点个数及高度等操作5.5.1 二叉树的结点个数5.5.2 二叉树叶子结点的个数5.5.3 二叉树第k层的结点个数5.5.4 查找二叉树中值为x的结点5.5.5 计算二叉树的深度5.5.6 判断是否为完全二叉树 6. 结尾 1. 前言
前面学习了数据结构中线性结构的几种结构顺序表链表栈和队列等今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点所以本文着重介绍二叉树的相关概念和性质以及二叉树的应用。
2. 树的概念及结构
2.1 树的概念 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。 注意事项 1.树是递归定义的 2.树形结构中子树之间不能有交集否则就不是树形结构 2.2 树的相关概念
如果有一棵树如下图所示 那么它有以下概念 节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6 叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点 非终端节点或分支节点度不为0的节点 如上图D、E、F、G…等节点为分支节点 双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点 孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点 兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点 树的度一棵树中最大的节点的度称为树的度 如上图树的度为6 节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推 树的高度或深度树中节点的最大层次 如上图树的高度为4 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点 节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先 子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林 2.3 树的表示
树在存储时既要保存数据也要保存结点与结点之间的关系而且实际中树有许多种表示方法如双亲表示法孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。下面我们就介绍最常用的孩子兄弟表示法。
typedef int TreeDataType;
struct TreeNode
{TreeDataType data;//结点的数据域struct TreeNode* FirstChild;//指向其第一个孩子结点struct TreeNode* NextBrother;//指向其下一个兄弟结点
};3. 二叉树的概念 一棵二叉树是结点的一个有限集合该集合: 1.或者为空 2.由一个根结点加上两棵分别称为左子树和右子树的二叉树组成 如下图所示就是一颗二叉树 从上图我们可以看出 1.二叉树不存在度大于2的结点 2.二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树 3.1 特殊二叉树
二叉树中还有俩种特殊的二叉树 1.满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是2^k - 1则它就是满二叉树。 2.完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。 3.2 二叉树的性质 1.若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点 2.若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h-1 3.对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n0 n2 1 4.若规定根节点的层数为1具有n个结点的满二叉树的深度h log2(n1) 5.对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号 则对于序号为i的结点有 1若i 0i位置节点的双亲序号(i - 1) / 2若i 0则i为根节点编号无双亲节点 2若2i 1 n左孩子序号2i 1若2i 1 n则无左孩子 3若2i 2 n右孩子序号2i 2若2i 2 n则无右孩子 4. 二叉树的顺序存储 顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。 二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 而现实中只有堆才会使用数组来存储。 4.1 堆的概念 所有元素按完全二叉树的顺序存储方式存储在一个一维数组中将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 4.2 堆的实现
4.2.1 堆的结点定义
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;4.2.2 堆的打印和销毁
打印
void HeapPrint(HP* php)
{assert(php);int i 0;for (i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}4.2.3 堆的插入 先插入一个数据到数组的尾上再进行向上调整算法直到满足大根堆或者小根堆。 向上调整算法以小根堆来举例从该结点开始向上找父结点如果该结点小于父结点就把该结点和父结点交换继续向上调整直到满足小根堆。 插入
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(malloc);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}向上调整算法
void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}4.2.4 堆的删除 删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 向下调整算法以小根堆来举例从该结点开始向下找子结点如果子结点小于该结点就把子结点和该结点交换再继续向下调整直到满足小根堆 删除
void HeapPop(HP* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){if (child 1 size (a[child 1] a[child])){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}4.2.5 取堆顶数据 堆顶元素就是数组下标为0的元素 HPDataType HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}4.2.6 堆的判空 size为0即为空 bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}4.2.7 堆的数据个数 size的大小就是数据个数 int HeapSize(HP* php)
{assert(php);return php-size;
}4.3 堆的应用
4.3.1 堆排序 堆排序即利用堆的思想来进行排序总共分为两个步骤 1.建堆 升序建大堆 降序建小堆 2.利用堆删除思想来进行排序 void HeapSort(int* arr, int size)
{//排升序建大堆排降序建小堆//向上调整建堆O(N*logN)//int i 0;//for (i 1; i size; i)//{// AdjustUp(arr, i);//}//向下调整建堆O(N)int i 0;for (i (size - 1 - 1) / 2; i 0; i--){AdjustDown(arr, size, i);}int end size - 1;while (end 0){Swap(arr[0], arr[end]);AdjustDown(arr, end, 0);end--;}
}int main()
{int arr[10] { 23,45,48,123,12,49,80,15,5,35 };HeapSort(arr, 10);int i 0;for (i 0; i 10; i){printf(%d , arr[i]);}return 0;
}4.3.2 TOP-K问题 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 思路 1.用数据集合中前K个元素来建堆 求前k个最大的元素则建小堆 求前k个最小的元素则建大堆 2.用剩余的N - K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N - K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 void PrintTopK(int* a, int n, int k)
{//1.建堆--用a中前k个元素建堆int* kMaxHeap (int*)malloc(sizeof(int)*k);assert(kMaxHeap);int i 0;for (i 0; i k; i){kMaxHeap[i] a[i];}for (i (k - 1 - 1) / 2; i 0; i--){AdjustDown(kMaxHeap, k, i);}//2.将剩余n-k个元素依次与堆顶元素交换不满则则替换int j 0;for (j k; j n; j){if (a[j] kMaxHeap[0]){kMaxHeap[0] a[j];AdjustDown(kMaxHeap, k, 0);}}for (i 0; i k; i){printf(%d , kMaxHeap[i]);}
}void TestTopk()
{int n 10000;int* a (int*)malloc(sizeof(int) * n);srand(time(0));for (int i 0; i n; i){a[i] rand() % 1000000;}a[5] 1000000 1;a[1231] 1000000 2;a[531] 1000000 3;a[5121] 1000000 4;a[115] 1000000 5;a[2335] 1000000 6;a[9999] 1000000 7;a[76] 1000000 8;a[423] 1000000 9;a[3144] 1000000 10;PrintTopK(a, n, 10);
}int main()
{TestTopk();return 0;
}5. 二叉树的链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。 链式结构又分为二叉链和三叉链。 5.1 链式二叉树的结点定义
typedef int BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType data;
}BTNode;5.2 结点创建
BTNode* CreatBTNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));assert(node);node-data x;node-left NULL;node-right NULL;return node;
}由于二叉树的创建比较复杂所以下面我们来手动模拟一个简单的二叉树便于后边操作的实现
5.3 模拟创建二叉树
BTNode* CreatBinaryTree()
{BTNode* node1 CreatBTNode(1);BTNode* node2 CreatBTNode(2);BTNode* node3 CreatBTNode(3);BTNode* node4 CreatBTNode(4);BTNode* node5 CreatBTNode(5);BTNode* node6 CreatBTNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}5.4 二叉树的遍历 二叉树的遍历有前序/中序/后序/层序的递归结构遍历 1.前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 2.中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。 3.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 4.层序遍历(Level Traversal)——从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 5.4.1 前序遍历
void PreOrder(BTNode* root)
{if (root NULL){printf(# );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}5.4.2 中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(# );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}5.4.3 后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(# );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}5.4.4 层序遍历 层序遍历稍微复杂一点需要队列来实现我们这里就之前使用之前创建好的队列不再过多展示核心思路是先判断该结点是不是空如果不是就进队再判断队是不是空如果不是先打印出此时队头元素然后删除队头元素接下来再分别判断打印的队头元素的左孩子和右孩子是不是为空不是空就继续入队。这样循环迭代即层序遍历。 void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);printf(%d , front-data);QueuePop(q);if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}}QueueDestroy(q);
}5.5 二叉树结点个数及高度等操作
5.5.1 二叉树的结点个数 因为二叉树的左子树和右子树都可以分别看成单独的二叉树所以核心思路是递归计算左子树和右子树的结点个数最后返回再加1就是该二叉树的结点个数。 int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}5.5.2 二叉树叶子结点的个数 左右子树都为空的结点就是叶子结点这里也采用递归的思路把二叉树分为左子树和右子树左子树也可以分为左子树和右子树递归计算并返回即可求的整棵树的叶子结点个数。 int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
}5.5.3 二叉树第k层的结点个数 这里的思路是求根结点的第k层的结点个数可以转换成求该结点的左孩子的第k-1层的结点个数该结点的右孩子的第k-1层的结点个数递归下去结束后返回的即为根结点第k层的结点个数。 int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k 1);if (root NULL){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);}5.5.4 查找二叉树中值为x的结点 这里的思路是如果该结点就是要求的结点直接返回该结点如果不是就递归查找该结点的左子树和右子树找到就返回。 BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* ret1 BinaryTreeFind(root-left, x);if (ret1){return ret1;}BTNode* ret2 BinaryTreeFind(root-right, x);if (ret2){return ret2;}return NULL;
}5.5.5 计算二叉树的深度 二叉树的深度就是该二叉树的左子树和右子树的最大深度再1这里的思路是递归计算左子树的深度和右子树的深度每次返回都是以某个结点为根的二叉树的深度最后返回的就是该二叉树的深度。 int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int LeftDepth BinaryTreeDepth(root-left);int RightDepth BinaryTreeDepth(root-right);return LeftDepth RightDepth ? LeftDepth 1 : RightDepth 1;}5.5.6 判断是否为完全二叉树 这里也要用到队列核心思路是利用完全二叉树的性质完全二叉树的非空结点一定是连在一起的一旦出现空结点则空结点后面的所有结点都应该为空如果还有非空结点就不是完全二叉树。 int BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){QueuePush(q, front-left);QueuePush(q, front-right);}else{break;}}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}6. 结尾
到这里二叉树的概念及二叉树顺序结构和链式结构的实现和应用就介绍完了二叉树作为数据结构中的重点和难点需要反复学习理解透彻非常考验大家的理解能力和基本功本人也是一个初学者文中难免有很多地方出现错误和纰漏此文仅供大家学习和参考。如果本文对大家学习二叉树有帮助的话博主感到非常荣幸。 最后感谢各位大佬的耐心阅读和支持觉得本篇文章写的不错的朋友可以三连关注支持一波如果有什么问题或者本文有错误的地方大家可以私信我也可以在评论区留言讨论再次感谢各位。
