DS

沟通的目的不在于自己表达了什么，而在于对方给到你的反馈， 自由了解了对方反馈，才能真正达到沟通的目的！

1.BinTree.h

//二叉树的链式存储方式--孩子表示法** #pragma once typedef int BTDataType; typedef struct BTNode{ struct BTNode* _pLeft; struct BTNode* _pRight; BTDataType _data; }BTNode; //获取二叉树** BTNode* BuyBinTreeNode(BTDataType data); //二叉树的创建** BTNode* _CreatBinTree(BTDataType* array, int size, int* index, BTDataType invalid); //重新包装 BTNode* CreatBinTree(BTDataType* array, int size, BTDataType invalid); //二叉树的拷贝(查询概念) void* CopyBinTree(BTNode* pRoot); //前序遍历** void PreOrder(BTNode* pRoot); //中序遍历** void InOrder(BTNode* pRoot); //后序遍历** void PosOrder(BTNode* pRoot); //获取二叉树中第k层结点的个数** void GetKLevelNodeCount(BTNode* pRoot, int K); //获取二叉树中的结点** int GetBinTreeSize(BTNode* pRoot); //叶子结点个数** int GetLeafCount(BTNode* pRoot); //获取树的高度** void GetBinTreeHeight(BTNode* pRoot); //元素在树中位置的查找** BTNode BinTreeFind(BTNode* pRoot, BTDataType x); //销毁** void DestroyBinTree(BTNode** pRoot); //测试** void TestBinTree();

2.BinTree.c

#include "BinTree.h" #include <stdio.h> #include <malloc.h> #include <assert.h> #include <string.h> **//获取二叉树** BTNode* BuyBinTreeNode(BTDataType data){ BTNode* pNewNode = (BTNode*)malloc(sizeof(BTNode)); if (NULL == pNewNode){ assert(0); return NULL; } pNewNode->_data = data; pNewNode->_pLeft = NULL; pNewNode->_pRight = NULL; return pNewNode; } **//二叉树的创建** BTNode* _CreatBinTree(BTDataType* array, int size, int* index, BTDataType invalid{ BTNode* pRoot = NULL; if (*index < size && invalid != array[*index]){ //创建根节点 pRoot = BuyBinTreeNode(array[*index]); //创建根的左子树 ++(*index); pRoot->_pLeft = _CreatBinTree(array, size, index, invalid); //创建根的右子树 ++(*index); pRoot->_pRight = _CreatBinTree(array, size, index, invalid); } return pRoot; } **//重新包装** BTNode* CreatBinTree(BTDataType* array, int size,BTDataType invalid){ int index = 0; return _CreatBinTree(array, size, &index, invalid); } **//前序遍历** void PreOrder(BTNode* pRoot){ if (pRoot){ printf("%c ", pRoot->_data); PreOrder(pRoot->_pLeft); PreOrder(pRoot->_pRight); } } **//中序遍历** void InOrder(BTNode* pRoot){ if (pRoot){ InOrder(pRoot->_pLeft); printf("%c ", pRoot->_data); InOrder(pRoot->_pRight); } } **//后序遍历** void PosOrder(BTNode* pRoot){ if (pRoot){ PosOrder(pRoot->_pLeft); PosOrder(pRoot->_pRight); printf("%c ", pRoot->_data); } } **//叶子结点个数** int GetLeafCount(BTNode* pRoot){ if (NULL == pRoot){ return 0; } if (NULL == pRoot->_pLeft && NULL == pRoot->_pRight){ return 1; } return GetLeafCount(pRoot->_pLeft) + GetLeafCount(pRoot->_pRight); } **//销毁(后序方法)** void DestroyBinTree(BTNode** pRoot){ if (*pRoot){ DestroyBinTree(&(*pRoot)->_pLeft); DestroyBinTree(&(*pRoot)->_pRight); free(*pRoot); *pRoot = NULL; } } **//测试** void TestBinTree(){ char* str = "ABD$$$CE$$F"; BTNode* pRoot = CreatBinTree(str, strlen(str),'$'); printf("前序遍历结果: "); PreOrder(pRoot); printf("\n"); printf("中序遍历结果: "); InOrder(pRoot); printf("\n"); printf("后序遍历结果: "); PosOrder(pRoot); printf("\n"); DestroyBinTree(&pRoot); }

3.test.c

