May 15, 2018

binary search tree

A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search property, which states that the key in each node must be greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.[1]:287 The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.

首先我们来实现一棵二叉树

                  
#pragma once
#include <stdio.h>
#include <stdlib.h>

typedef struct BTreeNode {
	int data;
	struct BTreeNode *leftChild;
	struct BTreeNode *rightChild;
}BTreeNode;

BTreeNode * init() {
	BTreeNode *t = (BTreeNode*)malloc(sizeof(BTreeNode));
	t->leftChild = NULL;
	t->rightChild = NULL;
	return t;
}

//查找某个结点
BTreeNode * search(BTreeNode *root, int e) {
	BTreeNode *find = NULL;
	if (root != NULL) {
		if (root->data == e) {
			find = root;
		}
		else {
			find = search(root->leftChild, e);
			if (find == NULL) {
				find = search(root->rightChild, e);
			}
		}
	}
	return find;
}

//撤销二叉树
void destroy(BTreeNode *root) {
	if (root != NULL && root->leftChild != NULL) {
		destroy(root->leftChild);
	}
	if (root != NULL && root->rightChild != NULL) {
		destroy(root->rightChild);
	}
	free(root);
}

BTreeNode * insertLeftNode(BTreeNode *curr, int e) {
	if (curr == NULL) {
		return NULL;
	}
	BTreeNode *tt = (BTreeNode*)malloc(sizeof(BTreeNode));
	tt->data = e;
	tt->leftChild = curr->leftChild;
	tt->rightChild = NULL;
	curr->leftChild = tt;
	return tt;
}

BTreeNode * insertRightNode(BTreeNode *curr, int e) {
	if (curr == NULL) {
		return NULL;
	}
	BTreeNode *tt = (BTreeNode*)malloc(sizeof(BTreeNode));
	tt->data = e;
	tt->rightChild = curr->rightChild;
	tt->leftChild = NULL;
	curr->rightChild = tt;
	return tt;
}

BTreeNode * deleteLeftNode(BTreeNode *curr) {
	if (curr == NULL || curr->leftChild == NULL) return NULL;
	destroy(curr->leftChild);
	curr->leftChild = NULL;
	return curr;
}

BTreeNode * deleteRightNode(BTreeNode *curr) {
	if (curr == NULL || curr->rightChild == NULL) return NULL;
	destroy(curr->rightChild);
	curr->rightChild = NULL;
	return curr;
}

//前序遍历二叉树
void preOrder(BTreeNode *root, void visit(BTreeNode *curr)) {
	if (root != NULL) {
		visit(root);
		preOrder(root->leftChild, visit);
		preOrder(root->rightChild, visit);
	}
}

//中序遍历二叉树
void inOrder(BTreeNode *root, void visit(BTreeNode *curr)) {
	if (root != NULL) {
		inOrder(root->leftChild, visit);
		visit(root);
		inOrder(root->rightChild, visit);
	}
}

//后序遍历二叉树
void postOrder(BTreeNode *root, void visit(BTreeNode *curr)) {
	if (root != NULL) {
		postOrder(root->leftChild, visit);
		postOrder(root->rightChild, visit);
		visit(root);
	}
}

void visit(BTreeNode *curr) {
	printf("%d, ", curr->data);
}

//横向打印一颗二叉树root，n为节点深度，初始值为0
void printBTree(BTreeNode *root, int n) {
	if (root == NULL) return;
	printBTree(root->leftChild, n + 1);
	for (int i = 0; i < n; i++) {
		printf("      ");
	}
	if (n > 0) {
		printf("---");
		printf("%d\n", root->data);
	}
	printBTree(root->rightChild, n + 1);

}

遍历一下这棵二叉树

                  
#include <stdio.h>
#include <stdlib.h>

#include "BTreeNode.h"

void main(void) {
	BTreeNode *root, *p, *q;
	root = init();
	insertLeftNode(root, 100);
	p = insertLeftNode(root->leftChild, 50);
	q = insertRightNode(root->leftChild, 200);

	insertLeftNode(p, 10);
	insertRightNode(p, 80);
	p = p->leftChild;
	insertLeftNode(p, 2);
	insertRightNode(p, 12);

	insertLeftNode(q, 150);
	insertRightNode(q, 170);

	printBTree(root, 0);
	printf("\n前序遍历");
	preOrder(root->leftChild, visit);
	printf("\n中序遍历");
	inOrder(root->leftChild, visit);
	printf("\n后序遍历");
	postOrder(root->leftChild, visit);

	BTreeNode *find = search(root->leftChild, 50);
	printf("\n在二叉树中查找元素50:：%d", find->data);
	destroy(root);

}

二叉树的遍历算法提供了二叉树的一次性遍历，但它无法实现用户程序像遍历双向链表那样，从前/从后分步遍历二叉树。
所以我们需要将一棵二叉树索引化，例如中序索引化二叉树，我们就可以通过一个循环结构遍历该二叉树所有的结点。例如循环初始为第一个结点，每次指向它的后驱结点。

