Anonymous
Anonymous asked in 電腦與網際網路程式設計 · 1 decade ago

binary Search tree

我有一個struct 給定的

in C語言

typedef struct node *treeptr;

typedef struct node{

int data;

treeptr left, right;

}

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

可以麻煩解釋一下嗎?

感激

Update:

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

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

2 Answers

Rating
  • Thomas
    Lv 6
    1 decade ago
    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是否正確

  • 1 decade ago

    用遞迴建立,

    比root大的放右邊,

    比root小的放左邊

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

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

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

Still have questions? Get your answers by asking now.