文章目录

前言

对于大量的输入数据，链表的线性访问时间太慢，不宜使用。本章我们介绍一种简单的数据结构——树（二叉查找树），其大部分操作的运行时间平均为O(log N) 。

树基础

树的基础内容已经在离散数学中学习过了，这里复习一些简单的概念：

父母（Parent）：结点之上连接的结点，即结点的前驱。一棵树中，根节点没有父母，其他节点只有一个父母。
孩子（Child）：结点之下连接的结点，即结点的后继。
兄弟（Sibling）：具有相同父母的不同结点互为兄弟结点。
树叶（Leaves）：没有孩子的结点。一般在树的最下端。
路径（Path）：n₁ to n_k 的序列由结点{n1,n2,...,nk}组成，其中ni是ni+1的父母，1<=i<k;
深度（Depth）：从根节点到目标结点的路径长度，根节点处长度为0.
高度（Height）：从目标结点到一个树叶的最长路径长度，树叶处高度为0.
树的深度：从根结点到树叶的最长路径的长度。
树的高度：从树叶开始到根节点的最长路径的长度。
祖先（Ancestor）/后代(Descendant)：路径{n1,n2,...,nk}中，结点ni的祖先有{n1,n2,...,ni-1}，它的后代有{ni+1,ni+2,...,nk}。
层（Layer）：同辈分结点所在的层次称为层，根节点为第一层，往下一次递增。
度（Degree）：节点拥有的子树的个数，度为0的节点称之为叶子节点。

通常来说，在数值上树的深度=树的高度，但是因为出发点不同，其中结点的深度与高度不同，即深度是从上往下数的，高度是从下往上数的。如图：

（图片来自cnblog：https://www.cnblogs.com/jianglinliu/p/11197715.html）

接下来是简单的实现。首先我们可以使用链表的方式实现模拟树：

typedef struct tree_first
{
    int data;
    struct tree_first *Firstchild;
    struct tree_first *NextSibling;
}tree;

其中Firstchild表示这个节点的第一个孩子，NextSibling表示下一个兄弟（同一层的，同父母的）。当然这种方式还是有点复杂，因为一颗树会有很多个连接。

遍历

先序遍历

在先序遍历中，对节点的处理工作是在它的诸儿子节点被处理之前(pre)进行的。

先序遍历步骤为：访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。即根左右。

例如下面的这个树：

它遍历的顺序就是ABDECF

后续遍历

和先续遍历不同的是它的访问不是我们所想的从跟开始，而是从左开始：

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即左右根。

例如之前的这个树：它遍历的顺序就是DEBFCA

因此我们可以发现，这个先和后，指的是跟的先后。

中序遍历

在二叉树中还有一种中序遍历，按照我们之前的说法，它是跟的中序：中

序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。即左根右。

故之前的那颗树的遍历顺序是：DBEAFC

二叉树

二叉树(binary tree)是一棵树，其中每个节点至多有两个节点。

这意味着二叉树的一个节点可能有0、1、2个子节点。

我们把二叉树的深度设为N（层数-1），则根据二叉树的结构，二叉树的平均深度可以是O(√N)，而二叉查找树的深度则可以达到O(log N)。但前面讲的只是平均的，最坏的情况也能达到N-1的深度。

实现

因为一棵二叉树最多有两个儿子，所以我们可以用指针直接指向它们。树节点的声明在结构上类似于双链表的声明，在声明中，一个节点就是由数据信息（data）加上两个指向其他节点的指针(Left 和Right)组成的结构。

例如：

typedef struct binary_tree
{
    int data;
    struct binary_tree *left;
    struct binary_tree *right;
}tree;

遍历在树中一般通过简单的递归来实现：

/*前序遍历"AVL树"*/
void preorder_avltree(tree* r)
{
     if(r != NULL)
     {
         printf("%d ", r->key);
         preorder_avltree(r->left);
         preorder_avltree(r->right);
     }
}
/*中序遍历"AVL树" */
void inorder_avltree(tree* r)
{
    if(r != NULL)
   {
       inorder_avltree(r->left);
       printf("%d ", r->key);
       inorder_avltree(r->right);
   }
}
/*后序遍历"AVL树"*/
void postorder_avltree(tree* r)
{
    if(r != NULL)
    {
       postorder_avltree(r->left);
       postorder_avltree(r->right);
       printf("%d ", r->key);
    }
}

