二叉排序树的构建与遍历

树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。二叉树的链式存储结构是一类重要的数据结构。
二叉树是每个结点最多只有两个子树的有序树。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^( i -1)个结点；深度为k的二叉树至多有2^k -1个结点；对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。

构造结点：

typedef struct _node{
    int data;
    struct _node *parent;//指向根结点
    struct _node *left;//指向左结点
    struct _node *right;//指向右结点
}node,*pnode;//*pnode为该结构体指针

申请结点：

pnode construct_node(int data){
    pnode temp = (pnode)malloc(sizeof(node));
    temp->data = data;
    temp->left = temp->right = temp->parent = NULL;
    return temp;
}

添加结点（构建二叉排序树）：

pnode add_node(pnode root,pnode newnode)
{
    if(root == NULL)
        return newnode;
    pnode temp = root;
    while(temp != NULL)
    {
        if(newnode->data < temp->data)
            {
               if(temp->left == NULL)
                   {    
                        temp->left = newnode;
                        return root;
                    } 
                else 
                    temp = temp->left;   
           }
        else
            {
                if(temp->right == NULL)
                    {
                        temp->right = newnode;
                        return root
                    }
                else
                    temp = temp->right;

            }          
    }
}

中序、前序、后序遍历：

void visit(pnode temp)
{
	printf("%d \n", temp->data);
}


//中序遍历（左-根-右）（中序相当于排序）
void inorder(pnode root)
{
	if (root == NULL)
		return;
	pnode temp = root;
	if(temp != NULL)
	{			
		inorder(temp->left);//访问左子节点
		visit(temp);//访问根结点
		inorder(temp->right);//访问右子结点
	}
}

//前序遍历（根-左-右）
void preorder(pnode root)
{
	if (root == NULL)
		return;
	pnode temp = root;
	if (temp != NULL)
	{
		visit(temp);
		preorder(temp->left);
		preorder(temp->right);
	}
}


//后序遍历（左-右-根）
void postorder(pnode root)
{
	if (root == NULL)
		return;
	pnode temp = root;
	if (temp != NULL)
	{
		postorder(temp->left);
		postorder(temp->right);
		visit(temp);
	}
}

应用：随机生成10个数，通过构建二叉排序树和中序遍历对其进行排序。

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

//构造结点
typedef struct _node {
	int data;
	struct _node *parent;
	struct _node *left;
	struct _node *right;
}node,*pnode;

//申请一个结点
pnode construct_node(int data) {
	pnode temp = (pnode)malloc(sizeof(node));
	temp->data = data;
	temp->left = temp->right = temp->parent = NULL;
	return temp;
}
//添加结点(构建二插排序树)
pnode add_node(pnode root, pnode newnode) {
	if (root == NULL)
		return newnode;
	pnode temp = root;
	while (temp != NULL)
	{
		if (newnode->data < temp->data)
		{
			if (temp->left == NULL)
			{
				temp->left = newnode; 
				return root;
			}
			else
				temp = temp->left;
		}
		else
		{
			if (temp->right == NULL)
			{
				temp->right = newnode;
				return root;
			}
			else
				temp = temp->right;
		}

	}
}

void visit(pnode temp)
{
	printf("%d \n", temp->data);
}
//中序输出（左-根-右）（中序相当于排序）
void inorder(pnode root)
{
	if (root == NULL)
		return;
	pnode temp = root;
	if(temp != NULL)
	{			
		inorder(temp->left);//访问左子节点
		visit(temp);//访问根结点
		inorder(temp->right);//访问右子结点
	}
}

int main()
{
	pnode root = NULL;
	int num = 10;
	for (int i = 0; i < num; i++)
	{
		pnode temp = construct_node(rand()%100);
		printf("%d ", temp->data);
		root = add_node(root, temp);
	}
	printf("\n");
	inorder(root);//中序输出（左-根-右）
}

参考文章：二叉树各种遍历