• 树的定义
• 树的遍历
  • 前序遍历
  • 中序遍历
  • 后序遍历
• 二叉搜索树

树的定义

typedef struct node {
        int data;
        struct node * left, *right, *parent;
}Node, *Tree;

树的遍历

前序遍历

void pre_order(Tree t){
        if(t){
                printf("pre order: %d.\n", t->data);
                pre_order(t->left);
                pre_order(t->right);
        }
}

中序遍历

void middle_order(Tree t){
        if(t){
                middle_order(t->left);
                printf("middle order: %d.\n", t->data);
                middle_order(t->right);
        }
}

后序遍历

void post_order(Tree t){
        if(t){
                post_order(t->left);
                post_order(t->right);
                printf("post order: %d.\n", t->data);
        }
}

二叉搜索树

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

typedef struct node {
        int data;
        struct node * left, *right, *parent;
}Node, *Tree;

Tree search_tree_insert(Tree T, int k){
        Tree root = T;

        Node* node = (Node*)malloc(sizeof(Node));
        node->data = k; node->left = NULL; node->right = NULL; node->parent = NULL;

        Node* parent = NULL;
        for(;T != NULL;)
        {
                parent = T;
                if(k < T->data) T = T->left;
                else T = T->right;
        }
        node->parent = parent;
        if(parent == NULL) return node; // Tree T is Null
        else if(k < parent->data) parent->left = node;
        else parent->right = node;

        return root;
}

void middle_order(Tree t){
        if(t){
                middle_order(t->left);
                printf("middle order: %d.\n", t->data);
                middle_order(t->right);
        }
}

int main()
{
        Tree tree_root = (Tree)malloc(sizeof(Node));
        tree_root->left = NULL; tree_root->right = NULL; tree_root->parent = NULL;

        int d;
        // first date at root node
        scanf("%d", &d);
        tree_root->data = d;
        // 二叉搜索树插入数据
        for(int i = 1; i <5 ; i++){
                scanf("%d", &d);
                tree_root = search_tree_insert(tree_root,d);
        }
        // 中序遍历二叉搜索树
        middle_order(tree_root);

        return 0;
}                                              

Wu_Being 博客声明：本人博客欢迎转载，请标明博客原文和原链接！谢谢！
《【数据结构5】树》
http://blog.csdn.net/u014134180/article/details/55506250

如果你看完这篇博文，觉得对你有帮助，并且愿意付赞助费，那么我会更有动力写下去。