数据结构——二叉树与哈希表

树的基本概念树是n个节点的有限集合n0时称为空树n0时满足a)有且只有一个根节点b)其余节点分为m个互不相交的有限集合每个集合本身也是一棵树称为根的子树二叉树一.定义二叉树是n个节点的有限集合n 0为空树n 0则是由一个根节点和两棵互不相交的子树组成分别称为左子树和右子树且两者有严格顺序二.特点1.每个节点最多有两个子树2.左右子树有顺序不可互换3.即使某节点只有一个子树也必须明确是左子树还是右子树特殊二叉树1.斜树所有节点只有左子树左斜树或者右子树右斜树2.满二叉树深度为k且节点数为2^k - 1的二叉树所有层均被填满叶子节点全在最后一层3.完全二叉树对n个节点层序从1到n编号若每个节点的位置与相同深度的满二叉树中编号相同的节点位置一致则为完全二叉树除最后一层外其他层全满最后一层节点靠左排列三.遍历方式1.前序遍历根-左-右先访问根节点再递归遍历左子树最后右子树2.中序遍历左-根-右先递归遍历左子树再访问根最后右子树3.后序遍历左-右-根先递归遍历左右子树最后访问根节点4.层序遍历从上到下从左到右按层次逐层访问通常借助队列实现前三种是深度优先遍历DFS层序为广度优先遍历BFSeg前序ABCDEFGH中序BDCEAFHG后序DECBHGFA二叉树的算法1.创建一棵树拓展序列 --- 二叉树的前序遍历序列 空节点标记用#表示NULL如图拓展序列为 ABDG##H###CE#I##F## 代码char tree_seq[] ABDG##H###CE#I##F## int idx 0; //索引 bree_t *btree_create(void) { char data tree_seq[idx]; if(data #) { return NULL; } btree_t *new malloc(sizeof(btree_t)); if(new NULL) { printf(malloc failed\n); return NULL; } new-data data; new-pl btree_create(); new-pr btree_create(); return new; }2.遍历a前序遍历代码int pre_order_travers(btree_t *root) { if(root NULL) { return -1; } printf(%c ,root-data); pre_order_travers(root-pl); pre_order_travers(root-pr); return 0; }b中序遍历代码int in_order_travers(btree_t *root) { if(root NULL) { return -1; } in_order_travers(root-pl); printf(%c ,root-data); in_order_travers(root-pr); return 0; }c后序遍历代码int post_order_travers(btree_t *root) { if(root NULL) { return -1; } post_order_travers(root-pl); post_order_travers(root-pr); printf(%c ,root-data); return 0; }d层序遍历代码int layer_order_traverse(btree_t *t) { if(t NULL) { return -1; } //创建队列 node_t *pq linklist_create(); enqueue(pq,t); while(is_empty(pq) ! 1) { btree_t *data NULL; dequeue(pq,data); printf(%c ,data-data); if(data-pl ! NULL) { enqueue(pq,data-pl); } if(data-pr ! NULL) { enqueue(pq,data-pr); } } linklist_destroy(pq); return 0; }3.销毁代码int btree_destroy(btree_t *p) { if(p NULL) { return -1; } btree_destroy(p-pl); btree_destroy(p-pr); free(p); return 0; }哈希表基本思想记录“存储位置”与“关键字要处理的数据相关的一个值”之间的对应关系对应关系 --- hash函数存储位置 --- funckey方式1直接把key的值对应就是存储位置数组下标addr key方式2通过某种计算得到直接定值法、数字分析法、平方取中法、折叠法、除留余数法、随机数法哈希冲突就是不同的key值产生了相同的位置哈希冲突解决方式常见开发地址法、链地址法链地址法数组中存储的是对应的链表地址数组的类型也变为了一个指针数组的类型实现数据存储需要用到链表链表节点typedef int data_t; typedef struct node { data_t data; struct node *next; }node_t; #define SIZE 10 node_t *hash_table[SIZE];哈希表创建代码data_t a[] {21,33,43,45,54,63,67,82,34}; //主函数中定义 int hash_create(data_t *a,int len) { int i; for(i 0;i len;i) { int addr a[i] % 10; node_t *p malloc(sizeof(node_t)); if(p NULL) { printf(malloc failed\n); return -1; } p-data a[i]; if(hash_table[addr] NULL) { hash_table[addr] p; p-next NULL; }else { p-next hash_table[addr]; hash_table[addr] p; } } return 0; }哈希表遍历代码int hash_show(void) { int i 0; for(i 0;i SIZE;i) { printf(%d[%p]-,i,hash_table[i]); if(hash_table[i] ! NULL) { node_t *p hash_table[i]; while(p) { if(p-next ! NULL) printf(%d-,p-data); else printf(%d |NULL,p-data); p p-next; } } putchar(\n); } }查找数据代码node_t *hash_find(data_t data) { int add data % SIZE; if(hash_table[add] NULL) { return NULL; } node_t *p hash_table[add]; while(p) { if(p-data data) { return p; } p p-next; } return NULL; }修改数据代码node_t *hash_find(data_t old,data_t new) { int add data % SIZE; if(hash_table[add] NULL) { return NULL; } node_t *p hash_table[add]; while(p) { if(p-data old) { p-data new; return p; } p p-next; } return NULL; }删除节点代码int hash_delete_key(data_t data) { int add data % SIZE; if(hash_table[add] NULL) { printf(NOT FOUND\n); return -1; } node_t *p hash_table[add]; if(p-data data) { hash_table[add] p-next; free(p) return 0; } while(p-next ! 0) { if(p-next-data data) { node_t *temp p; p-next p-next-next; free(temp); return 0; } p p-next; } if(p-next NULL) { printf(NOT FOUND\n); return -1; } }销毁代码int hash_destroy(void) { int i; for(i 0;i SIZE; i) { if(hash_table[i] ! NULL) { node_t *p hash_table[i]; hash_table[i] NULL; while(p) { node_t *temp p; p p-next; free(temp); } } } return 0; }