企业官网建设流程全解析

今天学习了数据结构的剩下知识，二叉树，哈希表，新增的几种排序，我觉得难点集中在二叉树的递归函数的使用和理解，二叉树主要就是不断地递归进行遍历和创建，哈希表就是用键值来查找数据，结合了链表的使用，我觉得不难理解，排序有冒泡，选择，插入，希尔排序，快速排序，主要难理解的就是快速排序，我觉得还是得花点时间去理解快速排序，今天先总结一下学习的知识。

1.二叉树

1.深度优先遍历

前序遍历：根左右

中序遍历：左根右

后序遍历：左右根

2.广度优先遍历

主要使用队列来进行操作

void LayerOrderBTree(BTreeNode_t *pTmpRoot) { Node_t *plinkqueue = NULL; BTreeNode_t *pTmpNode = NULL; plinkqueue = CreateLinkQueue(); EnterLinkQueue(plinkqueue, pTmpRoot); while (!IsEmptyLinkQueue(plinkqueue)) { pTmpNode = QuitLinkQueue(plinkqueue); printf("%c ", pTmpNode->Data); if (pTmpNode->pLeftChild != NULL) { EnterLinkQueue(plinkqueue, pTmpNode->pLeftChild); } if (pTmpNode->pRightChild != NULL) { EnterLinkQueue(plinkqueue, pTmpNode->pRightChild); } } DestroyLinkQueue(&plinkqueue); return; }

销毁二叉树（主要还是遍历的思想）

int DestroyBTree(BTreeNode_t *pTmpRoot) { if (pTmpRoot->pLeftChild != NULL) { DestroyBTree(pTmpRoot->pLeftChild); } if (pTmpRoot->pRightChild != NULL) { DestroyBTree(pTmpRoot->pRightChild); } free(pTmpRoot); return 0; }

创建二叉树

BTreeNode_t *CreateCompleteBTree(int StartNo, int EndNo) { BTreeNode_t *pTmpNode = NULL; //1.申请节点 pTmpNode = malloc(sizeof(BTreeNode_t)); if (NULL == pTmpNode) { printf("malloc failed\n"); return NULL; } //2.将编号存进去 pTmpNode->No = StartNo; //3.判断左子树是否存在,存在左子树创建左子树 if (2 * StartNo <= EndNo) { pTmpNode->pLeftChild = CreateCompleteBTree(2 * StartNo, EndNo); } else { pTmpNode->pLeftChild = NULL; } //4.判断右子树是否存在,存在右子树创建右子树 if (2 * StartNo + 1 <= EndNo) { pTmpNode->pRightChild = CreateCompleteBTree(2 * StartNo + 1, EndNo); } else { pTmpNode->pRightChild = NULL; } return pTmpNode; }

获取树高度

int GetBTreeHigh(BTreeNode_t *pTmpRoot) { int LeftHigh = 0; int RightHigh = 0; if (NULL == pTmpRoot) { return 0; } LeftHigh = GetBTreeHigh(pTmpRoot->pLeftChild); RightHigh = GetBTreeHigh(pTmpRoot->pRightChild); return (LeftHigh > RightHigh ? LeftHigh : RightHigh) + 1; }

2.排序

1.选择跟冒泡之前写过，还算理解

2.插入排序

主要思想是把数组分为两个部分，左边已经有序，右边无序区。每次从无序区取出第一 个数，插入到左边有序区的合适位置，不断扩大有序区，直到全部有序。

3.希尔排序

跟插入排序很像，但是是通过先初始步长为Len/2，每次步长为二分之一长度，来进行插入排序，

。

4.快速排序

选一个基准元素pivot，把数组划分成两部分：

• 左边全部 ≤ pivot

• 右边全部 ≥ pivot
基准元素放到它最终正确位置。
再递归对左子数组、右子数组重复划分，直到子数组长度为1（天然有序）。