行业网站开发程序,vue 做企业网站行不,wordpress多个页面,家装网站自己做的写在前面的话 最近接到几个大学同学研究生毕业不是签华为就是签百度,本人取经得到:操作系统、数据结构与算法、网络编程与数据库是面试中利器。想想自己工作2.5年月薪还不到10K,过着苦逼的码农生活,而他们一出校门就是大放光芒(最起码进入的公司就让人觉得牛逼哄哄的).本人痛定…写在前面的话
最近接到几个大学同学研究生毕业不是签华为就是签百度,本人取经得到:操作系统、数据结构与算法、网络编程与数据库是面试中利器。想想自己工作2.5年月薪还不到10K,过着苦逼的码农生活,而他们一出校门就是大放光芒(最起码进入的公司就让人觉得牛逼哄哄的).本人痛定思痛,决定下大功夫学习一下数据结构与算法,我想这应该是根本吧. 之前也看过数据结构,但是一看到那乱七八糟的关系,就觉得还是研究一下别的东西,结果就是好多东西都是浅尝辄止,知子皮毛. 本人只贴出学习过程中的代码,以及一些发杂算法函数的详细注释,还有就是学习过程中遇到过的好的讲解URL,以供自己理解和后续的复习巩固,有不对的地方还需指正. 学习二叉树之前总感觉很抽象,最近看到亚嵌一个关于红黑树讲解的视频用到一个命令,能够将二叉树转换成图形打印出来感觉很神奇,这个工具在Linux C编程一站式学习 中有提到过, http://www.essex.ac.uk/linguistics/external/clmt/latex4ling/trees/tree/ 有关应用会在后面代码测试中有提到,我想这应该是学习二叉树的一大利器,在此提出来。源码
binarytree.h #ifndef BINARYTREE_H
#define BINARYTREE_Htypedef struct node *link;
/***节点中的数据类型重定义*/
typedef unsigned char TElemType;struct node { TElemType item; link lchild, rchild;
};link init(TElemType VLR[], TElemType LVR[], int n);void pre_order(link t, void (*visit)(link));
void in_order(link t, void (*visit)(link));
void post_order(link t, void (*visit)(link));
void pprint(link t);
int count(link t);
int depth(link t);
void destroy(link t);/**
*http://www.cnblogs.com/bizhu/archive/2012/08/19/2646328.html 算法图解
*
*二叉排序树(Binary Sort Tree)又称二叉查找树(Binary Search Tree),亦称二叉搜索树,
*它或者是一棵空树或者是具有下列性质的二叉树:
*(1)若左子树不空则左子树上所有结点的值均小于它的根结点的值;
*(2)若右子树不空则右子树上所有结点的值均大于它的根结点的值;
*(3)左、右子树也分别为二叉排序树;
*(4)排序二叉树的中序遍历结果是从小到大排列的.
*
*二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,为O(log n)。
*二叉查找树是基础性数据结构用于构建更为抽象的数据结构如集合、multiset、关联数组等。
*
*搜索,插入,删除的复杂度等于树高期望O(log n),最坏O(n)(数列有序,树退化成线性表)
*改进版的二叉查找树可以使树高为O(logn),如SBT,AVL,红黑树等.
*
*程序来源于Linux C编程一站式学习
*/
link bstSearch(link t, TElemType key);
link bstInsert(link t, TElemType key);
link bstDelete(link t, TElemType key);/***http://baike.baidu.com/view/593144.htm?fraladdin*平衡二叉树*/#endifbinarytree.c/* binarytree.c */
#include stdio.h
#include stdlib.h
#include binarytree.h/***生成节点*param item is node value*returns link point to new node*/
static link make_node(TElemType item)
{link p malloc(sizeof *p);p-item item;p-lchild p-rchild NULL;return p;
}/***释放节点*param link to free*/
static void free_node(link p)
{free(p);
}/***根据前序与中序序列来初始化二叉树*param VLR 前序序列*param LVR 中序序列*param n 序列中数值个数*returns NULL when n 0*returns link pointer to new binarytree*/
link init(TElemType VLR[], TElemType LVR[], int n)
{link t;int k;if (n 0)return NULL;for (k 0; VLR[0] ! LVR[k]; k);t make_node(VLR[0]);t-lchild init(VLR1, LVR, k);t-rchild init(VLR1k, LVR1k, n-k-1);return t;
}#ifdef RECU
/***前序遍历(跟左右)*param t to visit*param visit point to a func*/
void pre_order(link t, void (*visit)(link))
{if (!t)return;visit(t);pre_order(t-lchild, visit);pre_order(t-rchild, visit);
}/***中序序遍历(左跟右)*param t to visit*param visit point to a func*/
void in_order(link t, void (*visit)(link))
{if (!t)return;in_order(t-lchild, visit);visit(t);in_order(t-rchild, visit);
}/***中序序遍历(左右跟)*param t to visit*param visit point to a func*/
void post_order(link t, void (*visit)(link))
{if (!t)return;post_order(t-lchild, visit);post_order(t-rchild, visit);visit(t);
}
#endif/***遍历二叉树,生成用于tree工具的字符串*param root to visit*/
void pprint(link root)
{printf(();if (root ! NULL) {printf(%d, root-item);pprint(root-lchild);pprint(root-rchild);}printf());
}int count(link t)
{if (!t)return 0;return 1 count(t-lchild) count(t-rchild);
}int depth(link t)
{int dl, dr;if (!t)return 0;dl depth(t-lchild);dr depth(t-rchild);return 1 (dl dr ? dl : dr);
}void destroy(link t)
{post_order(t, free_node);
}/***在bst中查找值为key的节点**1、若b是空树则搜索失败否则;*2、若x等于b的根节点的数据域之值则查找成功否则;*3、若x小于b的根节点的数据域之值则搜索左子树否则;*4、查找右子树.**param t to search*param key the value of link to find*returns the link of the key*/
link bstSearch(link t, TElemType key)
{if (t NULL)return NULL;if (t-item key) {return bstSearch(t-lchild, key);} else if (t-item key){return bstSearch(t-rchild, key);} else {return t;}
}/***在bst中插入值为key的节点**1、若t是空树则将key作为根节点的值插入否则;*2、若t-item大于key则把key插入到左子树中否则;*3、把key插入到左子树中.**param t 要插入的 bst*param key 要插入的值*returns 插入后的bst*/
link bstInsert(link t, TElemType key)
{if (t NULL) {return make_node(key);}if (t-item key) {t-lchild bstInsert(t-lchild, key);} else {t-rchild bstInsert(t-rchild, key);}return t;
}/***在bst中删除值为key的节点**1、若t为空树则直接返回NULL,否则;*2、若t-item大于keybst左子树为bst左子树删除key后的bst否则;*3、若t-item小于keybst右子树为bst右子树删除key后的bst否则;*4、若t-item key:* 1.若其左右子树为NULL,返回NULL,即对其父节点赋值为NULL* 2.若其左子树不为NULL,则在其左子树中找到最大节点p,将p-item赋值给当前节点,还需要在其左子树中删除p-item,3.若其右子树不为NULL,则在其左子树中找到最小节点p,将p-item赋值给当前节点,还需要在其右子树中删除p-item,**param t 要插入的 bst*param key 要插入的值*returns 插入后的bst*/
link bstDelete(link t, TElemType key)
{if (t NULL)return NULL;if (t-item key) t-lchild bstDelete(t-lchild, key);else if (t-item key)t-rchild bstDelete(t-rchild, key);else {link p;if (t-lchild NULL t-rchild NULL) {free_node(t);t NULL;} else if (t-lchild){for (p t-lchild; p-rchild; p p-rchild);t-item p-item;t-lchild bstDelete(t-lchild, t-item);} else {for (p t-rchild; p-lchild; p p-lchild);t-item p-item;t-rchild bstDelete(t-rchild, t-item);}}return t;
}测试程序/* main.c */
#include stdio.h
#include time.h
#include binarytree.h#define RANGE 50
#define N 15void print_item(link p)
{printf(%d\t, p-item);
}void testBst()
{int i;link root NULL;srand(time(NULL));for (i0; iN; i)root bstInsert(root, rand()%RANGE);printf(\\tree);pprint(root);printf(\n);TElemType key rand() % RANGE;if (bstSearch(root, key)) {bstDelete(root, key);printf(\n%d\n, key);printf(\\tree);pprint(root);printf(\n);}
}void testInitByList()
{TElemType pre_seq[] { 4, 2, 1, 3, 6, 5, 7 };TElemType in_seq[] { 1, 2, 3, 4, 5, 6, 7 };link root init(pre_seq, in_seq, 7);printf(\\tree);pprint(root);printf(\n);pre_order(root, print_item);putchar(\n);in_order(root, print_item);putchar(\n);post_order(root, print_item);putchar(\n);printf(count%d depth%d\n, count(root), depth(root));destroy(root);printf(\n\n);
}int main()
{//testInitByList();testBst();return 0;
}对应的Makefie #if you want to use recursive func,please make recuy
ifeq (y, $(recu))CFLAGS -DRECU
endififeq (y, $(debug))CFLAGS -g
endifall:gcc $(CFLAGS) main.c binarytree.c binarytree.h -o treeclean:$(RM) tree 编译测试 在这里遍历二叉树只写了递归函数 在编译的时候用一下命令make recuy debugy运行结构如下\tree(15(6(0()())(7()(14(11(8()())())())))(41(36(18(16()())(23(22()())(29()())))())(41()())))22
\tree(15(6(0()())(7()(14(11(8()())())())))(41(36(18(16()())(23()(29()())))())(41()())))好了接下来就是用工具tree把这些字符串图形化echo \tree(15(6(0()())(7()(14(11(8()())())())))(41(36(18(16()())(23(22()())(29()())))())(41()()))) | tree -b2怎么样这个效果。把b2改成b6