二叉树的一个重要的应用是它们在查找中的使用，接下来就是二叉查找树的内容。

二叉查找树

我们知道了二叉树，那什么是二叉查找树呢。它的定义是：

若其左子树非空，则左子树上所有节点各自的值都小于根节点的值
若其右子树非空，则右子树上所有节点各自的值都大于根节点的值
其左右子树都是一棵二叉查找树。

总结来说就是，根的左边比根小，根的右边比根大。

因此我们可以知道左子树<根<右子树，即二叉查找树的中序遍历是一个递增序列。

因为二叉查找树的中序遍历有序性，即得到的递增的序列，由于有序，因此其查找与二分查找类似，每次都可以缩小查找范围，查询效率较高。接下来我们就一步步完成这个树的功能定义。

MakeEmpty

我们在新建一个二叉查找树的时候，首先需要MakeEmpty。

tree *MakeEmpty(tree * r)  //传入root节点
{
    r=NULL;
    MakeEmpty(r->left);
    MakeEmpty(r->right);
    return r;
}

Find

接下来最主要的就是查找功能了，我们使用二叉查找树的查找类似于二分查找。因为比根小的都在左子树，比根大的都在右子树，所以我们只需要先和根比较，确定跳转的左右子树，连续和子树的根比较，找到最后的节点。我们使用递归的方式查找。

tree *Find(tree *r, int d)
{
    if(d == r->data) 
        return r;
    if(d > r->data)
        return Find(r->right,d);
    if(d < r->data)
        return Find(r->left,d);
    if(r == NULL) 
        return NULL;
}

我们拓展这个Find()函数，我们让它找到最大和最小的元素的地址。

根据这个结构，我们知道找到最小值，一定是先一直往左子树找。如果找到头了就可以返回了。因为左边的一定比右边的要小。同理找最大值也是这样。

tree *FindMin(tree *r)
{
    if(r == NULL)
        return NULL;
    if(r->left != NULL)
        return r->left;
    else return r;
}

当然也可以不用递归的方法，例如：

tree *FindMax(tree *r)
{
    if(r == NULL)
        return NULL;
    while(r->right!=NULL)
        r=r->right;
    return r;
}

Insert

插入操作是我们添加节点的方法。和查找一样，我们也可以通过类似的方式找到应该插入的位置。（如果有根的情况）

所以我们这时就要单独讨论是否为空的情况了。当然还有另外一种情况，就是重复元。我们插入的元素如果重复怎么办，这时候更好的解决方案就是用一个辅助的数据结构来存储元素的次数，而不是强行插入进树里。

一个基础的写法应该是这样的：

tree *Insert(tree *r, int d)
{
    if(r==NULL)
    {
        r=(tree *)malloc(sizeof(tree));
        if(r==NULL)
        {
            printf("Out of Space!\n");
            exit(-1);
        }
        r->left=r->right=NULL;
        r->data=d;
    }
    if(d < r->data)
        return Insert(r->left,d);
    if(d > r->data)
        return Insert(r->right,d);
    return r;    //这里是如果相同什么都不做
}

如果我们要记录一下重复元的话，可以使用一个数组，在那一位加一，或者在建树的时候结构处多加一个成员来记录频率都可以。

Delete

到了删除这里，我们也需要考虑一些特殊情况。如果删除的节点是片树叶，那么就可以立刻把它删了。如果是删除的节点有一个子节点，那么该节点可以在其父节点调整指针绕过该节点后被删除。

但如果是存在两个子节点，就会比较复杂。一般的删除策略是用其右子树的最小的数据（很容易找到）代替该节点的数据（此时这个最小数据也会比左节点大）并递归地删除那个节点（现在它是空的）。因为右子树中的最小的节点不可能有左儿子，所以第二次Delete容易。

