今天写了一下二叉搜索树，暂时没写完，因为涉及到平衡化的问题，还要想想，特此记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//BST.c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode
{
    int m_nValue;
    TreeNode* p_left;
    TreeNode* p_right;
    TreeNode* parent;
}TreeNode,*PTreeNode;

void insert(TreeNode** root,int value)
{
	TreeNode* pNode=(TreeNode*)malloc(sizeof(TreeNode));     //sizeof()的参数别写错了，没有*
	pNode->m_nValue=value;
	pNode->p_left=NULL;		pNode->p_right=NULL; 	pNode->parent=NULL;

	if(*root == NULL)
	{
		*root=pNode; return;
	}
	if( (*root)->p_left == NULL && value < ((*root)->m_nValue ))
	{
		pNode->parent = *root;
		(*root)->p_left = pNode;
	}else if((*root)->p_right == NULL && value > ((*root)->m_nValue ))
	{
		pNode->parent = *root;
		(*root)->p_right=pNode;
	}

	if(value < ((*root)->m_nValue ))
		insert(&(*root)->p_left,value);
	else if(value > ((*root)->m_nValue ))
		insert(&(*root)->p_right,value);
}

void printPreorder(TreeNode* root)
{
    if(root == NULL)
        return;
	
    printf("%d ",root->m_nValue);
    
    if(root->p_left != NULL)
        printPreorder(root->p_left);
    if(root->p_right != NULL)
        printPreorder(root->p_right);
};

int main()
{
    int a[]={2,3,4,5,6,7,8,9,1};
    int i=0;
    TreeNode* root = (TreeNode*) malloc(sizeof(TreeNode*));
    root = NULL;
    for(i=0; i < (sizeof(a)/sizeof(a[0]));++i)
        insert(&root,a[i]);
   
    printPreorder(root);
    return 0;
}