欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的创建,二叉搜索树的创建,(前序,中序,后序遍历)

程序员文章站 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;
}

输出,还有别的什么,等我再学学,再来总结哈

相关标签: 杂识