1 files changed, 85 insertions, 0 deletions
diff --git a/6.4/tree.c b/6.4/tree.c
new file mode 100644
index 0000000..7f12162
--- /dev/null
+++ b/6.4/tree.c
@@ -0,0 +1,85 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <error.h>
+#include <errno.h>
+#include "tree.h"
+
+struct tnode *talloc(void);
+void tlswap(struct tnode *l[], int p1, int p2);
+
+struct tnode *addtree(struct tnode *p, char *w)
+{
+	int cond;
+
+	if (p == NULL) {
+		p = talloc();
+		p->word = strdup(w);
+		p->count = 1;
+		p->left = p->right = NULL;
+	} else if (!(cond = strcasecmp(w, p->word))) {
+		p->count++;
+	} else if (cond < 0) {
+		p->left = addtree(p->left, w);
+	} else if (cond > 0) {
+		p->right = addtree(p->right, w);
+	}
+
+	return p;
+}
+
+int tlstore(struct tnode *p, struct tnode *l[], int lim)
+{
+	static int nt;
+
+	if (p != NULL && nt < lim) {
+		tlstore(p->left, l, lim);
+		l[nt++] = p;
+		tlstore(p->right, l, lim);
+	}
+
+	return nt;
+}
+
+void tlsort(struct tnode *l[], int lim)
+{
+	int gap, i, j;
+
+	for (gap = lim/2; gap > 0; gap /= 2)
+		for (i = gap; i < lim; ++i)
+			for (j = i - gap; j >= 0 &&
+				l[j]->count >= l[j+gap]->count; j -= gap)
+				tlswap(l, j, j + gap);
+}
+
+void tlswap(struct tnode *l[], int p1, int p2)
+{
+	struct tnode *temp;
+
+	temp = l[p1];
+	l[p1] = l[p2];
+	l[p2] = temp;
+}
+
+void printtl(struct tnode *l[], int lim)
+{
+	int i;
+
+	for (i = 0; i < lim; ++i)
+		printf("%4d %s\n", l[i]->count, l[i]->word);
+}
+
+void tfree(struct tnode *p)
+{
+	if (p != NULL) {
+		tfree(p->left);
+		tfree(p->right);
+		free(p->word);
+		free(p);
+	}
+}
+
+struct tnode *talloc(void)
+{
+	return (struct tnode *) malloc(sizeof(struct tnode));
+}