binary Search tree

Question

我有一個struct 給定的

in C語言

typedef struct node *treeptr;

typedef struct node{

int data;

treeptr left, right;

}

我要如何用他來建立一個Binary tree？

可以麻煩解釋一下嗎？

感激

Update:

我知道他的原理 但是我沒辦法跑出來...

insert()中 我基本上只有辦法建立root而以...

Answer 1

Favorite Answer

#include <stdio.h>

#include <stdlib.h>

typedef struct node *treeptr;

typedef struct node

{

int data;

treeptr left;

treeptr right;

}NODE;

// 建 Binary Tree

void insert(treeptr *treeNode, treeptr newNode)

{

if (*treeNode == NULL) //如果 Subtree 沒有 => 新加的 Node 就是 Subtree

{

// 為了能修改 treeNode 值 我們只好 call by address

*treeNode = newNode;

return;

}

if (newNode->data < (*treeNode)->data)

insert(&((*treeNode)->left), newNode); //值小, 到 left subtree 做 insert()

else

insert(&((*treeNode)->right), newNode);

}

void inorder(treeptr tree)

{

if (tree->left !=NULL)

inorder(tree->left);

printf(" %d,", tree->data);

if (tree->right !=NULL)

inorder(tree->right);

}

void preorder(treeptr tree)

{

printf(" %d,", tree->data);

if (tree->left !=NULL)

preorder(tree->left);

if (tree->right !=NULL)

preorder(tree->right);

}

int main(int argc, char *argv[])

{

int i, kkk[10] = {1,7,4,5,2,8,3,10,9,6}; //舉例

treeptr ptr, root=NULL;

for (i=0; i<10; i++)

{

ptr = (treeptr)malloc(sizeof(treeptr));

ptr->left = NULL;

ptr->right = NULL;

ptr->data = kkk[i];

insert(&root, ptr);

}

printf("PRE-ORDER: ");

preorder(root);

printf("\nIN-ORDER: ");

inorder(root);

printf("\n");

system("pause");

return 0;

}

1

↘

7

↙ ↘

4 8

↙ ↘ ↘

2 5 10

↘ ↘ ↙

3 6 9

用 pre-order 來 traverse (也稱 depth-first traversal),

1, 7, 4, 2, 3, 5, 6, 8, 10, 9

用 in-order 來 traverse

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

所以, 用來驗證 binary tree是否正確

Answer 2

用遞迴建立，

比root大的放右邊，

比root小的放左邊

2008-04-23 14:14:31 補充：

資料結構的書裡 應該都會有吧

請參考 蔡定遠 劉靜慧 資料結構與演算法則