Tree search (bintree)

介绍

We are in the usual search algorithm,The most are often sequential search and halved search,And the tree search is often half-understood,This article mainly introduces the creation of binary sorting tree,插入和查找.

树的定义

树是一种数据结构,它是由n(n≥0)个有限节点组成一个具有层次关系的集合.把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的.它具有以下的特点：
每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树.
If a tree contains at most two subtrees at each node, it is called a binary tree.
The program definition of a binary tree is generally as follows：

typedef char Elemtype ;
typedef struct BiNode
{
    
    Elemtype data;
    struct BiNode *lchild,*rchild;
}*BiTree;

二叉排序树的插入

添加一个值为knode to the treeT上.

int BST_inser(BiTree T,Elemtype k)
{
    
    if(T==NULL)
    {
    
        T=(BiTree)malloc(sizeof(BiNode));
        T->data=k;
        T->lchild=NULL;
        T->rchild=NULL;
        return 1;//插入成功
    }
    else if(T->data==k)
    {
    
        return 0;
    }
    else if(T->data>k)
    {
    
       return BST_inser( T=T->lchild,k);
    }
    else 
    {
    
        return BST_inser(T=T->rchild,k);
    }

}

二叉排序树的创建

The creation of a binary sorted tree is actually to create an empty tree,Then a set of data is stored in this tree species in turn.

void Creat_BST(BiTree &T,Elemtype a[],int n)
{
    
    T=NULL;//初始时T为空树
    int i=0;
   while(i<n)
   {
    
    BST_inser(T,a[i]);
    i++;
   }
}

树形查找

Searching a binary sorted tree is actually very simple,is the valuekfrom the root node of the sorted tree,Descending in turn,当kgreater than the current alignmentTnode value,Find this nodeT的右孩子,当ksmaller than the current alignmentTnode value,Find this nodeT的左孩子,When equal to the value of this node,Return this node.

BiNode *Bst_search(BiTree T,Elemtype k)
{
    
    while(T!=NULL&&T->data!=k)
    {
    
        if(k<T->data)
            T=T->lchild;
        else
            T=T->rchild;
    }
    return T;
}

后续

如果想了解更多物联网、智能家居项目知识,可以关注我的项目实战专栏和软硬结合专栏.
欢迎关注公众号了解更多.

编写不易,感谢支持.