C中的二叉树插入排序

Question

嘿，任何人都可以解释如何使用C语言中的插入排序来排序二叉树，其中时间复杂性是一个问题。我只是学习编码。感谢你们！

Answer 1

如果您以传统意义对二叉树进行编码，那么当您将项目添加到树中时，它将保留排序顺序。您可以通过遍历树来获得完整的项目列表。我建议你阅读：

• http://en.wikipedia.org/wiki/Tree_traversal

• http://en.wikipedia.org/wiki/Binary_tree

也看看：http://nova.umuc.edu/~jarc/idsv/lesson1.html

Answer 2

值得一提的是，有一定的术语，用在这里。 A 二叉树是一个数据结构，每个节点至多有两个孩子。对于二叉树中节点的排序没有约定。

甲二叉查找树是二叉树，使得对于给定的一个节点N中的N左子树的所有节点被认为是N和以N的右子树的所有节点“小于”被认为是大于” “N.你也可以让节点在树中被认为”等于“N，只要你一致地将它们定义为放置在左子树或右子树中。

正如其他人所说的，最好的办法是修改代码来构造二叉搜索树而不是普通的二叉树，或者将二叉树转换为线性数据结构并对其进行排序。

Answer 3

#include <stdio.h> 
#include <malloc.h> 
#define FIN "algsort.in" 
#define FOUT "algsort.out" 

struct Node { 
    int val; 
    struct Node *left; 
    struct Node *right; 
}; 

typedef struct Node node; 

void insert(node **bt, node *Node) { 

if(!(*bt)) { 

    *bt = Node; 

} else { 

     if(Node->val < (*bt)->val) 

      insert(&((*bt)->left), Node); 

     else 

      insert(&((*bt)->right), Node); 
} 
} 

void printout(struct Node *node) { 

    if(node->left) printout(node->left); 

    printf("%d ", node->val); 

    if(node->right) printout(node->right); 
} 

void postorder(struct Node *node) { 

     if(node->left) printout(node->left); 

     if(node->right) printout(node->right); 

     printf("%d ", node->val); 
} 

int main() { 

    int i, n, elem;  

    node *curr; 

    freopen(FIN, "r", stdin); 

    freopen(FOUT, "w", stdout); 

    node *bt = NULL; 

    scanf("%d", &n); 

    for(i = 0; i < n; ++i) { 

     scanf("%d", &elem); 

     curr = malloc(sizeof(struct Node)); 

     curr->val = elem; 

     curr->left = NULL; 

     curr->right = NULL; 

     insert(&bt, curr); 

    } 

    printout(bt); 

    return(0); 
    } 

假设algsort.in包含整数数组如下：

algsort.int - > 9,8,7,6,5,4,3,2,0,1， - 1;

algsort.out - > -1,0,1,2,3,4,5,6,7,8,9