二叉树是一种非线性数据结构，本文实现的是二叉树的三种遍历方法，以及一种二叉搜索树，即左孩子节点的值小于根节点的值小于右孩子节点的值

对二叉树不了解的需要先了解二叉树，本文说的比较简练实用

• 二叉树的结构,二叉树的链式结构非常简单，即一个数据节点，加上两个孩子节点。

typedef struct BitNode
{
	int data;
	struct BitNode *left_child,*right_child;

}BitNode,*BitNode_ptr;

二叉树的遍历

二叉树的遍历方法总结起来一共分为三步：

• 按照顺序访问节点，前序，中序，后序，分别对应
  1 从根节点到左右孩子
  2 左孩子到根节点再到右节点
  3 左右孩子节点再到根节点
• 有孩子节点的优先遍历孩子节点
• 访问到根节点就输出数据

  把握住这三步，对于二叉树的遍历基本没有问题,对于前中后序遍历步骤不用记，前就是从上到下，后就是从下到上，中就是下到上再到下

/* 前序遍历 */
/* 根->左->右 */
void preOrder(BitNode_ptr T)
{
	if(T == NULL)
		return;
	printf("%d ",T->data);  	// 访问根节点
	preOrder(T->left_child); 	// 访问左节点
	preOrder(T->right_child);	// 访问右节点
}

/* 中序遍历 */
/* 左->根->右 */
void InOrder(BitNode_ptr T)
{
	if(T == NULL)
		return;
	InOrder(T->left_child);	   /* 访问左节点 */
	/* 一直遍历到最后的左节点才开始返回打印数据 */
	printf("%d ",T->data);	   /* 访问根节点 */
	InOrder(T->right_child);   /* 访问右节点 */
}

/* 后序遍历 */
/* 左->右->根  / 右->左->根 */
void PostOrder(BitNode_ptr T)
{
	if(T == NULL)
		return;
	PostOrder(T->left_child);  	/* 访问左节点 */
	PostOrder(T->right_child);    /* 访问右节点 */
	printf("%d ",T->data);	    /* 访问根节点 */
}

二叉搜索树

对于二叉树的掌握需要对递归有一定的理解

/* 1 创建一个二叉树节点 */
BitNode_ptr create_bitnode(int data)
{
	BitNode_ptr t = malloc(sizeof(struct BitNode));
	t->left_child = NULL;
	t->right_child = NULL;
	t->data = data;
}

/* 2 将二叉树节点插入到二叉树中（以二叉搜索树的方式） */
void add_bitree(BitNode_ptr T,BitNode_ptr t)
{
	if(T == NULL)  	//	 根节点
	{
		T = t;
		return;
	}
	if(t->data < T->data)	// 小于 放在左节点，有孩子节点先判断孩子节点
	{
		if(T->left_child != NULL)
			add_bitree(T->left_child,t);	
		else
			T->left_child = t;
	}
	else  					// 大于等于  放在右节点，有孩子节点先判断孩子节点
	{
		if(T->right_child != NULL)
			add_bitree(T->right_child,t);
		else 
			T->right_child = t;
	}
}

/* 返回二叉树的深度 */
int bit_tree_depth(BitNode_ptr T)
{
	static int depth = 0;
	int left_depth = 0,right_depth = 0;
	
	if(T == NULL)
		return 0;
	
	left_depth  = bit_tree_depth(T->left_child);
	right_depth = bit_tree_depth(T->right_child);
	
	depth = right_depth>left_depth ? right_depth : left_depth;
	
	return depth + 1;
}

测试程序

void main()
{
	
/* 创建根节点 */	
	T = create_bitnode(10);
	BitNode_ptr t;
	
/* 创建各个节点 */	
	t = create_bitnode(9);
	add_bitree(T,t);
	
    t = create_bitnode(20);
	add_bitree(T,t);
	
	t = create_bitnode(15);
	add_bitree(T,t);
	
	t = create_bitnode(35);
	add_bitree(T,t);

/* 三种遍历方式 */	
	preOrder(T);		
	printf("\n");
	InOrder(T);
	printf("\n");
	PostOrder(T);
	printf("\n");
	
/* 返回二叉树的深度 */	
    printf("depth is %d\r\n ",bit_tree_depth(T));
}

还有一些高级的二叉树，如二叉平衡树，红黑树等，如果需要掌握这些高级的数据结构，还是要下一定的功夫的。