必会编程基础知识:二叉树

今日知识点:二叉树

全文字数: 772

阅读时间:5分钟

什么是二叉树?

二叉树是每个结点最多有两个子树的树结构。如果一个节点有3个子树,就不能称之为二叉树。例如下图b的二叉树,A的左子树是T B Z部分,它的右子树是X这一部分,而X的左子树又是C Y这部分,右子树就是P,这就是二叉数。

二叉树的特点

1. 非空二叉树只有一个根结点

2. 每一个结点最多有两颗子树,且分别被称为该结点的左子树和右子树

二叉树的基本性质

性质1:在二叉树的第k层上,最多有2k-1(k>=1)个结点。

性质2:深度为m的二叉树最多有2m-1个结点。21-1+22-1+…+2m-1=2m-1

性质3:在任意一颗二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。 n0=n2+1

性质4:具有n个结点的二叉树,其深度至少为[log2n]+1。其中[log2n]表示取log2n的整数部分

满二叉树

除最后一层外,每一层上的所有结点都有两个子结点,如下图所示。

完全二叉树

除最后一层外,每一层上的结点数达到最大值;在最后一层上只缺少右边若干结点。

注:具有n个结点的完全二叉树的深度为[log2n]+1

二叉树的存储结构

二叉树通常采用链式存储结构。每个结点由数据域和指针域两部分组成。

数据域:用于存放结点中的数据

指针域:又分左指针域、右指针域,分别用于存放左子节点、右子结点的存储地址。

以下图这棵二叉树为例,看一下它的逻辑结构是怎样的。

其中BT指向的是二叉树的头指针。

再来简单看一下,它的物理存储结构是什么样子。i相当于计算机中的存储地址。

二叉树的前序遍历

前序遍历(DLR)根->左->右

若二叉树为空,则结束;否则:

1.访问根节点

2.前序遍历左子树

3.前序遍历右子树

二叉树的中序遍历

中序遍历 (LDR)左->根->右

若二叉树为空,则结束;否则:

1.中序遍历左子树

2.访问根节点

3.中序遍历右子树

二叉树的后序遍历

后序遍历(LRD)左->右->根

若二叉树为空,则结束;否则:

1.后序遍历左子树

2.后序遍历右子树

3.访问根节点

怎么样?是不是其实也不难

二叉树是计算机二级必须会的考点

也是学习编程很重要的基础知识

今天搞定它了吧~

1元团购通关二级、更多编程干货

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180818G1D3VP00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券