建立二叉排序（搜索）树
描述
输入一组数，对输入的数建立二叉树排序（搜索），并前中后序遍历二叉树。
28, 40, 20, 54, 66, 79
对待排序的数据进行排序定义二叉树结构体，递归建立二叉树递归前中后序遍历
定义二叉树节点结构体
struct TreeNode
{
int val
;
TreeNode
* left
;
TreeNode
* right
;
TreeNode(int x
) : val(x
), left(NULL), right(NULL){}
};
typedef struct TreeNode TreeNode
;
建立二叉排序树
TreeNode
* buildTree(int a
[], int l
, int r
){
if(r
<= l
){
return NULL;
}
int mid
= l
+ (r
- l
) / 2;
TreeNode
* root
;
root
= new TreeNode(a
[mid
]);
root
->left
= buildTree(a
, l
, mid
);
root
->right
= buildTree(a
, mid
+ 1, r
);
return root
;
}
前序遍历
void preOrderTraversal(TreeNode
* root
){
if(root
!= NULL){
printf("%d ", root
->val
);
preOrderTraversal(root
->left
);
preOrderTraversal(root
->right
);
}
}
中序遍历
void inOrderTraversal(TreeNode
* root
){
if(root
!= NULL){
inOrderTraversal(root
->left
);
printf("%d ", root
->val
);
inOrderTraversal(root
->right
);
}
}
后序遍历
void postOrderTraversal(TreeNode
* root
){
if(root
!= NULL){
postOrderTraversal(root
->left
);
postOrderTraversal(root
->right
);
printf("%d ", root
->val
);
}
}
全部代码
#include<bits/stdc++.h>
using namespace std
;
struct TreeNode
{
int val
;
TreeNode
* left
;
TreeNode
* right
;
TreeNode(int x
) : val(x
), left(NULL), right(NULL){}
};
typedef struct TreeNode TreeNode
;
TreeNode
* buildTree(int a
[], int l
, int r
){
if(r
<= l
){
return NULL;
}
int mid
= l
+ (r
- l
) / 2;
TreeNode
* root
;
root
= new TreeNode(a
[mid
]);
root
->left
= buildTree(a
, l
, mid
);
root
->right
= buildTree(a
, mid
+ 1, r
);
return root
;
}
void preOrderTraversal(TreeNode
* root
){
if(root
!= NULL){
printf("%d ", root
->val
);
preOrderTraversal(root
->left
);
preOrderTraversal(root
->right
);
}
}
void inOrderTraversal(TreeNode
* root
){
if(root
!= NULL){
inOrderTraversal(root
->left
);
printf("%d ", root
->val
);
inOrderTraversal(root
->right
);
}
}
void postOrderTraversal(TreeNode
* root
){
if(root
!= NULL){
postOrderTraversal(root
->left
);
postOrderTraversal(root
->right
);
printf("%d ", root
->val
);
}
}
int main(){
int a
[6] = {28, 40, 20, 54, 66, 79};
sort(a
, a
+ 6);
TreeNode
* root
= buildTree(a
, 0, 6);
preOrderTraversal(root
);
printf("\n");
inOrderTraversal(root
);
printf("\n");
postOrderTraversal(root
);
return 0;
}
l(root
);
printf("\n");
inOrderTraversal(root
);
printf("\n");
postOrderTraversal(root
);
return 0;
}
