数据结构 の 树

2021/7/17 6:06:50

本文主要是介绍数据结构 の 树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

树的定义

由唯一的根和若干互不相交的子树,每一颗子树又是一棵树。

相关概念

  • 结点的度:拥有子树的个数
  • 树的度:树中各节点度的最大值
  • 双亲节点:
  • 祖先节点:他上边所有的节点都是祖先节点
  • 森林:把树的根去掉,剩下的树就构成了森林

树的存储结构

树的存储有两种方式:顺序存储链式存储

顺序存储:一般使用称双亲存储,一组数组就可以搞定

如知道了节点 i,那么 tree[i] 就是 i 的双亲节点
在这里插入图片描述

链式存储包括

孩子存储结构.

左孩子指针 数据 右孩子指针
lchild data rchilid

数据结构如下:

1
2
3
4
5
type BTNode struct {
    data    int
    lchild  *BTNode
    rchilid *BTNode
}

孩子兄弟存储结构。

image

二叉树

在普通树上再加两个条件,就构成了完全二叉树。

  • 每个节点最多有两个子树
  • 子树有左右之分,不能颠倒

二叉树又分为满二叉树,完全二叉树,完全二叉树是由满二叉树由右到左,从下到上排着删得到的。不能跳着删除

二叉树主要性质

  • 非空二叉树的叶子结点数,等于双分支结点数+1;
  • 在二叉树的第 i 层上,最多有 2i-1个结点。
  • 对于 k 层深的树,最多有 2k -1 个节点

对于完全二叉树的第 i 结点来说:

  • i 的双亲节点为 【i/2】向下取整

  • 如果 n>=2i 那么 i 的左孩子的编号为 2i ,如果 n<2i 则无左结点

  • 如果n>=2i+1,则右节点为 2i+1,如果 n<2i+1 则无右节点

在这里插入图片描述

二叉树的遍历

  • 先序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
type treeNode struct {
    data   int
    lchild *treeNode
    rchild *treeNode
}
 
// 先序遍历
func preorder(treenode *treeNode) {
    if treenode != nil {
        Visit(treenode)
        preorder(treenode.lchild)
        preorder(treenode.rchild)
    }
}
  • 总序遍历
  • 后序遍历
  • 层次遍历

二叉树的层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func Level(node *BTNode) {
    que := make([]*BTNode, 20) //20长的循环队列
    front, rear := 0, 0        //初始化队列,当front=rear表示队为空
                               //rear+1=front 表示队列已经满了。
    if node != nil {
        rear = (rear + 1) % 20  // 根节点入队
        que[rear] = node   
        for front != rear { // 如果不是空队
            front = (front + 1) % 20
            q := que[front] // 跟节点出队
            Visit(q)
            if q.lchilid != nil { // 如果有左节点就是入队
                rear = (rear + 1) % 20
                que[rear] = q.lchilid
            }
            if q.rchilid != nil { // 如果有右节点就入队
                rear = (rear + 1) % 20
                que[rear] = q
            }
        }
    }
}

常见问题

如何求一颗二叉树的深度

二叉树的深度,就是左右子树中,深度最大的,然后再加一; 所以步骤是,先求左子树,再求右子树,最后求 max{左,右}+1

森林还有树

森林还有树之间的转换,孩子兄弟链表的存储方式,具体还是看书吧。

赫夫曼树 (最小代价树)

赫夫曼树又叫最优二叉树,它的特点是带权路径最短。

在这里插入图片描述

赫夫曼树的构造过程

在这里插入图片描述

  • 先从所有的节点中,找出两个权值最小的节点
  • 将这两个节点构成一个新的树,然后,然后根节点权值就是左右之和
  • 把这个节点放到之前的节点中去
  • 以此类推着写

赫夫曼树的特点:

  • 权值越大,和根节点的距离越近
  • 树中没有度为 1 的节点,这类树叫做严格二叉树
  • 树的带权路径长度最短


这篇关于数据结构 の 树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


原文链接: https://www.cnblogs.com/rush-peng/p/15022403.html
扫一扫关注最新编程教程