c语言：基于排序二叉树的排序标签： c语言二叉树排序
by小威
1 .引入序列二叉树是二叉树的一种，其主要特色是二叉树的构建和二叉树的输出。 二叉树的子树很有特点。 左子树小于根节点，根节点小于右子树。 通过对二叉树进行排序，可以知道二叉树三种扫描中的两种。中序遍历和后序遍历。
中序遍历:中序扫描是指首先读取左子树，然后读取根节点，最后读取右子树。后序遍历:后面的遍历是先读取左边的子树，然后读取右边的子树，最后读取根节点。
补充说明：首先遍历的是读取根节点，然后读取左侧的子树，最后读取右侧的子树。
2 .代码前置代码：
代码主要分为两个部分。 第一部分是main函数的部分，第二部分是二叉树功能实现的部分。
/* main.h */# include stdio.h # include stdlib.h # include ' tree.h ' int main (void ) { int node_num，i=0，temme scanf('%d '，node_num )； wile(Inode_num ) scanf('%d '，temp )； if(I==0)根=init _根) temp； else insert _ node (根，时间)； I； } traverse _ tree _ in order (根)； printf((n )； recycle _ nodes (根； 返回0； }/* tree.h */# include stdlib.h # include stdio.htypedefstructnode { struct node * left； 结构节点*权限； int value； }节点； 节点* init _ root (intvalue ) { Node *root； 根=malloc (sizeof ) node )； 根值=值根值-左值=空值； 根光=空值； 返回根； }voidinsert_node(node*p，int value ) { Node *pArr； parr=malloc(sizeof ) node )； pArr-value=value； pArr-left=NULL； pArr-right=NULL； wile(p-left！=pArr p-right！=parr(while ) valuep-value ) if ) p-right==null ) { p-right=pArr； 返回； (else ) p=p-right； }while(valuep-value ) if ) p-left==null ) { p-left=pArr； 返回； } else { p=p-left； } }返回； } void traverse _ tree _ in order (node * p ) if ) p==null ) return； traverse_tree_inorder(p-left； printf('%d '，p-value )； traverse_tree_inorder(p-right； }voidrecycle_nodes(node*p ) if ) p==null ) return； 接收周期_节点(p-left； recycle_nodes(p-right； free(p； }主题的核心是写tree.h的头文件。
头文件必须实现以下函数：
/*如果按中序遍历二叉树并按升序输出，则每个数之间会有一个空格，最后一个数之后也会有一个空格。 */void traverse _ tree _ in order (node * p )/*重用生成二叉树时打开的内存空间，提示类似于以后的遍历。 */Void回复
_nodes(Node *p);/*将一个值为value的数插入到这个树中，但是要注意，需要插到那个地方，按照排序二叉树的要求来。*/void insert_node(Node *p, int value);/*初始化根节点的值。*/Node* init_root(int value);首先是初始化根结点的值的函数：
Node* init_root(int value) { Node *root; root = malloc(sizeof(Node)); root->value = value; root->left = NULL; root->right = NULL; return root;}这个函数很简单，只需给根结点开辟一个空间后初始化即可。注意，要把结点内的左右指针置为空。
其次是构建二叉树，这是本题的难点。
void insert_node(Node *p, int value) { Node *pArr; pArr = malloc(sizeof(Node)); pArr->value = value; pArr->left = NULL; pArr->right = NULL; while (p->left != pArr && p->right != pArr) { while (value > p->value) { if (p->right == NULL) { p->right = pArr; return; } else { p = p->right; } } while (value < p->value) { if (p->left == NULL) { p->left = pArr; return; } else { p = p->left; } } } return;}这种构建二叉树的方法我称它为插入构造法。即将元素插入正确的位置。这种插入使得中序遍历输出一串有顺序的数字。那么，怎么插？
举个例子：
输入这些数据：23， 3， 53， 333， 2
输出： 2， 3， 23， 53， 333
第一个数字一定是给根结点赋值，所以不用判断。但接下来的数字都要进行判断，进而插入合适的位置。第二个数字3，将3与23比较，发现3小于23，所以将3成为23的左儿子。第三个数字53，将53与23比较，发现53大于23，因此53作为23的右儿子。第四个数字333，将333与23比较，发现333大于23，然而23的右儿子已经存在了，因此将333与23的右儿子53进行比较，发现333大于23，因此将333作为53的右儿子。第五个数字2，将其与23比较，发现2小于23，然而23的左儿子已经存在，因此将2与23的左儿子3比较，发现2小于3，因此将2作为3的左儿子。如此，排序二叉树就这样建立起来了。
你们可以通过这个例子了解插入的原理，然后自己用代码实现出来。
然后我要讲第三个函数中序遍历输出二叉树：
void traverse_tree_inorder(Node *p) { if (p == NULL) return; traverse_tree_inorder(p->left); printf("%d ", p->value); traverse_tree_inorder(p->right);}对于二叉树的遍历，我们一般通过递归实现，左子树一个递归，右子树一个递归，还有一个额外的操作。中序遍历就是先左子树的递归，再额外的操作，最后再右子树的递归。后序遍历也是这样，先左子树的递归，后右子树的递归，最后再额外的操作。前序遍历以此类推。此处的额外操作就是输出操作。
最后我要讲的是第四个函数：释放二叉树
void recycle_nodes(Node *p) { if (p == NULL) return; recycle_nodes(p->left); recycle_nodes(p->right); free(p);}因为二叉树的各个结点都是通过动态分配内存得来的，因此在程序终止前要将这些结点所分配的内存全部释放。不难发现其实释放的原理便是后序遍历。这里额外的操作就是释放内存，即free()。
3.总结其实二叉树很好玩，只要你搞懂原理哈哈～
先序遍历：对一棵二叉树的前序遍历，先访问根结点，再访问左子树，然后访问右子树。
void preorder(Treenode *p) { if (p!=NULL){ visit(p); preorder(p->left); preorder(p->right); }}中序遍历：对一棵二叉树的中序遍历，先访问左子树，再访问根结点，然后访问右子树。
void inorder(Treenode *p) { if (p!=NULL){ inorder(p->left); visit(p); inorder(p->right); }}后序遍历：对一棵二叉树的后序遍历，先访问左子树，再访问右子树，然后访问根结点。
void postorder(Treenode *p) { if (p!=NULL){ postorder(p->left); postorder(p->right); visit(p); }}以上内容皆为本人观点，欢迎大家提出批评和指导，我们一起探讨！