例如，删除下面这棵树的(2)这个节点，我们找到了右子树中最小的3，把原来的(2)替换为(3)，此时在右子树中相当于删除了(3)，故连接(4)在(5)之下。

tree *Delete(tree *r, int d)  //查找同时删除
{
    if(r==NULL)
        return NULL;
    if(d < r->data)
        r->left=Delete(r->left,d);
    else if(d > r->data)
        r->right=Delete(r->right,d);    
    else if(r->left==NULL && r->right==NULL)    //找到了并且是树叶
    {
        tree *p=r;
        r=NULL;
        free(p);
    }
    else if(r->left && r->right)    //当前节点有左右子树
    {
        /*用右子树的最小值代替该节点，并且递归删除该最小值节点*/
        tree *p=FindMin(r->right);
        r->data=p->data;
        r->right=Delete(r->right,r->data);
    }
    return r;
}

但是这样删除的效率并不高，因为它沿该树进行两趟搜索以查找和删除右子树中最小的节点。当然我们还可以查找了再删除，但是这样同样需要查找两次（找到父节点）。

这是我的代码，可能有错误，仅供参考。

tree *Delete_find(tree *r, int d)
{
    tree *q=Find(r,d);
    if(q==r)    //root
    {
        free(q);
        return NULL;
    }
    tree *p=Find_Pre(r,d);
    int pos=1;    //删除位置是父节点的左节点为1，右为2
    if(p->right == q) pos=2;
    if(q->left==NULL && q->right==NULL)
    {
        if(pos==1)
            p->left=NULL;
        else p->right=NULL;
        free(q);
            return p;
    }
    if(q->left && !q->right)
    {
        if(pos==1) p->left=q->left;
        else p->right=q->left;
        free(q);
        return p;
    }
    if(!q->left && q->right)
    {
        if(pos==1) p->left=q->right;
        else p->right=q->right;
        free(q);
        return p;
    }
    if(q->left && q->right)
    {
        tree *m=FindMin(q->right);
        q->data=m->data;
        tree *t=Delete_find(r,m->data);
    }
    return q;
}

tree *Find_Pre(tree *r, int d)    //找到父节点
{
    if(d == r->left->data || d == r->right->data) 
        return r;
    if(d > r->data)
        return Find(r->right,d);
    if(d < r->data)
        return Find(r->left,d);
    if(r->left == NULL && r->right == NULL) 
        return NULL;
}

学习下别人的代码：https://blog.csdn.net/xiexiexiexieqing/article/details/117468490

void del(struct node*root,int data)
{
	struct node*pnode=root;   
	struct node*pnodeparent;
	while(pnode!=NULL && pnode->data!=data)  //先找到这个节点 
	{
		pnodeparent=pnode;       //父节点必须在子节点上面 
		if(data>pnode->data)
		pnode=pnode->right;
		else
		pnode=pnode->left;
	}
	if(pnode==NULL)    //当pnode为空 意思是把这颗树都找遍了 还是没有 
	{
		printf("没有");   //所以 返回时  要有一个提示 
		return ;
	}
	if(pnode->left!=NULL&&pnode->right!=NULL)  //删除节点的子节点都存在 
	{
		struct node*pmove=pnode->left;     //找左边的最大节点 
		struct node*pmoveparent;
		while(pmove->right!=NULL)
		{
			pmoveparent=pmove;
			pmove=pmove->right;
		}
		pnode->data=pmove->data;  //把这个最大节点的值赋给 删除节点 
		pnode=pmove;              //现在相当于删除这个 最大节点 
		pnodeparent=pmoveparent;
	}
	struct node*snode;      //定义一个节点 
	if(pnode->left!=NULL)   //获取 最大节点的子节点 
	snode=pnode->left;
	else                     //不存在子节点就赋值NULL 
	snode=NULL;         
	if(pnodeparent==NULL)  //如果父节点为空那么就是 空树  还是把获取到的节点给它 
	pnodeparent=snode;
	else if(pnodeparent->right==pnode)
	pnodeparent->right=snode;
	else
	pnodeparent->left=snode;
	free(pnode);
 }