C语言中树数据结构教程

Question

有没有人能够给我指一些使用C语言的树数据结构教程？我尝试了谷歌搜索，但大多数实现都是针对C++或Java。如果有人能够指向一些使用C的在线教程，那就太好了。

谢谢。

- The Stig

---

读过什么好的数据结构书。 - Tauquir

请查看 https://ece.uwaterloo.ca/~ece250/Lectures/Slides/ 的第4节。该网站还有许多其他数据结构和算法的实现和解释，以及它们的运行时间/渐近分析。 - rrazd

Answer 1

通用的树遍历方法：http://en.wikipedia.org/wiki/Tree_traversal （右侧边栏列出了可供选择的众多算法）。

一些教程：

• http://randu.org/tutorials/c/ads.php
• http://www.ehow.com/how_2056293_create-binary-tree-c.html

- eruciform

---

谢谢eruciform……正是我想要的。 - The Stig

没有问题 - 请在有机会的时候点击绿色复选标记。 - eruciform

Answer 2

这是几十年前的一段教程代码。实际上，它已经搁置了很长时间，我不记得它来自哪里或者是谁写的（可能是我，但我真的不确定）。理论上，它有点不可移植，使用了 strdup，它不是标准库的一部分，尽管大多数编译器都有/提供它。

/* Warning: untested code with no error checking included. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* A tree node. Holds pointers to left and right sub-trees, and some data (a string).
 */
typedef struct node {
    struct node *left;
    struct node *right;
    char *string;
} node;

node *root; /* pointers automatically initialized to NULL */

int insert(const char *string, node *root) {

    /* Add a string to the tree. Keeps in order, ignores dupes.
     */
    int num = strcmp(root->string, string);
    node *temp;

    for(;;) {
        if ( 0 == num)
            /* duplicate string - ignore it. */
            return 1;
        else if (-1 == num) {
            /* create new node, insert as right sub-tree.
             */
            if ( NULL == root -> right ) {
                temp = malloc(sizeof(node));
                temp -> left = NULL;
                temp -> right = NULL;
                temp -> string = strdup(string);
                return 2;
            }
            else
                root = root -> right;
        }
        else if ( NULL == root ->left ) {
            /* create new node, insert as left sub-tree.
             */
            temp = malloc(sizeof(node));
            temp -> left = NULL;
            temp -> right = NULL;
            temp -> string = strdup(string);
            return 2;
        }
        else
            root = root -> left;
    }
}


void print(node *root) {   
    /* in-order traversal -- first process left sub-tree.
     */
    if ( root -> left != NULL )
        print(root->left);
    /* then process current node.
     */
    fputs(root->string, stdout);

    /* then process right sub-tree
     */
    if ( root->right != NULL )
        print(root->right);
}

int main() {

    char line[100];

    /* Let user enter some data. Enter an EOF (e.g., ctrl-D or F6) when done.
     */
    while ( fgets(line, 100, stdin))
        insert(line, root);

    /* print out the data, in order
     */
    print(root);
    return 0;
}

- Jerry Coffin

---

@Jerry..我更想找一些教程而不是实际的代码。我想要对概念有一个很好的掌握，然后再自己尝试一下...无论如何，谢谢!!! - The Stig

@The Stig：啊，但这只是一个起点——它目前不支持查找特定值（应该很容易），删除（有些复杂），维护平衡（明显非常复杂）等功能。 - Jerry Coffin

Answer 3

#include <stdio.h>
#include <stdlib.h>

struct binary_node {
        struct binary_node *left;
        struct binary_node *right; int value;
};

typedef struct binary_node NODE;

int search(NODE *temp, int data)
{
        int found = 0;

#if 0
        while (temp == NULL) {
                if (temp->value == data) {
                        found = 1;
                        break;
                }
                else if (temp->value > data)
                        temp = temp->left;
                else if (temp->value < data)
                        temp = temp->right;
        }
        return found;
#endif

        if (temp == NULL)
                return 0;
        else if (temp->value == value)
                return 1;
        else if (temp->value > data)
                return search(temp->left, data);
        else if (temp->value < data)
  }




NODE *del(NODE *root, int val)
{
        if (root = NULL)
                return ;
        if (val < root->val)
                root->left = delete(root->left, val);
        else if (val > root->val)
                root->right = delete(root->right, val);

        else {
                if (root->left == NULL && root->right == NULL) {
                        temp = root;
                        free(temp);
                        root = NULL;
                }
                else if (root->left == NULL) {
                        temp = root;
                        root = root->right;
                        free(temp);
                }
                else if (root->right == NULL) {
                        temp = root;
                        root = root->left;
                        free(temp);
                }
                else {
                        temp = min(root->right);
                        root->data = temp->data;
                        root->right = delete(root->right, temp->data);
                }
        }

                return root;
}



NODE *insert_node(NODE *node, int val)
{

        if (*node == NULL) {
                node = (NODE *) malloc (sizeof(NODE));
                node->left = NULL;
                node->right = NULL;
                node->value = val;
        }

        if (node->value > val)
                node->left = insert_node(node->left, val);
        else if (node->value < val)
                node->right = insert_node(node->right, val);
        else
                printf("Discarding the data as it already exists in node\n");

        return node;
}

}
int main()
{

        NODE *root = NULL;

        root = insert_node(root, 50);
        insert_node(root, 4);
        insert_node(root, 14);
        insert_node(root, 44);
        insert_node(root, 24);
        insert_node(root, 34);
        insert_node(root, 74);
        insert_node(root, 54);
        insert_node(root, 64);

        print_order(&root);

        search(&root, 34);
        del(&root);

        return 0;
}

- Akshay Ithal

---

仅提供代码的答案很少有用或受欢迎，但在这种情况下，（古老的）问题根本不是要求代码，而是要求外部文档（教程）的参考，因此代码几乎无法回答问题。 顺便说一句，这个问题不符合SO当前的标准。 如果今天提出这个问题，它会很快被关闭。 - John Bollinger