搜索二叉树的创建

二叉搜索树的性质：

1）若它的左子树不为空，则左子树上所有节点都小于根节点的值。

2）若它的右子树不为空，则右子树上所有节点都大于根节点的值。

3）它的左右子树也分别为二叉搜索树。

二叉搜索树如下图：

二叉搜索树的创建过程：

先找到需要插入值得父节点，比较父节点与插入值得大小，确定插入的位置。

（找父节点，需要通过根节点与插入值得大小进行比较，确定根节点的左右孩子位置，继续循环，直到找到父节点的单个孩子节点为叶子结点。）

头文件：二叉搜索树.h

#pragma once

#include<stdio.h>

#include<Windows.h>

#include<stdlib.h>

typedef int Key;

typedef struct BST

{

struct BST *left;

struct BST *right;

Key key;

}BST;

#if 1

//建立二叉树

int CreatTree(BST**tree, Key aa)

{

BST*root = *tree;

BST*parent = NULL;

while (root!=NULL)

{

//如果root为空，表示此二叉树为空，需要建立根节点。

//if (root == NULL)

//根节点不为空

{//如果值存在

if (root->key == aa)

{

printf(“此值已经存在,无需添加\n”);

return -1;

}

parent = root; //双亲节点指向根节点。

//根节点的值大于所要插入的值，要插入的值在根节点的左边。

if (root->key > aa)

{

root = root->left;

}

else

{

root = root->right;

}

}

}

BSTpp = (BST)malloc(sizeof(BST));

pp->key = aa;

pp->left = pp->right = NULL;

if (parent == NULL)

{

tree = pp;//此处一定要注意！！！要用tree来保存pp的值。

return 0;

}

if (aa < parent->key)

parent->left = pp;

else

parent->right = pp;

return 0;

}

#endif

void test()

{

BST *tree = NULL;

Key aa[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };

int n = sizeof(aa) / sizeof(Key);

//BST*pp = NULL;

CreatTree(&tree, 5);

CreatTree(&tree, 3);

CreatTree(&tree, 4);

CreatTree(&tree, 1);

CreatTree(&tree, 7);

CreatTree(&tree, 8);

CreatTree(&tree, 2);

printf("\n");

}

源文件：test.cpp

#include"二叉搜索树.h"

#include<Windows.h>

int main()

{

test();

system(“pause”);

return 0;

}