#include "BinTree.h" int main(){ TestBinTree(); system("pause"); return 0; } #include <iostream> using namespace std; #if 0 // 所有排序：模板 + 仿函数 void HeapAdjust(int* array, int size, int parent) { int child = parent * 2 + 1; while (child < size) { // 找左右孩子中较大的孩子 if (child+1 < size && array[child+1] > array[child]) { child += 1; } if (array[parent] < array[child]) { swap(array[parent], array[child]); parent = child; child = parent * 2 + 1; } else return; } } // 堆排序 void HeapSort(int* array, int size) { // 1. 创建堆---向下调整 // 升序---->大堆 降序---小堆 // 找倒数第一个非叶子节点 int root = ((size - 2) >> 1); for (; root >= 0; --root) HeapAdjust(array, size, root); // 2. 堆删除的思想---向下调整 int end = size - 1; while (end) { swap(array[0], array[end]); HeapAdjust(array, end, 0); --end; } } int main() { int array[] = {3,4,1,9,0,6,8,5,2,7}; HeapSort(array, sizeof(array) / sizeof(array[0])); return 0; } #endif #if 0 template<class T, class Compare> void HeapAdjust(T* array, int size, int parent, Compare com) { int child = parent * 2 + 1; while (child < size) { // 找左右孩子中较大的孩子 if (child + 1 < size && com(array[child + 1], array[child])) { child += 1; } if (com(array[child], array[parent])) { swap(array[parent], array[child]); parent = child; child = parent * 2 + 1; } else return; } } // 堆排序 template<class T, class Compare> void HeapSort(T* array, int size, Compare com) { // 1. 创建堆---向下调整 // 升序---->大堆 降序---小堆 // 找倒数第一个非叶子节点 int root = ((size - 2) >> 1); for (; root >= 0; --root) HeapAdjust(array, size, root, com); // 2. 堆删除的思想---向下调整 int end = size - 1; while (end) { swap(array[0], array[end]); HeapAdjust(array, end, 0, com); --end; } } #include <functional> int main() { int array[] = { 3, 4, 1, 9, 0, 6, 8, 5, 2, 7 }; HeapSort(array, sizeof(array) / sizeof(array[0]), less<int>()); //sort(array, array + sizeof(array) / sizeof(array[0]), greater<int>()) return 0; } #endif #include <vector> // 孩子表示法 struct BTNode { BTNode(int data) : _pLeft(nullptr) , _pRight(nullptr) , _data(data) {} BTNode* _pLeft; BTNode* _pRight; int _data; }; // A B D C E F BTNode* CreateBinTree(const vector<int>& v, int& index, const int invalid) { BTNode* pRoot = nullptr; if (index < v.size() && invalid != v[index]) { // 创建根节点pRoot pRoot = new BTNode(v[index]); // 创建pRoot的左子树 pRoot->_pLeft = CreateBinTree(v, ++index, invalid); // 创建pRoot的右子树 pRoot->_pRight = CreateBinTree(v, ++index, invalid); } return pRoot; } void Destroy(BTNode*& pRoot) { if (pRoot) { Destroy(pRoot->_pLeft); Destroy(pRoot->_pRight); delete pRoot; pRoot = nullptr; } } // 遍历：对二叉树中的每个节点进行某种操作，并且每个节点只操作一次 // 前序、中序、后序 // 操作：将节点中的值域打印 void PreOrder(BTNode* pRoot) { if (pRoot) { cout << pRoot->_data << " "; PreOrder(pRoot->_pLeft); PreOrder(pRoot->_pRight); } } #include <stack> void PreOrderNor(BTNode* pRoot) { if (nullptr == pRoot) return; stack<BTNode*> s; s.push(pRoot); while (!s.empty()) { BTNode* pCur = s.top(); s.pop(); cout << pCur->_data << " "; if (pCur->_pRight) s.push(pCur->_pRight); if (pCur->_pLeft) s.push(pCur->_pLeft); } } void InOrder(BTNode* pRoot) { if (pRoot) { InOrder(pRoot->_pLeft); cout << pRoot->_data << " "; InOrder(pRoot->_pRight); } } void InOrderNor(BTNode* pRoot) { if (nullptr == pRoot) return; stack<BTNode*> s; BTNode* pCur = pRoot; while (!s.empty() || pCur) { // 找以pRoot为根的二叉树最左侧的节点，并保存其所经路径中所有节点 while (pCur) { s.push(pCur); pCur = pCur->_pLeft; } pCur = s.top(); cout << pCur->_data << " "; s.pop(); pCur = pCur->_pRight; } } void PostOrder(BTNode* pRoot) { if (pRoot) { PostOrder(pRoot->_pLeft); PostOrder(pRoot->_pRight); cout << pRoot->_data << " "; } } void PostOrderNor(BTNode* pRoot) { if (nullptr == pRoot) return; stack<BTNode*> s; BTNode* pCur = pRoot; BTNode* pPrev = nullptr; while (!s.empty() || pCur) { // 找以pRoot为根的二叉树最左侧的节点，并保存其所经路径中所有节点 while (pCur) { s.push(pCur); pCur = pCur->_pLeft; } BTNode* pTop = s.top(); // pTop右子树不存在 // pTop右子树已经遍历 if (nullptr == pTop->_pRight || pTop->_pRight == pPrev) { cout << pTop->_data << " "; pPrev = pTop; s.pop(); } else { pCur = pTop->_pRight; } } } #include <queue> void LevelOrder(BTNode* pRoot) { if (nullptr == pRoot) return; queue<BTNode*> q; q.push(pRoot); while (!q.empty()) { BTNode* pCur = q.front(); cout << pCur->_data << " "; if (pCur->_pLeft) q.push(pCur->_pLeft); if (pCur->_pRight) q.push(pCur->_pRight); q.pop(); } } size_t Height(BTNode* pRoot) { if (nullptr == pRoot) return 0; size_t leftHeight = Height(pRoot->_pLeft); size_t rightHeight = Height(pRoot->_pRight); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } size_t GetBTreeNode(BTNode* pRoot) { if (nullptr == pRoot) return 0; return GetBTreeNode(pRoot->_pLeft) + GetBTreeNode(pRoot->_pRight) + 1; } size_t GetLeafNode(BTNode* pRoot) { if (nullptr == pRoot) return 0; if (nullptr == pRoot->_pLeft && nullptr == pRoot->_pRight) { return 1; } return GetLeafNode(pRoot->_pLeft) + GetLeafNode(pRoot->_pRight); } size_t GetKLevelNodeCount(BTNode* pRoot, size_t K) { if (nullptr == pRoot || 0 == K) return 0; if (1 == K) return 1; return GetKLevelNodeCount(pRoot->_pLeft, K - 1) + GetKLevelNodeCount(pRoot->_pRight, K - 1); } BTNode* GetParent(BTNode* pRoot, BTNode* pNode) { if (nullptr == pRoot || pRoot == pNode) return nullptr; if (pRoot->_pLeft == pNode || pRoot->_pRight == pNode) return pRoot; BTNode* pParent = GetParent(pRoot->_pLeft, pNode); if (pParent) return pParent; return GetParent(pRoot->_pRight, pNode); } // 前序 中序 BTNode* _ReBuildTree(const vector<int>& pre, int& index, const vector<int>& In, int left, int right) { if (left >= right) return nullptr; // 1. 从前序遍历结果中获取根节点 BTNode* pRoot = new BTNode(pre[index]); // 2. 从中序遍历结果确认根的左右子树 size_t InIdx = left; while (In[InIdx] != pre[index]) InIdx++; // [left, InIdx) // [InIdx+1, right) if (left < InIdx) pRoot->_pLeft = _ReBuildTree(pre, ++index, In, left, InIdx); if (index+1 < right) pRoot->_pRight = _ReBuildTree(pre, ++index, In, InIdx + 1, right); return pRoot; } BTNode* ReBuildTree(const vector<int>& pre, const vector<int>& In) { int index = 0; return _ReBuildTree(pre, index, In, 0, In.size()); } int main() { vector<int> v{ 1, 2, 3, -1,-1,-1,4, 5, -1,-1,6 }; int index = 0; BTNode* pRoot = CreateBinTree(v, index, -1); PreOrder(pRoot); PreOrderNor(pRoot); cout << endl; InOrder(pRoot); InOrderNor(pRoot); cout << endl; PostOrder(pRoot); PostOrderNor(pRoot); Destroy(pRoot); vector<int> Pre{ 1, 2, 3, 4, 5, 6 }; vector<int> In{3,2,1,5,4,6}; BTNode* pNewRoot = ReBuildTree(Pre, In); return 0; }