©2020-2024 ioDraw All rights reserved
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; }