在用二叉树实现散列表之前，首先需要明白的是二叉树与散列表各自的特性。
对于二叉树，主要表现形式是一对二；拿链型二叉树来说，即一个结点含有一个前驱，两个后继，两个后继即是该结点的两个孩子，如图。建立和处理用递归的方法可以轻松实现。具体关于树的结构在此不再详解。
对于散列表，通俗来说，即对于将要插入的元素再通过一种函数式（如取余）后，得到一个具体数字（或字符），这个数字（或字符）将决定该元素所存放的位置，如果这个位置已经存有元素，则需要再次经过一系列的处理（或计算）得到一个新的地址位置，然后再原来的元素存入该为空的位置；具体的实现方法在此也不再详解。
在对两者进行结合的过程中，需要考虑两者的特性，然后再进行实现。下面是个人在VC环境下使用了两个自定义函数对其进行中序实现的过程。
数字可以分为两种，奇数和偶数，根据此特点，可以对该数字进行不断的除二取余的方式得到储存地址
如图，首先插入的数是2,2%2==0，则在头结点的左边建立一个结点，存放数字2，并将其地址赋予头结点的lchild，然后插入的是奇数3，判断得其为奇数，故存放与右侧地址2；在再次插入偶数6时，经判断，6是偶数，而地址1中又存有元素，则需要重新寻找新的空的地址，再次做出的处理是6/2=3；3是奇数，则存放的是4，即作为1的右子树，依次类推，在相应的地址已经存放有元素的情况下，改变参数，寻找新的地址。由于每个数在取余过一定的次数以后，得到的数是不会重复的，所以每一个数字都会有一个地址来存放，不会发生冲突，二叉树就可以顺利实现。
在其中需要注意的是，每个元素在经过除二之后虽然参数发生了变化，但是在找到并开辟好了需要存放该元素的空间后，存放的元素却还是客户端键入的原数字，所以在程序的运行中，要注意赋值对象是否正确。所以我在程序的实现中，采用了函数嵌套的方法，一个函数的作用是找到地址开辟空间，其返回值便是需要进行赋值的空间，在调用过后，只需将原来的元素放到该返回地址的相应区域即可。
如果各位还不够明白，则下面开始解读程序。
在运行开始，用户首先键入数字2，初始化成功的情况下，判断出2的存放位置应是位置1，（满足条件2%2==0&&p->lchild==NULL）这时建立一个结点，把这个结点放到头结点的左子树处，返回这个新建结点的地址，find函数执行一次，由于判断语句是else if型，直接退出进入insert函数实现赋值。在插入12时，满足else if (data%2==0&&p->lchild !=NULL)，进入递归，p指向的是地址1,12/2==6，参数为6，对6继续判断，满足else if (data%2==0&&p->lchild!=NULL)，再次递归，直到else if (data%2==1&&p->rchild==NULL)，此时，data为3，开始创建空间并且退出递归，最后，在insert中返回的地址仍为新开辟的地址，此时开始赋值。
在进行删除的过程中，只需要找到对应与欲删除元素相匹配的地址，然后改变地址中元素的值即可（如if (p->data==data)p->data=-1;）遍历时遇到-1即不进行遍历即可，不需要释放空间。
以上存属个人看法，如有不足，欢迎指正。
网友评论