学步园

86.
怎样编写一个程序，把一个有序整数数组放到二叉树中？
分析:本题考察二叉搜索树的建树方法，简单的递归结构。关于树的算法设计一定要联想到
递归，因为树本身就是递归的定义。而，学会把递归改称非递归也是一种必要的技术。毕竟，
递归会造成栈溢出，关于系统底层的程序中不到非不得以最好不要用。但是对某些数学问题，
就一定要学会用递归去解决。

/*
86.
怎样编写一个程序，把一个有序整数数组放到二叉树中？
分析:本题考察二叉搜索树的建树方法，简单的递归结构。关于树的算法设计一定要联想到
递归，因为树本身就是递归的定义。而，学会把递归改称非递归也是一种必要的技术。毕竟，
递归会造成栈溢出，关于系统底层的程序中不到非不得以最好不要用。但是对某些数学问题，
就一定要学会用递归去解决。

有序的，直接中间分开 左右子树建立递归 
*/
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define N 101
struct  Node{
	int data;
	struct Node *left,*right;
}; 


Node* bulidTree(int array[], int start, int end) 
{
	if (start>end) 
		return NULL;
	int m=(start+end)/2;
	Node *root=(Node*)malloc(sizeof(Node));
	root->data=array[m];
	root->left=bulidTree(array,start,m-1);
	root->right=bulidTree(array,m+1,end);
	return root;
} 

// 中序遍历 左根右 
void displayTreeMid(Node *head) 
{
	if(head->left)
		displayTreeMid(head->left);
	printf("%d ",head->data);
	if(head->right)
		displayTreeMid(head->right);
}
// 前序遍历 根左右 
void displayTreeFore(Node *head) 
{
	printf("%d ",head->data);
	if(head->left)
		displayTreeFore(head->left);
	if(head->right)
		displayTreeFore(head->right);
}

// 后序遍历 左右根 
void displayTreeBack(Node *head) 
{
	if(head->left)
		displayTreeBack(head->left);
	if(head->right)
		displayTreeBack(head->right);
	printf("%d ",head->data);
}

int main()
{
	/*
			  5
		  2	     7
		1  3   6  8
		    4      9
	中序遍历：1 2 3 4 5 6 7 8 9
	前序遍历：5 2 1 3 4 7 6 8 9
	后序遍历：1 4 3 2 6 9 8 7 5
	*/
	int array[]={1,2,3,4,5,6,7,8,9};
	Node *root;
	root=bulidTree(array,0,sizeof(array)/sizeof(int)-1);
	printf("中序遍历：");
	displayTreeMid(root);
	printf("\n");
	 
	printf("前序遍历：");
	displayTreeFore(root);
	printf("\n");
	
	printf("后序遍历：");
	displayTreeBack(root);
	printf("\n");
	return 0;
}