数据结构简单入门/复习(四)-树与二叉树的知识介绍(C语言)

在 栈与队列 树与二叉树 这两个章节之前还有 串 和 数组与广义表,但字符串与数组的基本使用并没有值得注意的,因此跳过。

这部分介绍树与二叉树的知识点,各种实现代码将在后续章节补充。

树的定义

右图便是一种树,A是树的根,树的编号按层序遍历编号。

一棵非空树中,(1)有且只有一个根(root)(2)除根结点外的其他结点可以组成多个互不相见的树,被称为根的子树。

树的结点:包含一个数据元素及若干指向其子树的分支。
结点的度:结点拥有的子树个数。
叶子/终端结点:度为零,即没有子树。
非终端节点/分支结点:度不为零。
树的度:取 树内各结点的度 的最大值。
孩子/孩子结点:结点的子树的根,即子树中与结点相邻的结点。
双亲/父结点:上述关系(孩子结点)的颠倒。
兄弟/兄弟结点:拥有同一个父结点的结点。
祖先:父结点的父结点的父结点的…结点。
子孙:孩子结点的孩子结点的孩子结点的…结点。

结点的层次:树的根为第一次,其孩子为第二层…
深度:取 树中结点层次 的最大值。
有序树:子树有序,不可交换。
无序树:子树无序,可以交换。
森林:多棵不相交树的集合。

二叉树的定义、性质

二叉树是一种特殊的树,每个结点最多只有两棵子树,且子树有左右之分,是有序树。

性质1:在二叉树的第i层至多有2^(i-1)个结点(i>=1)。
性质2:深度为k的二叉树至多有(2^k)-1个结点(k>=1)。
性质3:对于任何一棵二叉树T,若其叶子/终端结点数为N,度为2的结点数为M,啧N=M+1。
性质4:具有n个结点的完全二叉树的深度为 (log2 n)+1,log2 n向下取整。
性质5:对一棵n个结点的完全二叉树的结点按层序编号,则对任意结点i(1<=i<=n),有:
(1)若 i=1,则 i 是二叉树的根,若 i>1,则双亲是是 i/2,向下取整。
(2)若 2i>n,则结点 i 无孩子结点(是叶子),相反,则其左孩子是结点 2i。
(3)若 2i + 1 > n,则结点i无右孩子,相反,其右孩子是结点 2i+1。

二叉树的遍历

前三种遍历只在于根的位置不同,先序在左,中序在中,后序在右,方便记忆。
先序遍历:根左右
中序遍历:左根右
后序遍历:左右根
层序遍历:按层,从左到右排序

对于右图的完全二叉树,各遍历分别为:
先序遍历:124536
中序遍历:425163
后序遍历:452631
层序遍历:123456

满二叉树:深度为k,且又(2^k)-1个结点的二叉树
完全二叉树:满二叉树按层序遍历编号,缺少最后n个结点的二叉树,其的叶子结点只出现在最后两层。上图即为一种完全二叉树。

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注