ツリーの作成、遍歴および検索(C実装)
binTree.h
binTree.c
main.c
#ifndef BIN_TREE_H
#define BIN_TREE_H
typedef int DataType;
typedef struct node
{
DataType data;
struct node *lchild, *rchild;
}BinTNode;
typedef BinTNode* BinTree;
void CreateBinTree(BinTree* root);
BinTree BinTreeInsert(BinTree bt, DataType k);
void preorderTraversal(BinTree root);
void inorderTraversal(BinTree root);
void postorderTraversal(BinTree root);
void FindValue(BinTree root, DataType k, int level);
#endif
binTree.c
#include "binTree.h"
#include
#include
/* init a BST */
void CreateBinTree(BinTree* root)
{
BinTree t; /* t will be the bintree root pointer */
DataType tmp;
t = NULL;
printf("please input the new node value:");
scanf("%d", &tmp);
while (tmp != 0)
{
t = BinTreeInsert(t, tmp);
printf("please input the new node value:");
scanf("%d", &tmp);
}
*root = t;
}
/* insert a node into bintree */
/* during this procedure, we can't lose the root pointer(bt) */
BinTree BinTreeInsert(BinTree bt, DataType k)
{
BinTNode *p;
/* if the tree is empty, first create the root node */
if (bt == NULL)
{
p = (BinTNode *)malloc(sizeof(BinTNode));
p->data = k;
p->lchild = p->rchild = NULL;
return p; /* , , ^_^ */
}
else if (bt->data == k)
{
return bt;
}
else if (bt->data > k)
{
bt->lchild = BinTreeInsert(bt->lchild, k);
}
else
{
bt->rchild = BinTreeInsert(bt->rchild, k);
}
/* , bt , */
return bt;
}
/* */
void inorderTraversal(BinTree root)
{
if (root)
{
inorderTraversal(root->lchild);
printf("%d ", root->data);
inorderTraversal(root->rchild);
}
}
/* */
void preorderTraversal(BinTree root)
{
if (root)
{
printf("%d ", root->data);
preorderTraversal(root->lchild);
preorderTraversal(root->rchild);
}
}
/* */
void postorderTraversal(BinTree root)
{
if (root)
{
postorderTraversal(root->lchild);
postorderTraversal(root->rchild);
printf("%d ", root->data);
}
}
/* print out the times of call when you find out this value */
void FindValue(BinTree root, DataType k, int level)
{
level++;
if (root == NULL)
{
printf("sorry, after %d times call, I can't find this value
", level);
return;
}
if (root->data == k)
{
printf("after %d times call, I find it!!
", level);
}
else if (k < root->data)
{
FindValue(root->lchild, k, level);
}
else if (k > root->data)
{
FindValue(root->rchild, k, level);
}
}
main.c
#include "binTree.h"
#include
int main()
{
BinTree root;
int v;
CreateBinTree(&root);
printf("inorderTraversal is:
");
inorderTraversal(root);
printf("
");
printf("preorderTraversal is:
");
preorderTraversal(root);
printf("
");
printf("postorderTraversal is:
");
postorderTraversal(root);
printf("
");
printf("root->data is %d
", root->data);
while (v >= 0)
{
printf("please input the value you want to find:");
scanf("%d", &v);
FindValue(root, v, 0);
}
return 0;
}