数据结构第四章树(一)线索二叉树

1. 树的基本概念

(1) 树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关
系构成的。集合中的元素称为树的节点&＃xff0c;所定义的关系称为父子关系。父子关系在树的
节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位&＃xff0c;
这个节点称为该树的根节点&＃xff0c;或称为树根。
(2) 空集合也是树&＃xff0c;称为空树。空树中没有节点&＃xff1b;
(3) 孩子节点或子节点&＃xff1a;一个节点含有的子树的根节点称为该节点的子节点&＃xff1b;
(4) 节点的度&＃xff1a;一个节点含有的子节点的个数称为该节点的度&＃xff1b;
(5) 叶节点或终端节点&＃xff1a;度为0的节点称为叶节点&＃xff1b;
(6) 非终端节点或分支节点&＃xff1a;度不为0的节点&＃xff1b;
(7) 双亲节点或父节点&＃xff1a;若一个节点含有子节点&＃xff0c;则这个节点称为其子节点的父节点&＃xff1b;
(8) 兄弟节点&＃xff1a;具有相同父节点的节点互称为兄弟节点&＃xff1b;
(9) 树的度&＃xff1a;一棵树中&＃xff0c;最大的节点的度称为树的度&＃xff1b;
(10) 节点的层次&＃xff1a;从根开始定义起&＃xff0c;根为第1层&＃xff0c;根的子节点为第2层&＃xff0c;以此类推&＃xff1b;
(11) 树的高度或深度&＃xff1a;树中节点的最大层次&＃xff1b;
(12) 节点的祖先&＃xff1a;从根到该节点所经分支上的所有节点&＃xff1b;
(13) 子孙&＃xff1a;以某节点为根的子树中任一节点都称为该节点的子孙&＃xff1b;
(14) 森林&＃xff1a;由棵互不相交的树的集合称为森林。


2. 二叉树

(1) 二叉树的定义及其主要特征a. 二叉树的基本形态&＃xff1a;空二叉树、单节点二叉树、左子树、右子树b. 性质&＃xff1a;[1] 在非空二叉树中&＃xff0c;第i层上至多有2^(i-1) 个结点。[2] 深度为k的二叉树至多有2^k - 1个结点[3] 对任何一棵二叉树&＃xff0c;若其叶子结点数为n0&＃xff0c;度为2的结点数为n2&＃xff0c;则n0 &＃61; n2 &＃43; 1。[4] n个结点的完全二叉树深度为&＃xff1a;log2(n)向下取整 &＃43; 1[5] 二叉树的堆式存储: 节点p的左儿子&＃xff1a;2x&＃xff0c;右儿子&＃xff1a;2x&＃43;1c. 两种特殊的二叉树[1] 满二叉树&＃xff1a;一颗深度为k且有2^k-1个结点的二叉树[2] 如果深度为k,有n个结点的二叉树&＃xff0c;当且仅当其每个结点都与深度为k的满二叉树中编号从1到n的结点一一对应&＃xff0c;该二叉树称为完全二叉树
(2) 二叉树的顺序存储结构和链式存储结构
(3) 二叉树的遍历a. 前序遍历b. 中序遍历c. 后序遍历d. 根据前序 &＃43; 中序重建二叉树&＃xff08;AcWing 18)
(4) 线索二叉树的基本概念和构造对二叉树节点的指针域做如下规定&＃xff1a;a. 若节点有左孩子&＃xff0c;则Lchild指向左孩子&＃xff0c;否则指向直接前驱&＃xff1b;右孩子同理&＃xff1b;b. 增加两个标志域&＃xff0c;Ltag表示指向的是子节点还是前驱&＃xff1b;Rtag同理c. 指向前驱和后继的指针叫做线索。按照某种次序遍历&＃xff0c;加上线索的二叉树称之为线索二叉树


3. 树、森林

(1) 树的存储结构a. 只存父节点b. 邻接表存储所有子节点c. 左儿子右兄弟
(2) 森林F与二叉树T的转换a. 原树中叶子节点数 &＃61; 转换后的树中有右儿子的节点数 &＃43; 1b. F的前序遍历就是T的前序遍历c. F的后序遍历就是T的中序遍历
(3) 树和森林的遍历a. 前序遍历b. 后序遍历


4.线索二叉树

对二叉树节点的指针域做如下规定&＃xff1a;
a. 若节点有左孩子&＃xff0c;则Lchild指向左孩子&＃xff0c;否则指向直接前驱&＃xff1b;右孩子同理&＃xff1b;
b. 增加两个标志域&＃xff0c;Ltag表示指向的是子节点还是前驱&＃xff1b;Rtag同理
c. 指向前驱和后继的指针叫做线索。按照某种次序遍历&＃xff0c;加上线索的二叉树称之为线索二叉树

例如:按照中序遍历&＃xff0c;节点g没有左孩子&＃xff0c;就指向其直接前驱b&＃xff0c;也没有右孩子&＃xff0c;就指向其直接后继e(如上图)

按照前序遍历&＃xff0c;节点g的前驱是e&＃xff0c;后继是c

后序遍历画线索二叉树例题&＃xff1a;

5.森林转二叉树