二叉树的创建,二叉搜索树的创建,(前序,中序,后序遍历)
程序员文章站
2022-05-16 11:25:43
...
二叉树
概念性质:二叉树的每个结点最多有两个子节点,左孩子和右孩子,以他们为根,有左子树和右子树。第i层最多有2^(i-1)个结点,如果每层都是满的,就是满二叉树。如果只在最后一层缺失,缺失的都在最后,就是完全二叉树。
完全二叉树
结点数量为k,i>1,父节点为i/2,2i>k,i没有孩子,2i+1>k,i没有右孩子。如果i有孩子,左孩子为2i,右孩子为2i+1。
二叉树创建
struct node
{
int date;
struct node *left;//为node类型,结点
struct node *right;
};
/*node 为结点的结构,包含数值,左孩子的指针,右孩子的指针。
*/
二叉树的遍历
//前序遍历
/*前序遍历,遍历顺序为 根->左->右
递归的方式,先把根输出,然后去找它的左孩子,一直找,直到为NULL,然后回溯找右孩子。当一个根节点的左右都找完了,回溯到上一个,直到全部遍历结束。
*/
void preorder(struct node *x)
{
if(x!=NULL){
cout<<x->date<<" ";
preorder(x->left);
preorder(x->right);
}
}
//中序遍历
/*中序遍历,遍历顺序为 左->根->右
递归,先走左边,直到走到空,回溯,然后输出根节点的值,在去找右边,直到空,就回溯。
*/
void inorder(struct node *x)
{
if(x!=NULL){
inorder(x->left);
cout<<x->date<<" ";
inorder(x->right);
}
}
//后序遍历
/*递归,遍历顺序为 左->右->根
先走左边,左边走到空,回溯,走右边,右边也为空,回溯,然后输出根节点,回溯结点
*/
void postorder(struct node *x)
{
if(x!=NULL){
postorder(x->left);
postorder(x->right);
cout<<x->date<<" ";
}
}
二叉搜索树(BST)
概念:首先必须是一颗二叉树,然后根节点>左结点,根节点<右节点。二叉搜索树能降低复杂度。
将a[8]={6,3,8,2,5,1,7}拼成一颗二叉搜索树
二叉搜索树的建立
struct node//建立结点
{
int date;
struct node *left;
struct node *right;
};
struct tree//建立二叉搜索树
{
struct node *root;//可以根据 根节点 就能找到这颗树
};
二叉搜索树的插入
void insert(struct tree *tre,int x)//要插入的那棵树,插入的数值
{
struct node *p=(struct node*)malloc(sizeof(node));//分配空间
p->date=x;p->left=NULL;p->right=NULL;//将插入的数值打包成一个结点
if(tre->root==NULL){//根结点是空,插入的结点为根节点
tre->root=p;
}
else{
struct node *temp=tre->root;//用来比较大小的结点,开始为根结点
while(temp!=NULL)//直到比较的函数为空,就可以插入退出了
{
if(x<temp->date){//如果比结点小,就放在左边
if(temp->left==NULL){//左边为空
temp->left=p; return ;//就放在左边,退出
}
else{
temp=temp->left;//比较结点更新为左边
}
}
else{
if(temp->right==NULL){//右边为空
temp->right=p; return ;//就放在右边,退出
}
else{
temp=temp->right;//比较结点更新为右边
}
}
}
}
}
二叉搜索树的高度
高度由根结点的左右子树的高度的最大值+1,所以是一个递归求高度
int get_height(struct node *x)
{
if(x==NULL){//递归出口,如果是空结点,高度为0
return 0;
}
else{
int left_h=get_height(x->left);//左子树的高度
int right_h=get_height(x->right);//右子树的高度
int maxx=max(left_h,right_h);//最大值
//cout<<maxx<<endl;
return maxx+1;//左右子树的最大值+1
}
}
二叉搜索树求最大值
即为最右最右的那个数字,也是递归,比较根节点左右子树的最大值,与根节点比较,他们三个的最大值,即为树的最大值。
int get_maxx(struct node *x)
{
if(x==NULL){//如果结点为空,没有最大值
return -1;
}
else{
int left_maxx=get_maxx(x->left);//左子树的最大值
int right_maxx=get_maxx(x->right);//右子树的最大值
int maxx=max(left_maxx,right_maxx);
maxx=max(maxx,x->date);//三者的最大值
return maxx;
}
}
二叉搜索树的遍历与二叉树的遍历一样。
二叉搜索树的中序遍历就是从小到大的排序。
最初提出的那个问题,把a[8]={6,3,8,2,5,1,7}拼成一颗二叉搜索树。
完整代码
注意一下完整代码中指针的建立和传输
#include<bits/stdc++.h>
using namespace std;
struct node
{
int date;
struct node *left;
struct node *right;
};
struct tree
{
struct node *root;
};
void insert(struct tree *tre,int x)
{
struct node *p=(struct node*)malloc(sizeof(node));
p->date=x;p->left=NULL;p->right=NULL;
if(tre->root==NULL){
tre->root=p;
}
else{
struct node *temp=tre->root;
while(temp!=NULL)
{
if(x<temp->date){
if(temp->left==NULL){
temp->left=p; return ;
}
else{
temp=temp->left;
}
}
else{
if(temp->right==NULL){
temp->right=p; return ;
}
else{
temp=temp->right;
}
}
}
}
}
int get_height(struct node *x)
{
if(x==NULL){
return 0;
}
else{
int left_h=get_height(x->left);
int right_h=get_height(x->right);
int maxx=max(left_h,right_h);
//cout<<maxx<<endl;
return maxx+1;
}
}
int get_maxx(struct node *x)
{
if(x==NULL){
return -1;
}
else{
int left_maxx=get_maxx(x->left);
int right_maxx=get_maxx(x->right);
int maxx=max(left_maxx,right_maxx);
maxx=max(maxx,x->date);
return maxx;
}
}
void preorder(struct node *x)
{
if(x!=NULL){
cout<<x->date<<" ";
preorder(x->left);
preorder(x->right);
}
}
void inorder(struct node *x)
{
if(x!=NULL){
inorder(x->left);
cout<<x->date<<" ";
inorder(x->right);
}
}
void postorder(struct node *x)
{
if(x!=NULL){
postorder(x->left);
postorder(x->right);
cout<<x->date<<" ";
}
}
int main ()
{
ios::sync_with_stdio(false);
int a[10]={6,3,8,2,5,1,7};
struct tree t;
t.root=NULL;
for(int i=0;i<7;i++){
insert(&t,a[i]);
}
preorder(t.root);
cout<<endl;
inorder(t.root);
cout<<endl;
postorder(t.root);
cout<<endl;
int h=get_height(t.root);
cout<<h<<endl;
int maxx=get_maxx(t.root);
cout<<maxx<<endl;
return 0;
}
输出,还有别的什么,等我再学学,再来总结哈
上一篇: 遍历二叉树的叶子结点
下一篇: 有关php数组合并与递归合并的例子