一、树1.1 树的定义树是一种非线性的数据结构它是由有限的集合组成具有层次的集合。是有一个特殊的节点根节点该节点之前在也没有节点。树是递归定义的。树是由根和子树构成。注意树形结构中子树之间不能有交集否则就不是树形结构。1.2 树的相关概念结点的度一个结点含有的子树的个数称为该结点的度叶结点或终端结点度为0的结点称为叶结点非终端结点或分支结点度不为0的结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点兄弟结点具有相同父结点的结点互称为兄弟结点树的度一棵树中最大的结点的度称为树的度结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次堂兄弟结点双亲在同一层的结点互为堂兄弟结点的祖先从根到该结点所经分支上的所有结点子孙以某结点为根的子树中任一结点都称为该结点的子孙。森林由mm0棵互不相交的树的集合称为森林1.3 树的表示树的表示既要表示父子之间关系又要存储本节点的值使用孩子兄弟表示法二、二叉树2.1 二叉树的基础概念二叉树是一个有限的节点的集合可以为空或者是有根节点和左子树和右子树。要求必须节点的度要小于等于2同时二叉树分左右子树所以称二叉树又为有向树。特殊的二叉树完全二叉树和满二叉树。完全二叉树假设树的高度为hh-1层都是满的但是h层并不是满的最后一层必须是从左到右连续的。满二叉树在完全二叉树的基础上h层叶结点也均是满的。2.二叉树的性质二叉树的根节点如果层次为1那么第i层中节点最多有2^(i-1)个节点深度为h的二叉树节点最多有2^h-1个。在二叉树中如果度为0的节点数为n0,度为1的节点数为n1度为2的节点数为n2则有以下关系n0n21。若规定根结点的层数为1具有N个结点的满二叉树的深度hlog2(N1),(log以2为底N1为对数的等式)对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0开始编号则对 于序号为i的结点有 1. 若i0i位置结点的双亲序号(i-1)/2i0i为根结点编号无双亲结点 2. 若2i1n,左孩子序号为2i12i1n,无左孩子。 3. 若2i2n右孩子序号为2i2;2i2n无右孩子。2.2 二叉树的存储方式二叉树的存储方式有两种数组存储和链式存储。数组存储从上面图中就可以看出普通的二叉树使用数组存储时就会空出空间造成浪费可以用但是不适合完全二叉树可以使用数组存储根据访问规律就可以找到目标节点。规律如果父亲下标为i,则左孩子下标为(2*i1),右孩子下标为2*i2如果孩子(不论是左孩子还是右孩子)的下标为i,则父亲的下标为i-1/ 2链式存储使用链表来进行存储二叉链表中要包含左孩子和右孩子的指针同时要包含该节点的数值三叉链表中在二叉链表的基础上同时保存了父亲节点的指针。2.3 二叉树数组存储的实现2.3.1 堆的基础概念二叉树中使用顺序存储的方式最好是完全二叉树/满二叉树。其中堆完全二叉树就是用数组存储的方式来存储数据。堆分为大堆和小堆大堆是指所有的父亲节点都要大于孩子节点就是大堆小堆是所有的父亲节点都要小于孩子节点。根据大堆和小堆的概念我们就可以知道大堆中根节点那个数一定是数组中最大的小堆中根节点的那个数一定是最小的。但是需要注意的是兄弟节点之间是没有大小关系的。2.3.2 堆的实现堆是是用数组存储方式来存储和顺序表定义的方式一模一样。先定一个这样的结构体。typedef int HPDataType; typedef struct Heap { HPDataType* arr; int capacity; int size; }HP;我们要实现的操作有堆的初始化、销毁堆的插入数据堆的删除数据返回堆中根节点的数据判断堆是否为空2.3.2.1 堆的初始化、销毁这个堆的初始化和销毁和顺序表的代码一样。void HeapInit(HP* ps) { assert(ps); ps-arr NULL; ps-size ps-capacity 0; } void HeapDestroy(HP* ps) { assert(ps); free(ps-arr); ps-arr NULL; ps-size ps-capacity 0; }2.3.2.2 堆的插入既然顺着双亲调整到合适的位置那么就需要一个算法向上调整。插入数据后拿数据和它的所有的祖先进行比较如果孩子小就往上调整将孩子和祖先进行交换。void swap(HPDataType* a, HPDataType* b) { int tmp *a; *a *b; *b tmp; } void AdaptUp(HPDataType* a, int child) { assert(a); int parent (child - 1) / 2; while (child 0) { if (a[parent] a[child]) { break; } swap(a[parent], a[child]); child parent; parent (child - 1) / 2; } } void HeapPush(HP* ps, HPDataType x) {//假设这个堆为小堆 assert(ps); assert(ps-size0); //再插入之前应先看看数组中有没有空间 if (ps-size ps-capacity) { //需要扩容 int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity; HPDataType* tmp (HPDataType*)realloc(ps-arr, sizeof(int) * newcapacity); if (tmp NULL) { perror(HeapPush::realloc fail); } ps-arr tmp; ps-capacity newcapacity; } //插入数据 ps-arr[ps-size] x; AdaptUp(ps-arr, ps-size-1); }向上调整的时间复杂度一个节点最多向上调整的次数是高度次也就是log2(N1),所以时间复杂度为 ologN。2.3.2.3 堆的删除对于删除根节点的数据我们应该将根节点数据和末尾的数据交换一下位置然后size--这样就能删除数据但是这样会破坏堆的结构所以我们就需要做一个向下调整的算法。向下调整算法中先进行左右孩子的比较找出最小者可以利用假设法然后再与父亲节点比较。void AdaptDown(HPDataType* a, int parent,int n) { assert(a); int child (2 * parent ) 1; while (child n) { //先比较左右孩子的大小 if (child 1 n a[child 1] a[child]) { child; } if (a[child] a[parent]) { swap(a[child], a[parent]); parent child; child (2 * parent) 1; } else { break; } } } void HeapPop(HP* ps) { assert(ps); //删除数据直接size--就可以了但是这种删除没有意义 //我们的目标是删除根节点的数据 swap((ps-arr[0]), (ps-arr[ps-size - 1])); ps-size--; AdaptDown(ps-arr, 0,ps-size); }向下调整的时间复杂度向下调整最多的次数是高度次也就是log2(N1),所以时间复杂度为 ologN。2.3.2.4 返回堆顶元素HPDataType HeapTop(HP* ps) { assert(ps); assert(ps-size 0); return ps-arr[0]; }2.3.2.5 判断堆是否为空bool HeapEmpty(HP* ps) { assert(ps); return ps-size 0; }通过堆的实现我们就可以完成打印的堆排序并不是真正的堆排序。我们首先要建堆使用堆这个数据结构来建堆。然后取堆顶元素并打印最后再进行堆删除的操作。void test1() { int a[] { 3,5,8,9,7,12,58,74,15 }; int len sizeof(a) / sizeof(a[0]); HP hp { 0 }; HPInit(hp); //先是一个堆建堆 for (int i 0; i len; i) { HPPush(hp, a[i]); } //打印堆排序并不是真正意义上的堆排序 while(!HPEmpty(hp)) { int ret HPTop(hp); printf(%d , ret); HPPop(hp); } HPDestroy(hp); }这种方式是在堆这个结构体里实现的排序并且并不是真正的排序数组里的元素并没有改变。下面将要讲一下真正的排序。2.3.3 堆的应用升序建大堆降序建小堆以降序建小堆为例整体思路是这样的我不从前往后排我是从后往前排先选出最小的数然后利用堆删除的思路当然不是真删除而是将不管那个数了将最大数与末尾数进行交换交换之后就不用管他了只需要管前N-1个数再调整一次找到次大的数再放到次末尾。最后按降序排出。升序建大堆的道理也是相通的。建堆建堆有两种方法向下调整建堆和向上调整建堆向上调整建堆将首元素就作为一个堆然后将数组之后的每个元素都进行向上调整最后建成堆。void test3() { //建堆 int a[] { 1,2,4,5,7,99,54,58,78 }; int len sizeof(a) / sizeof(a[0]); //向上调整建堆 for (int i 1; i len; i) { AdjustUp(a, a[i]); } }我们来讨论一下这个建堆的时间复杂度。通过计算向上调整算法建堆的时间复杂度为o(nlogn)。向下调整算法向下调整要从倒数第一个非叶子节点开始进行向下调整。直到最后一个根节点停止。void test3() { //建堆 int a[] { 3,5,8,9,7,12,58,74,15 }; int len sizeof(a) / sizeof(a[0]); //向下调整建堆 for (int i (len - 1 - 1) / 2; i 0; i--) { AdjustDown(a, i, len); } }我们来看看它的时间复杂度。通过计算向下调整算法建堆的时间复杂度为o(N)。通过二者比较可以看出向下调整算法比向上调整算法的更加效率高。所以我们建堆就可以使用向下调整算法。建堆以后我们就可以进行排序。void HeapSort(int* arr, int n) { int end n - 1; //建堆 for (int i (end - 1) / 2; i 0; i--) { AdjustDown(arr, i, n); } //排序 while (end 0) { swap(arr[0], arr[end]); AdjustDown(arr, 0, end); end--; } }Top-K问题再一串数组中找出最大或最小的前k个数。下面以找出最小的k个数为例void Topkmin(int* arr, int len, int k) { //建堆 for (int i (len - 1 - 1) / 2; i 0; i--) { AdjustDown(arr, i, len); } int end len - 1; while (k--) { swap(arr[0], arr[end]); printf(%d , arr[end]); AdjustDown(arr, 0, end); end--; } } void test4() { int a[] { 3,5,8,9,7,12,58,74,15 }; int len sizeof(a) / sizeof(a[0]); int k 0; scanf(%d, k); Topkmin(a, len, k); }这种方法能行当Nk时运行效率为O(N)。但是这个有一个致命的缺点。n个数求k个最大的数思路n个元素全部在文件中我们取文件中数据的前k个对这k个进行建小堆拿堆顶元素和其他n-k个数据进行比较如果若还有比堆顶元素还大的就进行交换。这样前k个元素就都是比其他n-k个数大的了就找出k个最大的数。#include stdlib.h #include stdio.h #include time.h //自己造的数据 void Createdata() { FILE* pf fopen(data.txt, w); if (pf NULL) { perror(fopen fail); exit(1); } for (int i 0; i 10000; i) { int data (rand()i)%10000; fprintf(pf, %d\n, data); } fclose(pf); pf NULL; } void test5() { //打开文件 FILE* pf fopen(data.txt, r); if (pf NULL) { perror(fopen fail); exit(1); } int k 0; scanf(%d, k); int* a (int*)malloc(sizeof(int) * k); for (int j 0; j k; j) { fscanf(pf, %d, a[j]); } //建小堆 for (int i (k - 2) / 2; i 0; i--) { AdjustDown(a, i, k); } int ret 0; for (int i k; i 10000; i) { fscanf(pf, %d, ret); //比较然后向下调整 if (a[0] ret) { swap(a[0], ret); AdjustDown(a, 0, k); } } //关闭文件 fclose(pf); pf NULL; //打印k个最大的数 for (int i 0; i k; i) { printf(%d , a[i]); } } int main() { srand((unsigned int)time(NULL)); Createdata(); test5(); return 0; }2.4 二叉树的链式存储在学习二叉树的操作时我们首先要创建一个二叉树我们可以首先使用最笨拙的方式自己来创建节点并且建立节点之间的联系。typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType val; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* ret (BTNode*)malloc(sizeof(BTNode)); ret-val x; ret-left ret-right NULL; return ret; } BTNode* CreateBinaryTree() { BTNode* node1 BuyNode(1); BTNode* node2 BuyNode(2); BTNode* node3 BuyNode(3); BTNode* node4 BuyNode(4); BTNode* node5 BuyNode(5); BTNode* node6 BuyNode(6); BTNode* node8 BuyNode(8); BTNode* node7 BuyNode(7); node1-left node2; node1-right node3; node2-left node4; node2-right node5; node3-left node6; node3-right node7; node5-right node8; return node1; } int main() { BTNode* rootCreateBinaryTree(); return 0; }2.4.1 二叉树的遍历递归遍历递归遍历分为前序遍历、中序遍历、后序遍历。前序遍历遍历顺序根、左子树、右子树。DFS - 深度优先遍历以上面二叉树为例首先从根开始然后遍历左子树而左子树又可以看成一颗完整的树所以继续被分为根、左子树和右子树。由大问题不断分割成小问题不断地逼近限制条件根为空指针。//前序遍历 void preOrder(BTNode* root) { if (root NULL) { printf(N ); return; } printf(%d , root-val); preOrder(root-left); preOrder(root-right); }中序遍历遍历顺序左子树、根、右子树。以上面二叉树为例//中序遍历 void inOrder(BTNode* root) { if (root NULL) { printf(N ); return; } inOrder(root-left); printf(%d , root-val); inOrder(root-right); }后序遍历遍历顺序左子树、右子树、根以上面的二叉树为例//后序遍历 void postOrder(BTNode* root) { if (root NULL) { printf(N ); return; } postOrder(root-left); postOrder(root-right); printf(%d , root-val); }非递归遍历层序遍历就属于非递归遍历。层序遍历BFS - 广度优先遍历层序遍历结合了队列进行遍历。队列的代码可以看一下文章栈和队列首先先将根节点入队然后出根节点同时将它的左右孩子依次入队。按照上一层带动下一层的思想进行考虑。同时空指针是不需要入队的。void LevelOrder(BTNode* root) { //队列中的节点元素类型为指针 Q q; //队列初始化 QInit(q); //根节点不为空才能入队列 if (root) { QueuePush(q, root); } while (!QIsEmpty(q)) { BTNode* top QueueTop(q); QueuePop(q); printf(%d , top-val); //不将空指针放入队列中 if (top-left) { QueuePush(q, top-left); } if (top-right) { QueuePush(q, top-right); } } //队列的销毁 QDestroy(q); }2.4.2 二叉树中的基础操作求节点个数求节点个数我们可以使用递归的方式分为两种情况根节点为空时那么节点的个数为0如果根节不为空那么节点个数就为左子树的节点个数加上右子树节点的个数1。再想为啥是递归呢因为求左子树的节点个数又可以将其看成一个子树再求其左子树的节点个数右子树的节点个数1。因此这是相似的问题又是将大问题 逐渐转化为小问题。//求二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root NULL) { return 0; } return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1; }求二叉树的高度求二叉树的高度我们求的高度一定是左子树和右子树之间中最大的高度1。分为以下几种情况1.根节点为空那么就返回02.根节点不为空就返回左右子树最大的那个树的高度1这里需要考虑的是我们能直接返回一个三目表达式比较左右子树的高度大小吗如下int BinaryTreeHeight(BTNode* root) { if (root NULL) { return 0; } // 重复递归计算左右子树高度大量冗余计算时间复杂度爆炸 return BinaryTreeHeight(root-left) BinaryTreeHeight(root-right) ? BinaryTreeHeight(root-left) 1 : BinaryTreeHeight(root-right) 1; }答案是不能的因为假设我们的树的高度只有2层比较一下左右子树的大小会进行递归调用但是算出最大的之后1由于没有存数据就会导致重新递归会出现效率问题。当二叉树的深度足够深时就会超出时间限制。//求二叉树的高度 int BinaryTreeHeight(BTNode* root) { if (root NULL) { return 0; } int leftHeight BinaryTreeHeight(root-left); int rightHeight BinaryTreeHeight(root-right); return leftHeight rightHeight ? leftHeight 1 : rightHeight 1; }求二叉树的叶子节点个数求叶子节点个数分为以下几种情况1.空树返回02.非空树如果左右孩子都是空指针说明为叶子节点返回1。如果以上都不满足那么就继续往下递归返回左右子树的叶子节点个数。//求叶子节点的个数 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); }求第 k 层的节点个数二叉树的问题想成根和子树的问题。求第 k 层的节点个数那么也就是求左子树相对于原二叉树 第 k 层的节点个数和右子树相对于原二叉树第 k 层节点个数之和。而求左 / 右子树相对于原二叉树第 k 层的节点个数相当于求左 / 右子树第 k-1 层的节点个数。逐渐缩小范围靠近限制条件k1时节点个数就是1空树节点个数就是0。思路1.空树返回02.非空树但k1:返回13.k 1 :返回左子树和右子树第 k-1层的节点个数。// 二叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root NULL) { return 0; } if (k 1) { return 1; } if (k 1) { return BinaryTreeLevelKSize(root-left, k-1) BinaryTreeLevelKSize(root-right, k-1); } }二叉树查找值为x的节点BTNode* BTNodeFind(BTNode* root, BTDataType x) { //空树就返回NULL if (root NULL) { return NULL; } //节点值相等就返回这个节点指针 if (root-val x) { return root; } //不为空树根节点值也不相等看其左右子树 //如果能找到那么返回值不为NULL BTNode* ret1BTNodeFind(root-left, x); if (ret1) { return ret1; } BTNode* ret2 BTNodeFind(root-right, x); if (ret2) { return ret2; } //如果都不满足那么就找不到,返回NULL return NULL; }2.4.3 二叉树的基础oj题单值二叉树bool _isUnivalTree(struct TreeNode* root, int val) { if (root NULL) { return true; } if (root-val ! val) { return false; } return _isUnivalTree(root-left, val) _isUnivalTree(root-right, val); } bool isUnivalTree(struct TreeNode* root) { return _isUnivalTree(root, root-val); }相同二叉树bool isSameTree(struct TreeNode* p, struct TreeNode* q) { if(pNULL qNULL) { return true; } if (pNULL || qNULL) { return false; } if(p-val!q-val) { return false; } return isSameTree(p-left,q-left) isSameTree(p-right,q-right); }二叉树的前序遍历int TreeSize(struct TreeNode* root) { return rootNULL? 0 :TreeSize(root-left) TreeSize(root-right) 1; } void preOrder(struct TreeNode* root,int* a,int* pi) { if(rootNULL) { return; } a[(*pi)]root-val; preOrder(root-left,a,pi); preOrder(root-right,a,pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize) { int sizeTreeSize(root); *returnSizesize; int* a(int* )malloc(sizeof(int)*(*returnSize)); int i0; preOrder(root,a,i); return a; }需要注意的两点在oj题中returnSize是指向数组大小的指针也叫输出型参数。在前序遍历时要将值放入数组中需要传数组大小的参数但是不能传值因为在一个函数栈帧中 i 值的改变并不能改变其他函数栈帧中的值。对称二叉树bool _isSymmetric(struct TreeNode* p,struct TreeNode* q) { if(pNULL qNULL) { return true; } if(pNULL || qNULL) { return false; } if(p-val ! q-val) { return false; } return _isSymmetric(p-left,q-right) _isSymmetric(p-right,q-left); } bool isSymmetric(struct TreeNode* root) { if(root NULL) { return true; } return _isSymmetric(root-left,root-right); }另一棵树的子树bool IsSameTree(struct TreeNode* p,struct TreeNode* q) { if(pNULL qNULL) { return true; } if(pNULL || qNULL) { return false; } if(p-val !q-val) { return false; } return IsSameTree(p-left,q-left) IsSameTree(p-right,q-right); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if(rootNULL subRootNULL) { return true; } if(rootNULL || subRootNULL) { return false; } if(root-val subRoot-val) { if(IsSameTree(root,subRoot)) { return true; } } return isSubtree(root-left,subRoot) || isSubtree(root-right,subRoot); }2.4.4 二叉树的创建和销毁判断是否为完全二叉树首先要想完全二叉树的特点前 h-1 层为满的二叉树最后一层节点数可能满也可能不满但是节点一定从左到右是连续的。我们怎么样才能知道从左到右是连续的呢当说到从左到右我们可以想到层序遍历它就是每一层从左到右遍历当我们遍历到第一个空时分为两种情况1.队列中全部是空没有非空节点那么这就是完全二叉树。2.队列中存在非空节点那么就不是非空节点。是否存在已经遍历到第一个空节点但是下一层还有的非空节点并没有入队列答案是不存在的。因为第一个空节点后面的非空节点的根节点一定是空节点之前的非空节点已经遍历到空节点说明前面的非空节点已经出队列了而出队列必定他们下一层的孩子就已经入队列里了。所以不存在。// 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Q q; QInit(q); QueuePush(q, root); while (!QIsEmpty(q)) { BTNode* top QueueTop(q); QueuePop(q); //遇到第一个空就停止,如果队列中还有非空节点那么就不是完全二叉树 if (top NULL) { break; } QueuePush(q,top-left); QueuePush(q,top-right); } while (!QIsEmpty(q)) { BTNode* top QueueTop(q); QueuePop(q); if (top ! NULL) { QDestroy(q); return false; } } QDestroy(q); return true; }二叉树的构建与遍历#include stdio.h #include stdlib.h typedef char BTDateType; typedef struct BinaryTreeNode { BTDateType val; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; void inOrder(BTNode* root) { if(root NULL) { return; } inOrder(root-left); printf(%c ,root-val); inOrder(root-right); } BTNode* CreateBinaryTree(BTDateType* a,int* pi) { if(a[*pi] #) { (*pi); return NULL; } BTNode* root(BTNode*)malloc(sizeof(BTNode)); root-vala[*pi]; (*pi); root-leftCreateBinaryTree(a, pi); root-rightCreateBinaryTree(a, pi); return root; } int main() { char a[100]; //输入 scanf(%s,a); //输出 //1.前序遍历的方法建立二叉树 int i0; BTNode* rootCreateBinaryTree(a,i); //2.中序遍历 inOrder(root); return 0; }这里和前序遍历一样一定要注意穿过数组的大小必须是是指针控制否则无效。二叉树的销毁//二叉树的销毁 void BinaryTreeDestroy(BTNode* root) { if (root NULL) { return; } BinaryTreeDestroy(root-left); BinaryTreeDestroy(root-right); free(root); }三、 总结这节花费了好长时间整理收藏起来多看几遍每一遍都会有不一样的收获如果有不对的地方请及时指出我会及时更正。