二叉树(Binary Tree)的基本操作

发布于 / 数据结构与算法 / Comments Off on 二叉树(Binary Tree)的基本操作

0x00、树(Tree)

树是一种和链表一样重要的数据结构,与链表不同的是,树有着层次结构。

现实生活中的树,是由树根(root)树枝(edge),节点叶子(leaf)组成的。

在数据结构中的树,就像是把数连根拔起,再单脚朝天,也就是把现实生活中的树倒了过来。

树根位于顶部,树根向下形成了若干个树枝,树枝又向下形成了更多的树枝,向下延伸到达子节点(child)形成子树(subtree)

0x01、树的基本定义

下面是几个关于数的定义:

1,树可以没有节点,称之为空树(empty tree)

2,树是有层级(layer)之分的,根节点为第一层,根节点的子节点为第二层,根节点的子节点的子节点为第三层。以此类推

3,把节点的子树的棵树称为节点的度(degree),树中节点最大的度称为数的度,或树的宽度。上面图片的度为3

4,有n个节点的树(根节点也算一个节点)一定有(n-1)条边

5,叶子被定义为 度为0的节点,树中只有一个根节点的时候,根节点也算叶子

6,结点的深度(depth)指从根节点(根节点深度为1)开始,自顶向下逐层累加至该节点的深度值。结点的高度(height)指从最底层叶子结点(高度为1)开始,自底向上逐层累加至该节点的高度值。树的深度指的是树中结点的最大深度。树的高度是指树中结点的最大高度。一般来说,树的深度和高度是相等的。上面图片中的树的高度和深度都是3

7,多棵树组合在一起,称之为森林(forest)

0x02、二叉树的递归定义

二叉树是一种很重要的树,下面是它的定义:

1,如果二叉树没有根节点,则二叉树是一棵空树。

2,如果二叉树有结点,则二叉树由根节点、左子树、右子树构成。而且左子树和右子树都是二叉树。

二叉树的递归定义是一个很好理解的定义:

我们把二叉树想象称为亲缘血统关系,在血缘关系中,爷爷可以用“爸爸的爸爸”来表示,曾祖父可以用“爸爸的爸爸的爸爸”来表示。所以整个家谱都可以用“爸爸”来表示,这样就叫做递归定义。

下面是两种特殊的二叉树:

1,二叉树每一层节点个数都达到了当层所能达到的最大节点数,称之为满二叉树

2,二叉树除了最下面的一层,其余节点都达到了当层所能达到的最大节点数,称之为完全二叉树

如上图所示。

0x03、二叉树的C语言实现

二叉树的定义类似链表,与链表不同的是,链表只有一个指向下一节点的指针,而二叉树有两个分别指向左节点与右节点的指针。

定义方式如下:

struct node{
    ElementType data;
    node* lchild;    //LeftChild
    node* rchild;    //RightChild
};

这样我们定义了二叉树的结构,下面我们定义一棵空树:

node* root = NULL;

接着创建节点:

node* newNode(int v){
    node* Node = new node;    //申请node类型的地址空间
    Node->data = v;    //写入数据
    Node->lchild = Node->rchild = NULL;    //节点初始状态没有左右child
    return Node;
}

我们可以使用递归来搜索二叉树中的数据:

void search(node* root, int x){
    if(root == NULL)
        return;
    if(root->data == x)
        //找到了
        ;
    search(root->lchild, x);    //本节点没有,继续递归查找左节点
    search(root->rchild, x);    //左节点也没有,查找右节点
}

这段代码和DFS算法比较相似。具体问题要根据情况具体分析。在后面的文章中会详细讲解二叉树的遍历。

转载原创文章请注明,转载自: 斐斐のBlog » 二叉树(Binary Tree)的基本操作
评论已关闭