怎么查看网站快照,自己搭建公司网站,百度小说网,怎么建设QQ网站文章目录 前言树和森林基础概念二叉树二叉树的遍历二叉树的构造树和森林与二叉树之间的转化树和森林的遍历 满二叉树完全二叉树线索二叉树线索二叉树的构造寻找前驱和后继线索二叉树的遍历 最优二叉树#xff08;哈夫曼树#xff09;哈夫曼树的构造哈夫曼编码 二叉排序树哈夫曼树哈夫曼树的构造哈夫曼编码 二叉排序树BST二叉排序树的插入二叉排序树的构造二叉排序树的查找二叉排序树的删除 平衡二叉树AVL平衡二叉树失衡调整平衡二叉树的插入平衡二叉树的删除 红黑树红黑树的插入红黑树的删除 B树B树的插入B树的删除B树的查找 B树 前言
本文所有代码均在仓库中这是一个完整的由纯C语言实现的可以存储任意类型元素的数据结构的工程项目。 首先是极好的工程意识该项目是一个中大型的CMake项目结构目录清晰通过这个项目可以遇见许多工程问题并且可以培养自己的工程意识。其次是优秀的封装性每个数据结构的头文件中只暴漏少量的信息以及优秀的代码风格和全面的注释通过这个项目可以提升自己的封装技巧 异常处理功能在使用C语言编写代码的时候不能使用类似Java的异常处理机制是非常难受的所以我也简单实现了一下。详情可看在C语言中实现类似面向对象语言的异常处理机制 最后也是最重要的一点数据结构的通用性和舒适的体验感下面以平衡二叉树为例
第一步要想使用平衡二叉树只需要引入其的头文件
#include tree-structure/balanced-binary-tree/BalancedBinaryTree.h第二步定义自己任意类型的数据并构造插入数据以一个自定义的结构体为例
#include tree-structure/balanced-binary-tree/BalancedBinaryTree.hint dataCompare(void *, void *);typedef struct People {char *name;int age;
} *People;int main(int argc, char **argv) {struct People dataList[] {{张三, 15},{李四, 3},{王五, 7},{赵六, 10},{田七, 9},{周八, 8},};BalancedBinaryTree tree balancedBinaryTreeConstructor(NULL, 0, dataCompare);for (int i 0; i 6; i) {balancedBinaryTreeInsert(tree, dataList i, dataCompare);}return 0;
}/*** 根据人的年龄比较*/
int dataCompare(void *data1, void *data2) {int sub ((People) data1)-age - ((People) data2)-age;if (sub 0) {return 1;} else if (sub 0) {return -1;} else {return 0;}
}第三步打印一下平衡二叉树
#include tree-structure/balanced-binary-tree/BalancedBinaryTree.hint dataCompare(void *, void *);void dataPrint(void *);typedef struct People {char *name;int age;
} *People;int main(int argc, char **argv) {struct People dataList[] {{张三, 15},{李四, 3},{王五, 7},{赵六, 10},{田七, 9},{周八, 8},};BalancedBinaryTree tree balancedBinaryTreeConstructor(NULL, 0, dataCompare);for (int i 0; i 6; i) {balancedBinaryTreeInsert(tree, dataList i, dataCompare);balancedBinaryTreePrint(tree, dataPrint);printf(-------------\n);}return 0;
}/*** 根据人的年龄比较*/
int dataCompare(void *data1, void *data2) {int sub ((People) data1)-age - ((People) data2)-age;if (sub 0) {return 1;} else if (sub 0) {return -1;} else {return 0;}
}/*** 打印人的年龄* param data*/
void dataPrint(void *data) {People people (People) data;printf(%d, people-age);
}打印的结果如下 最后期待大佬们的点赞。
树和森林基础概念
树是由 n n n个结点组成的有限集其中每个结点有零个或多个子结点以及零个或一个父结点没有父结点的结点称为根结点每一个非根结点有且只有一个父结点。除根结点外的其余结点可以分为 m m m个互不相交的有限集其中每个有限集本身就是一棵树这些树又称为根的子树。森林就是 m m m棵不相交的树的集合树一定是森林但森林不一定是树。
结点间的关系A是E的祖先E是A的子孙A是B的双亲B是A的孩子有相同双亲的结点称为兄弟。度一个结点的孩子数称为该结点的度树中结点最大的度称为树的度。度数为零的结点称为叶子结点度不为零的结点称为分支结点。 树中的结点数就等于所有结点的度数之和加一。度为 m m m的树第 i i i层最多有 m i − 1 m^{i-1} mi−1个结点。 m m m叉树任意结点的度小于 m m m的树层次结点的层次从根结点开始定义在同一层的非兄弟结点互为堂兄弟。深度结点的深度从根结点开始向下逐层累加树的深度就是结点的最大层数。高度结点的高度从叶子节点开始向上逐层累加树的高度就是结点的最大层数。 高度为 h h h的 m m m叉树至多有 m h − 1 m − 1 \frac{m^h-1}{m-1} m−1mh−1个结点最少有 h h h个结点。高度为 h h h、度为 m m m的树至少有 h m − 1 hm-1 hm−1个结点。具有 n n n个结点的 m m m叉树的最小高度为 ⌈ l o g m ( n ( m − 1 ) 1 ) ⌉ \lceil log_m(n(m-1)1)\rceil ⌈logm(n(m−1)1)⌉。 结点的间的路径和路径长度结点间的路径由这两个结点之间所经过的结点序列构成路径长度是路径上所经过的边的条数。树的路径长度为根到每个结点的路径长度之和。有序树和无序树结点的每个子树是有序的不能互换的树称为有序树否则就是无序树。 树一般有以下三种存储方式
顺序存储双亲表示法顺序链式存储孩子表示法链式存储孩子兄弟表示法
双亲表示法采用一组连续的空间存储每一个结点同时在每个结点中增设一个伪指针这个伪指针指向其双亲结点在连续空间中的位置 struct ParentTreeNode {void *data;int parent;
};struct ParentTree {struct ParentTreeNode *nodeList;int size;int nodeCount;
};在孩子表示法中每个结点不再增设一个伪指针而是增设一个存储当前结点孩子下标的链表 struct ChildTreeNode {void *data;int index; //表示当前接结点在数组中的位置仅在链表中使用struct ChildTreeNode *child;
};struct ChildTree {struct ChildTreeNode *nodeList;int size;int nodeCount;
};孩子兄弟表示法又称为二叉树表示法它采用二叉链表作为树的存储结构其中每个结点包含三部分内容结点值、指向第一个孩子结点的指针以及指向下一个兄弟结点的指针 struct ChildSiblingTreeNode {void *data;struct ChildSiblingTreeNode *firstChild;struct ChildSiblingTreeNode *nextSibling;
};二叉树
二叉树是指每个结点最多只有两棵子树且子树之间顺序不能颠倒的树这两棵子树分别称为左子树和右子树。二叉树与度为 2 2 2的有序树的区别如下
度为 2 2 2的有序树至少有三个结点而二叉树可以为空树。度为 2 2 2的有序树的孩子的左右次序是相对于另一个孩子而言的如果只有一个孩子那么无需区分左右而二叉树无论几个孩子必须区分左右。
二叉树的性质如下 二叉树在第 i i i层至多有 2 i − 1 2^{i-1} 2i−1个结点最少有 1 1 1个结点。 高度为 h h h的二叉树最多有 2 h − 1 2^h-1 2h−1个结点。 设非空二叉树中度为 0 、 1 、 2 0、1、2 0、1、2的结点的个数分别为 n 1 、 n 2 、 n 3 n_1、n_2、n_3 n1、n2、n3设树中结点的总个数为 n n n则 n n 0 n 1 n 2 nn_0n_1n_2 nn0n1n2 n n 1 2 n 2 1 nn_12n_21 nn12n21 n 0 n 2 1 n_0n_21 n0n21 对于任意一颗二叉树如果对其进行编号那么结点编号所对应的二进制可以反应从根节点到该结点的路径其中最高位是 1 1 1其余各位从高到低表示从根节点到第 k k k个节点的移动方向 0 0 0表示移动到左子节点 1 1 1表示移动到右子节点。 二叉树的顺序存储是指用一组地址连续的存储单元依次自上而下、自左向右存储完全二叉树上的结点元素这样树中结点的序号就可以唯一反应结点之间的关系。对于不是完全二叉树的二叉树需要填充空结点让其每个结点与完全二叉树上的结点对应。因此非完全二叉树的二叉树通常采用链式存储链表结点至少包含三个域数据域、左孩子指针域和右孩子指针域。还可以增加一个指针域指向其双亲。
struct BinaryTreeNode {void *data;struct BinaryTreeNode *lNode;struct BinaryTreeNode *rNode;
};二叉树的遍历
遍历一棵二叉树要决定对根节点N、、左子树L和右子树R的访问顺序常见的访问顺序如下
先序遍历NLR首先访问根结点然后遍历左子树最后遍历右子树。
void preOrder(BinaryTree tree, LinkedQueue preOrderList) {if (tree ! NULL) {linkedQueueEnQueue(preOrderList, tree-data);preOrder(tree-lNode, preOrderList);preOrder(tree-rNode, preOrderList);}
}中序遍历LNR先遍历左子树然后访问根结点然后遍历右子树。
void inOrder(BinaryTree tree, LinkedQueue inOrderList) {if (tree ! NULL) {inOrder(tree-lNode, inOrderList);linkedQueueEnQueue(inOrderList, tree-data);inOrder(tree-rNode, inOrderList);}
}后序遍历LRN是先遍历左子树然后遍历右子树最后访问根结点。
void postOrder(BinaryTree tree, LinkedQueue postOrderList) {if (tree ! NULL) {postOrder(tree-lNode, postOrderList);postOrder(tree-rNode, postOrderList);linkedQueueEnQueue(postOrderList, tree-data);}
}层序遍历根据二叉树的层次层次结构从第一层开始自上而下、自左向右访问每一个结点。
void levelOrder(BinaryTree tree, LinkedQueue levelOrderList) {LinkedQueue queue linkedQueueConstructor();linkedQueueEnQueue(queue, tree);while (!linkedQueueIsEmpty(queue)) {BinaryTreeNode *node linkedQueueDeQueue(queue);linkedQueueEnQueue(levelOrderList, node-data);if (node-lNode ! NULL) {linkedQueueEnQueue(queue, node-lNode);}if (node-rNode ! NULL) {linkedQueueEnQueue(queue, node-rNode);}}
}二叉树的构造
由二叉树的以下遍历序列组合可以唯一确认一棵二叉树
先序中序后序中序层序中序
BinaryTree binaryTreePreInOrderConstructor(void **preOrderList, void **inOrderList, int (*compare)(void *, void *), int ps, int pe, int is, int ie) {BinaryTreeNode *root malloc(sizeof(BinaryTreeNode));root-data *(preOrderList ps);int lLen, rLen;for (int i is; i ie; i) {if (compare(*(inOrderList i), *(preOrderList ps))) {lLen i - is;rLen ie - i;break;}}if (lLen) {root-lNode binaryTreePreInOrderConstructor(preOrderList, inOrderList, compare, ps 1, ps lLen, is, is lLen - 1);} else {root-lNode NULL;}if (rLen) {root-rNode binaryTreePreInOrderConstructor(preOrderList, inOrderList, compare, pe - rLen 1, pe, ie - rLen 1, ie);} else {root-rNode NULL;}return root;
}如果将二叉树的某一遍历序列使用填充元素填充为满二叉树的相同遍历序列那么也可以唯一确定一棵二叉树
BiTree completeLevelOrderConstruct(BiTreeElemType completeLevelOrderList[],int len,BiTreeElemType filler){LinkQueue queue linkQueueConstruct();BiTNode * root malloc(sizeof (BiTNode));root-datacompleteLevelOrderList[0];enQueue(queue,root);for (int i 1; !isEmpty(queue); i) {BiTNode * nodedeQueue(queue);if(node!NULL){if((2*1-1)len||(2*i1-1)len){node-lChildNULL;node-rChildNULL;continue;}if(completeLevelOrderList[2*i-1]!filler){node-lChild malloc(sizeof (BiTNode));node-lChild-datacompleteLevelOrderList[2*i-1];enQueue(queue,node-lChild);} else{node-lChildNULL;enQueue(queue,NULL);}if(completeLevelOrderList[2*i1-1]!filler){node-rChild malloc(sizeof (BiTNode));node-rChild-datacompleteLevelOrderList[2*i1-1];enQueue(queue,node-rChild);} else{node-rChildNULL;enQueue(queue,NULL);}} else{continue;}}linkQueueFinalize(queue);return root;
}树和森林与二叉树之间的转化
由于二叉树的结构简单、规律性最强因此在处理树和森林时一般将它们转换成一个唯一的二叉树进行。由于树和二叉树都可以使用二叉链表表示那么就可以以二叉链表做媒介来进行转化。 树转换为二叉树每个结点左指针指向它的第一个孩子右指针指向它在树中的相邻右兄弟由于根节点没有兄弟所以对应的二叉树没有右子树。 树转换为二叉树的画法在兄弟结点之间加一条线对每一个结点只保留它与第一个孩子的连线与其它孩子的连线全部抹掉以树根为中心顺时针旋转四十五度。 森林转换为二叉树先将森林中的每一棵树转换为二叉树然后将第二棵二叉树作为第一棵二叉树的右子树再将第三棵二叉树作为第二棵二叉树的右子树···依次类推。 森林转换为二叉树的画法将森林中的每一棵树转换为二叉树每棵树的根视为兄弟关系在每棵树的根之间加一条连线以第一棵树的根为中心顺时针旋转四十五度。 二叉树转换为森林将二叉树的根及左子树视为第一棵树的二叉树形式并将右链断开将右子树视为一个由除第一棵树外的森林转换后的二叉树应用相同的方法直到最后只剩一棵没有右子树的二叉树为止最后将每棵二叉树依次转换为树就得到了森林。
树和森林的遍历
树的遍历方式如下
先根遍历先访问根结点再依次访问根结点的每棵子树依次类推。其遍历序列对应二叉树的先序序列。后根遍历先访问根结点的每棵子树再访问根结点依次类推。其遍历序列对应二叉树的中序序列。层序遍历按层次访问。
森林的遍历方式如下
先根遍历访问森林中第一棵树的根节点先根遍历第一棵树中根结点的子树森林先根遍历除去第一棵树之后剩余的树构成的森林其遍历序列对应二叉树的先序序列。后根遍历后根遍历森林中第一棵树的根结点的子树森林访问第一棵树根结点后根遍历除第一棵树之后剩余的树构成的森林其遍历序列对应二叉树的中序序列。层序遍历按层次遍历。
满二叉树
每一层的结点数都达到最大值的二叉树称为满二叉树满二叉树的性质如下
所有叶子节点都在最后一层。一棵高为 h h h的满二叉树的结点数为 2 h − 1 2^h-1 2h−1。不存在度为 1 1 1的结点。若对满二叉树自上而下自左到右从 1 1 1开始编号那么对于编号为 i i i的结点若有双亲则其双亲编号为 ⌊ i / 2 ⌋ \lfloor i/2\rfloor ⌊i/2⌋若有左孩子则左孩子编号为 2 i 2i 2i若有右孩子则其编号为 2 i 1 2i1 2i1。 完全二叉树
一棵深度为 k k k的有 n n n个结点的二叉树对树中的结点自上而下自左到右从 1 1 1开始编号如果编号为 i i i的结点与满二叉树中编号为 i i i的结点在二叉树中的位置相同则这棵二叉树称为完全二叉树。完全二叉树的性质如下
若 i ⌊ n / 2 ⌋ i⌊n/2⌋ i⌊n/2⌋那么结点 i i i为分支结点否则为叶子结点。叶子节点只可能在层次最大的两层上出现对于最大层次中的叶子结点都依次排列在该层的最左边的位置。若有度为 1 1 1的结点则只可能有一个且该结点只有左孩子而没有右孩子。一但某结点 i i i为叶子结点或只有左孩子则编号大于 i i i的结点均为叶子结点。若 n n n为奇数则每个分支结点都有左孩子和右孩子若 n n n为偶数则编号最大的分支结点只有左孩子没有右孩子其余分支结点左孩子右孩子都有。当 i i i为偶数时其双亲的编号为 i / 2 i/2 i/2它是双亲的左孩子当 i i i为奇数时其双亲的编号为 ( i − 1 ) / 2 (i-1)/2 (i−1)/2它是双亲的右孩子。当 2 i n 2in 2in时结点i的左孩子编号为 2 i 2i 2i否则无左孩子。当 2 i 1 n 2i1n 2i1n时结点i的右孩子编号为 2 i 1 2i1 2i1否则无右孩子。结点 i i i所在的层次为 ⌊ l o g 2 i ⌋ 1 ⌊log₂i⌋1 ⌊log2i⌋1。具有 n n n个结点的完全二叉树的高度为 ⌈ l o g 2 ( n 1 ) ⌉ ⌈log₂(n1)⌉ ⌈log2(n1)⌉或 ⌊ l o g 2 n ⌋ 1 ⌊log₂n⌋1 ⌊log2n⌋1。 线索二叉树
在含有 n n n个结点的二叉树中含有 n 1 n1 n1个空指针域。线索化是指利用这些空指针域存放指向结点的前驱和后继的指针它的规则如下
如果某个结点的左孩子为空则将空的左孩子引用指向其前驱如果某结点的右孩子为空则将空的右孩子引用指向其后驱。
此外还需要增加两个标志位标识指针域是指向左右孩子还是指向前驱后继最好再添加一个指针域指向其父结点。
struct ThreadedBinaryTreeNode {void *data;ThreadedBinaryTreeNode *lNode;ThreadedBinaryTreeNode *rNode;ThreadedBinaryTreeNode *pNode;bool lIsPredecessor;bool rIsSuccessor;
};线索二叉树的构造
构造一棵线索二叉树分为两步
首先使用普通二叉树的构造方法构造一棵ThreadTree然后使用线索化方法将ThreadTree转换成一个真正的线索二叉树
以前序线索化为例它的算法思想为
本质是一次前序遍历设tree指针指向当前访问的结点predecessor指针指向tree的前驱在遍历时 检查tree的左指针是否为空若为空则将其指向predecessor检查predecessor 的右指针是否为空若为空则将其指向tree
/*** 先序线索化* param tree* param predecessor* return*/
ThreadedBinaryTree preOrderThreaded(ThreadedBinaryTree tree, ThreadedBinaryTreeNode *predecessor) {if (tree ! NULL) {if (tree-lNode NULL) {tree-lNode predecessor;tree-lIsPredecessor true;}if (predecessor ! NULL predecessor-rNode NULL) {predecessor-rNode tree;predecessor-rIsSuccessor true;}predecessor tree;if (tree-lIsPredecessor false) {preOrderThreaded(tree-lNode, predecessor);}if (tree-rIsSuccessor false) {preOrderThreaded(tree-rNode, predecessor);}}
}寻找前驱和后继
以前序线序哦二叉树为例寻找tree结点前驱的算法思想如下
如果tree-lIsPredecessor true则直接返回其左孩子若tree的左孩子不指向其前驱 若tree是其父结点的左孩子则直接返回其父结点若tree是其父结点的右孩子 若父结点没有左孩子则直接返回父结点若父结点有左孩子则返回父结点左子树中按照前序序列访问到的最后一个结点
/*** 寻找前序序列的前驱* param tree* return*/
ThreadedBinaryTreeNode *preOrderFirstNode(ThreadedBinaryTree tree) {if (tree-lIsPredecessor true) {return tree-lNode;} else {ThreadedBinaryTreeNode *parent tree-pNode;if (parent-lNode tree) {return parent;} else {if (parent-lIsPredecessor true || parent-lNode NULL) {return parent;} else {ThreadedBinaryTreeNode *node parent-lNode;while (node ! NULL) {if (node-rNode tree) {break;} else if (node-rNode ! NULL) {node node-rNode;} else if (node-lIsPredecessor false node-lNode ! NULL) {node node-lNode;}}return node;}}}
}寻找后继的算法思想如下
如果tree-rIsSuccessor true则直接返回其右孩子若tree的右孩子不指向其后继 如果 tree-lIsPredecessor false tree-lNode ! NULL返回其左孩子否则返回其右孩子
/*** 寻找前序序列的后继* param tree* return*/
ThreadedBinaryTreeNode *preOrderNextNode(ThreadedBinaryTree tree) {if (tree-rIsSuccessor true) {return tree-rNode;} else {if (tree-lIsPredecessor false tree-lNode ! NULL) {return tree-lNode;} else {return tree-rNode;}}线索二叉树的遍历
以前序线序哦二叉树为例前序线索二叉树中包含了二叉树的前驱和后继的信息在对其进行遍历时只需要找到前序序列中的第一个结点然后依次找结点的后继直至其后继为空。
/*** 线索二叉树前序遍历* param tree* param queue*/
void threadedBinaryTreePreOrder(ThreadedBinaryTree tree, LinkedQueue queue) {for (ThreadedBinaryTreeNode *node tree; node ! NULL; node preOrderNextNode(node)) {linkedQueueEnQueue(queue, node-data);}
}最优二叉树哈夫曼树
如果给树中结点赋一个有某种含义的数值则这个数值称为该结点的权。结点的权和根结点到该结点的路径长度的乘积称为结点的带权路径长度树的带权路径长度是树中所有叶子节点带权路径长度之和。带权路径长度最小的二叉树称为最优二叉树。最优二叉树的特点如下
包含 n n n个叶子节点的最优二叉树共有 2 n − 1 个 2n-1个 2n−1个结点。最优二叉树结点的度要么是 0 0 0要么是 2 2 2。
struct HuffmanTreeNode {void *data;void *weight;struct HuffmanTreeNode *lNode;struct HuffmanTreeNode *rNode;
};哈夫曼树的构造
给定 n n n个结点以及它们的权值那么构造过程如下
构造森林全是根将这 n n n个结点分别作为 n n n棵仅包含一个结点的二叉树构成森林 F F F。选用两小造新树构造一个新结点在 F F F中选择两棵根结点权值最小的树作为新结点的左右子树新结点权值即为两个孩子节点的权值之和。删除两小添新人从 F F F中删除刚才选出的两棵树并将新构造的二叉树加入 F F F。重复2、3剩单根重复2和3步直至F中只剩一棵树。
/*** 构造哈夫曼树* param dataList 数据列表* param weightList 权值列表* param size 大小* param reCompare 权值逆序比较* param weightSum 权值相加* return*/
HuffmanTree huffmanTreeNodeConstructor(void *dataList[], void *weightList[], int size, int (*reCompare)(void *, void *), void *(*weightSum)(void *, void *)) {HuffmanTreeNode *forest[size];int treeCount 0;for (int i 0; i size; i) {HuffmanTreeNode *node malloc(sizeof(HuffmanTreeNode));node-data dataList[i];node-weight weightList[i];node-lNode NULL;node-rNode NULL;forest[i] node;treeCount;}sorted(forest, size, reCompare);for (; treeCount ! 1;) {HuffmanTreeNode *node malloc(sizeof(HuffmanTreeNode));node-lNode forest[0];forest[0] NULL;treeCount--;node-rNode forest[1];forest[1] NULL;treeCount--;node-data NULL;node-weight weightSum(node-lNode-weight, node-rNode-weight);forest[0] node;sorted(forest, size, reCompare);}return forest[0];
}哈夫曼编码
由哈夫曼树可以得到哈夫曼编码
首先将一段文本中每个出现的字符当作一个独立的结点构造成哈夫曼树每个字符都会出现在叶子结点其权值为它出现的频度然后在每条路径上标记 0 0 0和 1 1 1标记为 0 0 0表示转向左孩子标记为 1 1 1表示转向右孩子。那么字符的哈夫曼编码就为从根结点到该结点的路径上边标记的 01 01 01序列。哈夫曼树的带权路径长度就是该文本最终编码得到的二进制编码长度。
/*** 是否是叶子结点* param node* return*/
static bool isLeafNode(HuffmanTreeNode *node) {return node-lNode NULL node-rNode NULL;
}/*** 哈夫曼编码* param tree* param target* param compare* return*/
char *huffmanCoding(HuffmanTree tree, void *target, int (*compare)(void *, void *)) {if (tree ! NULL) {char *lr huffmanCoding(tree-lNode, target, compare);char *rr huffmanCoding(tree-rNode, target, compare);if (lr ! NULL) {char *code calloc(strlen(lr) 2, sizeof(char));strcat(code, 0);strcat(code, lr);return code;} else if (rr ! NULL) {char *code calloc(strlen(rr) 2, sizeof(char));strcat(code, 1);strcat(code, rr);return code;} else if (tree-lNode ! NULL isLeafNode(tree-lNode) compare(tree-lNode-data, target) 0) {return 0;} else if (tree-rNode ! NULL isLeafNode(tree-rNode) compare(tree-rNode-data, target) 0) {return 1;} else {return NULL;}} else {return NULL;}
}二叉排序树BST
二叉排序树是满足以下性质的二叉树
若任意结点的左子树不空则左子树上所有结点的值均小于它的根结点的值若任意结点的右子树不空则右子树上所有结点的值均大于它的根结点的值任意结点的左、右子树也分别为二叉排序树
对二叉排序树进行中序遍历可以得到一个递增有序的有序序列。
struct SortedBinaryTreeNode {void *data;SortedBinaryTreeNode *lNode;SortedBinaryTreeNode *rNode;
};二叉排序树的插入
算法思想
若树为空则新建根结点若树非空则插入值与根结点值比较 若相等则插入失败若小于根结点值则插入到左子树若大于根结点值则插入到右子树
/*** 二叉排序树的插入* param tree* param element* param compare* return*/
bool sortedBinaryTreeInsert(SortedBinaryTree *tree, void *element, int (*compare)(void *, void *)) {if ((*tree) NULL) {*tree malloc(sizeof(SortedBinaryTreeNode));(*tree)-data element;(*tree)-lNode NULL;(*tree)-rNode NULL;return true;} else {int cmpResult compare(element, (*tree)-data);if (cmpResult 0) {return false;} else if (cmpResult 0) {if ((*tree)-rNode NULL) {SortedBinaryTreeNode *node malloc(sizeof(SortedBinaryTreeNode));node-data element;node-rNode NULL;node-rNode NULL;(*tree)-rNode node;return true;} else {return sortedBinaryTreeInsert((*tree)-rNode, element, compare);}} else {if ((*tree)-lNode NULL) {SortedBinaryTreeNode *node malloc(sizeof(SortedBinaryTreeNode));node-data element;node-rNode NULL;node-rNode NULL;(*tree)-lNode node;return true;} else {return sortedBinaryTreeInsert((*tree)-lNode, element, compare);}}}
}二叉排序树的构造
/*** 二叉排序树构造函数* param elementList* param size* param compare* return*/
SortedBinaryTree sortedBinaryTreeConstructor(void **elementList, int size, int (*compare)(void *, void *)) {static SortedBinaryTree tree NULL;for (int i 0; i size; i) {sortedBinaryTreeInsert(tree, *(elementList i), compare);}return tree;
}二叉排序树的查找
算法思想
若树非空则目标值与根结点值比较若相等则查找成功若小于根结点值则在左子树上查找若大于根结点值则在右子树上查找
/*** 二叉排序树的查找* param tree* param element* param compare* return*/
SortedBinaryTreeNode *sortedBinaryTreeSearch(SortedBinaryTree tree, void *element, int (*compare)(void *, void *)) {if (tree NULL) {return NULL;} else {int cmpResult compare(element, tree-data);if (cmpResult 0) {return tree;} else if (cmpResult 0) {return sortedBinaryTreeSearch(tree-rNode, element, compare);} else {return sortedBinaryTreeSearch(tree-lNode, element, compare);}}
}二叉排序树的删除
算法思想
首先找到要删除的结点。若删除结点是叶子结点则直接删除。若删除结点只有左子树或者右子树则让左子树或右子树替代删除结点。若若删除结点左右子树都存在 方法一找到右子树中最小的值替代删除结点的值然后再删除这个最小值所在的结点。方法二找到左子树中最大的值替代删除结点的值然后再删除这个最大值所在的结点。
/*** 删除元素* param tree* param element* param compare* return*/
bool sortedBinaryTreeDelete(SortedBinaryTree *tree, void *element, int (*compare)(void *, void *)) {if (*tree NULL) {return false;} else {int cmpResult compare(element, (*tree)-data);if (cmpResult 0) {if ((*tree)-lNode NULL (*tree)-rNode NULL) {free(*tree);*tree NULL;return true;} else if ((*tree)-lNode NULL) {SortedBinaryTreeNode *node (*tree);*tree (*tree)-rNode;free(node);return true;} else if ((*tree)-rNode NULL) {SortedBinaryTreeNode *node (*tree);*tree (*tree)-lNode;free(node);return true;} else {SortedBinaryTreeNode *node (*tree)-rNode;while (node-lNode ! NULL) {node node-lNode;}(*tree)-data node-data;return sortedBinaryTreeDelete((*tree)-rNode, node-data, compare);}} else if (cmpResult 0) {return sortedBinaryTreeDelete((*tree)-rNode, element, compare);} else {return sortedBinaryTreeDelete((*tree)-lNode, element, compare);}}
}平衡二叉树AVL
结点的平衡因子定义如下 平衡因子 左子树高 − 右子树高 平衡因子左子树高-右子树高 平衡因子左子树高−右子树高 树中任一结点的平衡因子的绝对值不超过 1 1 1的二叉树称为平衡二叉树平衡二叉树避免了树高的过度增长如果可以保证一棵二叉排序树为平衡二叉树那么就可以减少搜索元素时比较的次数从而提高二叉排序树的性能。
struct BalancedBinaryTreeNode {void *data;BalancedBinaryTreeNode *lNode;BalancedBinaryTreeNode *rNode;
};平衡二叉树失衡调整
当对一棵平衡二叉树进行插入或删除操作时有可能会导致平衡二叉树失衡此时应该从插入或删除结点往回找到第一个不平衡结点调整以该结点为根的子树这棵被调整的树称为最小不平衡子树。平衡二叉树的失衡类型有以下四种针对不同的类型有不同的调整策略。
LL平衡旋转B结点带左子树代替A成为根结点A结点带右子树成为B的右子树B结点原来的右子树作为A的左子树。
void ll(BalancedBinaryTree *tree) {BalancedBinaryTreeNode *rootNode *tree;BalancedBinaryTreeNode *lNode rootNode-lNode;BalancedBinaryTreeNode *lrNode lNode-rNode;*tree lNode;lNode-rNode rootNode;rootNode-lNode lrNode;
}RR平衡旋转B结点带右子树代替A成为根结点A结点带左子树成为B的左子树B结点原来的左子树作为A的右子树。
void rr(BalancedBinaryTree *tree) {BalancedBinaryTreeNode *rootNode *tree;BalancedBinaryTreeNode *rNode rootNode-rNode;BalancedBinaryTreeNode *rlNode rNode-lNode;*tree rNode;rNode-lNode rootNode;rootNode-rNode rlNode;
}LR先左后右双旋转C结点代替A结点成为根结点B结点带左子树成为C的左孩子A结点带右子树成为C的右孩子原来C结点的左子树作为B的右子树原来C的右子树作为A的左子树。
void lr(BalancedBinaryTree *tree) {BalancedBinaryTreeNode *rootNode *tree;BalancedBinaryTreeNode *lNode rootNode-lNode;BalancedBinaryTreeNode *lrNode lNode-rNode;BalancedBinaryTreeNode *lrlNode lrNode-lNode;BalancedBinaryTreeNode *lrrNode lrNode-rNode;*tree lrNode;lrNode-lNode lNode;lrNode-rNode rootNode;lNode-rNode lrlNode;rootNode-lNode lrrNode;
}RL先右后左双旋转C结点代替A作为根结点A结点带左子树成为C的左孩子B结点带右子树成为C的右孩子原来C结点的左子树作为A的右子树原来C的右子树作为B的左子树。
void rl(BalancedBinaryTree *tree) {BalancedBinaryTreeNode *rootNode *tree;BalancedBinaryTreeNode *rNode rootNode-rNode;BalancedBinaryTreeNode *rlNode rNode-lNode;BalancedBinaryTreeNode *rllNode rlNode-lNode;BalancedBinaryTreeNode *rlrNode rlNode-rNode;*tree rlNode;rlNode-lNode rootNode;rlNode-rNode rNode;rNode-lNode rlrNode;rootNode-rNode rllNode;
}最后是失衡调整算法在这个算法中只需要判断失衡类型是哪种并调用相应的算法即可
void imbalanceAdjust(BalancedBinaryTree *tree) {int lDeep balancedBinaryTreeDeep((*tree)-lNode);int rDeep balancedBinaryTreeDeep((*tree)-rNode);int balance lDeep - rDeep;if (balance 1) {lDeep balancedBinaryTreeDeep((*tree)-lNode-lNode);rDeep balancedBinaryTreeDeep((*tree)-lNode-rNode);//左左和左右if (lDeep rDeep) {ll(tree);} else {lr(tree);}} else if (balance -1) {lDeep balancedBinaryTreeDeep((*tree)-rNode-lNode);rDeep balancedBinaryTreeDeep((*tree)-rNode-rNode);//右右和右左if (rDeep lDeep) {rr(tree);} else {rl(tree);}} else {return;}
}平衡二叉树的插入
对于平衡二叉树的插入而言只要调整第一棵最小不平衡子树只要第一颗最小不平衡子树恢复了平衡那么整棵树就恢复了平衡。
/*** 二叉排序树的插入* param tree* param element* param compare* return*/
bool balancedBinaryTreeInsert(BalancedBinaryTree *tree, void *element, int (*compare)(void *, void *)) {if ((*tree) NULL) {*tree malloc(sizeof(BalancedBinaryTreeNode));(*tree)-data element;(*tree)-lNode NULL;(*tree)-rNode NULL;return true;} else {int cmpResult compare(element, (*tree)-data);if (cmpResult 0) {return false;} else if (cmpResult 0) {if ((*tree)-rNode NULL) {BalancedBinaryTreeNode *node malloc(sizeof(BalancedBinaryTreeNode));node-data element;node-rNode NULL;node-rNode NULL;(*tree)-rNode node;return true;} else {bool result balancedBinaryTreeInsert((*tree)-rNode, element, compare);imbalanceAdjust(tree);return result;}} else {if ((*tree)-lNode NULL) {BalancedBinaryTreeNode *node malloc(sizeof(BalancedBinaryTreeNode));node-data element;node-rNode NULL;node-rNode NULL;(*tree)-lNode node;return true;} else {bool result balancedBinaryTreeInsert((*tree)-lNode, element, compare);imbalanceAdjust(tree);return result;}}}
}平衡二叉树的删除
对于平衡二叉树的删除而言需要在被删除的结点处一直向上回溯找到所有最小不平衡子树并进行失衡调整。
/*** 删除元素* param tree* param element* param compare* return*/
bool balancedBinaryTreeDelete(BalancedBinaryTree *tree, void *element, int (*compare)(void *, void *)) {if (*tree NULL) {return false;} else {int cmpResult compare(element, (*tree)-data);if (cmpResult 0) {if ((*tree)-lNode NULL (*tree)-rNode NULL) {free(*tree);*tree NULL;return true;} else if ((*tree)-lNode NULL) {BalancedBinaryTreeNode *node (*tree);*tree (*tree)-rNode;free(node);return true;} else if ((*tree)-rNode NULL) {BalancedBinaryTreeNode *node (*tree);*tree (*tree)-lNode;free(node);return true;} else {BalancedBinaryTreeNode *node (*tree)-rNode;while (node-lNode ! NULL) {node node-lNode;}(*tree)-data node-data;bool result balancedBinaryTreeDelete((*tree)-rNode, node-data, compare);imbalanceAdjust(tree);return result;}} else if (cmpResult 0) {bool result balancedBinaryTreeDelete((*tree)-rNode, element, compare);imbalanceAdjust(tree);return result;} else {bool result balancedBinaryTreeDelete((*tree)-lNode, element, compare);imbalanceAdjust(tree);return result;}}
}红黑树
虽然平衡二叉树可以保证二叉排序树的性能但是频繁的平衡调整代价较大为此在平衡二叉树上放宽了条件引入了红黑树红黑树是具有以下性质的二叉排序树
每个结点或是红色或是黑色的。根结点是黑色的。所有叶子结点虚构的外部结点即NULL结点都是黑色的。不存在两个相邻的红结点即红结点的父结点和孩子结点都是黑色的。对于每个结点而言其到任意叶子结点的路径都包含相同数量的黑结点不包含自己这些黑结点的数量称为该结点的黑高根结点的黑高称为树的黑高。
struct RedBlackTreeNode {void *data;RedBlackTreeNode *lNode;RedBlackTreeNode *rNode;RedBlackTreeNode *pNode;int color;
};红黑树的性质如下
从根结点到叶子结点的最长路径不大于最短路径的两倍。有 n n n个内部结点的红黑树的高度 h ≤ 2 l o g 2 ( n 1 ) h\leq 2log₂(n1) h≤2log2(n1)。
红黑树的插入
红黑树插入的算法思想如下①先查找确定插入的位置和二叉搜索树相同。②插入结点是根结点则染成黑色否则就染成红色。③如果插入新结点后满足红黑树的定义则插入结束否则就进行调整此时只可能违反红黑树的第四条性质。针对不同的类型有不同的调整策略
黑叔LL型和平衡二叉树一样的LL平衡旋转父和爷染色
static void ll(RedBlackTree *tree) {RedBlackTreeNode *rootNode *tree;RedBlackTreeNode *rootPNode (*tree)-pNode;RedBlackTreeNode *lNode rootNode-lNode;RedBlackTreeNode *lrNode lNode-rNode;*tree lNode;lNode-pNode rootPNode;lNode-rNode rootNode;rootNode-pNode lNode;rootNode-lNode lrNode;if (lrNode ! NULL) {lrNode-pNode rootNode;}reverseColor(rootNode);reverseColor(lNode);
}黑叔RR型和平衡二叉树一样的RR平衡旋转父和爷染色
static void rr(RedBlackTree *tree) {RedBlackTreeNode *rootNode *tree;RedBlackTreeNode *rootPNode (*tree)-pNode;RedBlackTreeNode *rNode rootNode-rNode;RedBlackTreeNode *rlNode rNode-lNode;*tree rNode;rNode-pNode rootPNode;rNode-lNode rootNode;rootNode-pNode rNode;rootNode-rNode rlNode;if (rlNode ! NULL) {rlNode-pNode rootNode;}reverseColor(rootNode);reverseColor(rNode);
}黑叔LR型和平衡二叉树一样的LR平衡旋转儿和爷染色
static void lr(RedBlackTree *tree) {RedBlackTreeNode *rootNode *tree;RedBlackTreeNode *rootPNode (*tree)-pNode;RedBlackTreeNode *lNode rootNode-lNode;RedBlackTreeNode *lrNode lNode-rNode;RedBlackTreeNode *lrlNode lrNode-lNode;RedBlackTreeNode *lrrNode lrNode-rNode;*tree lrNode;lrNode-pNode rootPNode;lrNode-lNode lNode;lNode-pNode lrNode;lrNode-rNode rootNode;rootNode-pNode lrNode;lNode-rNode lrlNode;if (lrlNode ! NULL) {lrlNode-pNode lNode;}rootNode-lNode lrrNode;if (lrrNode ! NULL) {lrrNode-pNode rootNode;}reverseColor(rootNode);reverseColor(lrNode);
}黑叔RL型和平衡二叉树一样的RL平衡旋转儿和爷染色
static void rl(RedBlackTree *tree) {RedBlackTreeNode *rootNode *tree;RedBlackTreeNode *rootPNode (*tree)-pNode;RedBlackTreeNode *rNode rootNode-rNode;RedBlackTreeNode *rlNode rNode-lNode;RedBlackTreeNode *rllNode rlNode-lNode;RedBlackTreeNode *rlrNode rlNode-rNode;*tree rlNode;rlNode-pNode rootPNode;rlNode-lNode rootNode;rootNode-pNode rlNode;rlNode-rNode rNode;rNode-pNode rlNode;rNode-lNode rlrNode;if (rlrNode ! NULL) {rlrNode-pNode rNode;}rootNode-rNode rllNode;if (rllNode ! NULL) {rllNode-pNode rootNode;}reverseColor(rootNode);reverseColor(rlNode);
}红叔叔父爷染色爷变为新结点代码见失衡调整
完整的失衡调整代码如下
static void imbalanceAdjust(RedBlackTree tree, RedBlackTree *root) {RedBlackTreeNode *fatherNode tree-pNode;if (fatherNode NULL) {return;}RedBlackTreeNode *grandFatherNode fatherNode-pNode;if (grandFatherNode NULL) {return;}RedBlackTreeNode *uncleNode grandFatherNode-lNode fatherNode ? grandFatherNode-rNode : grandFatherNode-lNode;if (!(tree-color RED fatherNode-color RED)) {return;}if (uncleNode NULL || uncleNode-color BLACK) {if (grandFatherNode-lNode fatherNode) {if (fatherNode-lNode tree) {if (grandFatherNode-pNode NULL) {ll(root);} else {ll(grandFatherNode-pNode-lNode grandFatherNode ? (grandFatherNode-pNode-lNode) : (grandFatherNode-pNode-rNode));}} else {if (grandFatherNode-pNode NULL) {lr(root);} else {lr(grandFatherNode-pNode-lNode grandFatherNode ? (grandFatherNode-pNode-lNode) : (grandFatherNode-pNode-rNode));}}} else {if (fatherNode-rNode tree) {if (grandFatherNode-pNode NULL) {rr(root);} else {rr(grandFatherNode-pNode-lNode grandFatherNode ? (grandFatherNode-pNode-lNode) : (grandFatherNode-pNode-rNode));}} else {if (grandFatherNode-pNode NULL) {rl(root);} else {rl(grandFatherNode-pNode-lNode grandFatherNode ? (grandFatherNode-pNode-lNode) : (grandFatherNode-pNode-rNode));}}}} else {reverseColor(grandFatherNode);reverseColor(fatherNode);reverseColor(uncleNode);if (grandFatherNode-pNode NULL) {grandFatherNode-color BLACK;} else {imbalanceAdjust(grandFatherNode, root);}}
}完整的插入代码如下
static bool insert(RedBlackTree *tree, RedBlackTree *root, void *element, int (*compare)(void *, void *)) {if ((*tree) NULL) {*tree malloc(sizeof(RedBlackTreeNode));(*tree)-data element;(*tree)-lNode NULL;(*tree)-rNode NULL;(*tree)-pNode NULL;(*tree)-color BLACK;return true;} else {int cmpResult compare(element, (*tree)-data);if (cmpResult 0) {return false;} else if (cmpResult 0) {if ((*tree)-rNode NULL) {RedBlackTreeNode *node malloc(sizeof(RedBlackTreeNode));node-data element;node-rNode NULL;node-rNode NULL;node-pNode *tree;node-color RED;(*tree)-rNode node;imbalanceAdjust(node, root);return true;} else {return insert((*tree)-rNode, root, element, compare);}} else {if ((*tree)-lNode NULL) {RedBlackTreeNode *node malloc(sizeof(RedBlackTreeNode));node-data element;node-rNode NULL;node-rNode NULL;node-pNode *tree;node-color RED;(*tree)-lNode node;imbalanceAdjust(node, root);return true;} else {return insert((*tree)-lNode, root, element, compare);}}}
}/*** 二叉排序树的插入* param tree* param element* param compare* return*/
bool redBlackTreeInsert(RedBlackTree *tree, void *element, int (*compare)(void *, void *)) {return insert(tree, tree, element, compare);
}红黑树的删除
B树
B树又称为多路平衡查找树B数中所有结点的孩子个数的最大值称为B树的阶通常用 m m m表示B树要么是空树要么是满足以下条件的 m m m叉树
树中每个结点至多有 m m m棵子树最多含有 m − 1 m-1 m−1个数据若根结点不是终端结点则至少有两棵子树。除根结点之外的非叶子结点至少有 ⌈ m / 2 ⌉ ⌈m/2⌉ ⌈m/2⌉棵子树所有叶子节点都出现在同一层次上且不带任何信息。每个结点数据和子树的关系如下 子树 0 数据 1 子树 1 数据 2 子树 2 … 子树0数据1子树1数据2子树2\dots 子树0数据1子树1数据2子树2…
struct BTreeNode {void **dataList;BTreeNode **childList;int dataCount;
};B树的插入
B树的删除
B树的查找
B树
