©2020-2024 ioDraw All rights reserved
86.
How to write a program , Put an ordered array of integers into a binary tree ?
analysis : This paper investigates the construction method of binary search tree , Simple recursive structure . The algorithm design of tree must be associated with
recursion , Because the tree itself is the definition of recursion . and , Learning to change the name of recursion to non recursion is also a necessary technique . after all ,
Recursion can cause stack overflow , On the system of the underlying program must not be used . But for some mathematical problems ,
We must learn to use the return to solve .
/* 86. How to write a program , Put an ordered array of integers into a binary tree ? analysis : This paper investigates the construction method of binary search tree , Simple recursive structure . The algorithm design of tree must be associated with
recursion , Because the tree itself is the definition of recursion . and , Learning to change the name of recursion to non recursion is also a necessary technique . after all ,
Recursion can cause stack overflow , On the system of the underlying program must not be used . But for some mathematical problems , We must learn to use the return to solve . Orderly , Direct middle separation Left and right subtrees establish recursion */
#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; } // Middle order traversal Left root right void displayTreeMid(Node *head) { if(head->left)
displayTreeMid(head->left); printf("%d ",head->data); if(head->right)
displayTreeMid(head->right); } // Preorder traversal Left and right roots void displayTreeFore(Node *head) {
printf("%d ",head->data); if(head->left) displayTreeFore(head->left);
if(head->right) displayTreeFore(head->right); } // Postorder traversal Left and right roots 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 Middle order traversal ：1 2 3 4 5 6 7 8 9 Preorder traversal ：5 2 1 3 4 7 6 8 9
Postorder traversal ：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(" Middle order traversal ：");
displayTreeMid(root); printf("\n"); printf(" Preorder traversal ："); displayTreeFore(root);
printf("\n"); printf(" Postorder traversal ："); displayTreeBack(root); printf("\n"); return 0; }
Technology