定义ThreadBNode.h头文件，用来将二叉树索引化。

                  
#pragma once
#include <stdio.h>
#include <stdlib.h>


typedef struct ThreadBNode {
	char *data;
	int leftThread;
	int rightThread;
	struct ThreadBNode *leftChild;
	struct ThreadBNode *rightChild;
}ThreadBNode;

//将其余结点线索化
void inThread(ThreadBNode *curr, ThreadBNode *pre) {
	if (curr != NULL) {
		inThread(curr->leftChild, pre);//中序线索化左子树。对于左子树来说，上一个结点就是往上找第一个右结点的根节点/头结点
		if (curr->leftChild == NULL) {
			curr->leftThread = 1;
			curr->leftChild = pre;
		}
		else curr->leftThread = 0;
		if (curr->rightChild == NULL) {
			curr->rightThread = 1;
		}
		else curr->rightThread = 0;
		if (pre->rightChild == NULL) {
			pre->rightThread = 1;
			pre->rightChild = curr;
		}
		else pre->rightThread = 0;
		pre = curr;
		inThread(curr->rightChild, pre);//中序线索化右子树。对于右子树来说，上一个结点就是父结点
	}
}

//中序线索化二叉树
ThreadBNode * createInThread(ThreadBNode *root) {
	//将头结点线索化
	ThreadBNode *t = (ThreadBNode*)malloc(sizeof(ThreadBNode));
	if (root == NULL) {
		t->leftThread = 0;
		t->rightThread = 1;
		t->leftChild = t;
		t->rightChild = t;
	}
	else {
		ThreadBNode *curr = root;//第一个数据结点
		ThreadBNode *pre = root;//当前结点的前驱结点

		t->leftThread = 0;
		t->leftChild = root;
		inThread(curr, pre);
		pre->rightThread = 1;//置最后一个结点右线索
		pre->rightChild = t;//置最后一个结点右指针
		t->rightThread = 1;//置头结点右线索
		t->rightChild = pre;//置头结点右指针
	}
	return t;
}

定义ThreadBTree.h头文件，用来遍历线索二叉树。

                  
#include <stdio.h>
#include <stdlib.h>

#include "ThreadBNode.h"

typedef struct ThreadBTree{
	ThreadBNode *root;
	ThreadBNode *curr;
	int nextComplete;
}ThreadBTree;

//初始化线索二叉树
ThreadBTree * init(ThreadBNode *root) {
	ThreadBTree *tree = (ThreadBTree*)malloc(sizeof(ThreadBTree));
	tree->root = root;
	tree->curr = root;
	if (root == NULL)
		tree->nextComplete = 1;
	else
		tree->nextComplete = 0;
	return tree;
}

//使当前结点指针指向中序线索二叉树第一个结点
void first(ThreadBTree *tree) {
	ThreadBNode *p = tree->root;
	while (p->leftThread == 0) {
		p = p->leftChild;
	}
	tree->curr = p;
	if (tree->curr == tree->root) tree->nextComplete = 1;
	else tree->nextComplete = 0;
}

//使当前结点指针指向中序线索二叉树下一个结点
void next(ThreadBTree *tree) {
	if (tree->nextComplete == 1) return;
	ThreadBNode *p = tree->curr->rightChild;
	if (tree->curr->rightThread == 0) {
		while (p->leftThread == 0) {
			p = p->leftChild;
		}
	}
	tree->curr = p;
	if (tree->curr == tree->root) tree->nextComplete = 1;
	else tree->nextComplete = 0;
}

//判断是否有后驱结点
int hasNext(ThreadBTree *tree) {
	return tree->nextComplete;
}

建立一棵二叉树，中序索引化，测试下遍历。

                  
#include <stdio.h>
#include <stdlib.h>

#include "ThreadBTree.h"


ThreadBNode * createTreeNode(char *data, ThreadBNode *left, ThreadBNode *right){
	ThreadBNode *n = (ThreadBNode*)malloc(sizeof(ThreadBNode));
	n->data = data;
	n->leftChild = left;
	n->rightChild = right;
	return n;
}


void main(void) {

	//创建一棵带头结点的二叉树
	ThreadBNode *G = createTreeNode("G", NULL, NULL);
	ThreadBNode *D = createTreeNode("D", NULL, G);
	ThreadBNode *B = createTreeNode("B", D, NULL);

	ThreadBNode *E = createTreeNode("E", NULL, NULL);
	ThreadBNode *F = createTreeNode("F", NULL, NULL);
	ThreadBNode *C = createTreeNode("C", E, F);
	ThreadBNode *root = createTreeNode("A", B, C);

	
	//中序线索化二叉树
	root = createInThread(root);

	//初始化线索二叉树
	ThreadBTree *tree = init(root);
	first(tree);
	while(hasNext(tree)==0){
		next(tree);
		printf("%s  ", tree->curr->data);
	}


}

输出D G B A E C F