故（2）和（3）得证,由（2）和（3）我们可以很容易证明（1） 。
当i=1时 ，显然该结点为根结点 ， 无双亲结点 。
当i1时 ， 设序号为i的结点的双亲结点的序号为m ， 如果序号为i的结点是其双亲结点的左孩子 ， 根据（2）有i=2m ， 即m=i/2;
如果序号为i的结点是其双亲结点的右孩子 ， 根据（3）有i=2m+1 ，即m=（i-1）/2=i/2-1/2 ， 综合这两种情况 ， 可以得到 ， 当i1时 ，其双亲 。

15、结点的序号等于i/2 。
证毕,二叉树的存储结构,二叉树的结构是非线性的 ，每一结点最多可有两个后继 。
二叉树的存储结构有两种： 顺序存储结构和链式存储结构,1. 顺序存储结构,图6.4 二叉树与顺序存储结构,图6.5 单支二叉树与其顺序存储结构,2. 链式存储结构 对于任意的二叉树来说 ， 每个结点只有两个孩子 ， 一个双亲结点 。
我们可以设计每个结点至少包括三个域：数据域、 左孩子域和右孩子,其中 ， LChild域指向该结点的左孩子 ， Data域记录该结点的信息 ， RChild域指向该结点的右孩子,用C语言可以这样声明二叉树的二叉链表结点的结构,typedef struct Node DataType dat 。

16、a;
struct Node *LChild;
struct Node *RChild;
BiTNode, *BiTree,有时 ， 为了便于找到父结点 ， 可以增加一个Parent域 ，Parent域指向该结点的父结点 。
该结点结构如下,图6.6 二叉树和二叉链表,若一个二叉树含有n个结点 ， 则它的二叉链表中必含有2n个指针域 ，其中必有n1个空的链域 。
此结论证明如下： 证明：分支数目B=n-1 ， 即非空的链域有n-1个 ， 故空链域有2n-(n-1)=n+1个 。
不同的存储结构实现二叉树的操作也不同 。
如要找某个结点的父结点 ， 在三叉链表中很容易实现；在二叉链表中则需从根指针出发一一查找 。
可见 ， 在具体应用中 ，。

17、需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构,二叉树的遍历,图6.7 二叉树结点的基本结构,我们用L、D、R分别表示遍历左子树、访问根结点、 遍历右子树 ，那么对二叉树的遍历顺序就可以有六种方式： (1) 访问根 ， 遍历左子树 ， 遍历右子树（记做DLR） 。
(2) 访问根 ， 遍历右子树 ， 遍历左子树（记做DRL） 。
(3) 遍历左子树 ， 访问根 ， 遍历右子树（记做LDR） 。
(4) 遍历左子树 ， 遍历右子树 ， 访问根（记做LRD） 。
(5) 遍历右子树 ， 访问根 ， 遍历左子树（记做RDL） 。
(6) 遍历右子树 ， 遍历左子树 ， 访问根（记做RLD,注意：先序、中序、后序遍历是递归定义的 ，即在其子树中亦 。

18、按上述规律进行遍历 。
下面就分别介绍三种遍历方法的递归定义 。
先序遍历（DLR）操作过程： 若二叉树为空 ， 则空操作 ， 否则依次执行如下3个操作： (1) 访问根结点； (2) 按先序遍历左子树； (3) 按先序遍历右子树,中序遍历（LDR）操作过程： 若二叉树为空 ， 则空操作 ， 否则依次执行如下3个操作： (1) 按中序遍历左子树； (2) 访问根结点； (3) 按中序遍历右子树 。
后序遍历（LRD）操作过程： 若二叉树为空 ， 则空操作 ， 否则依次执行如下3个操作： (1) 按后序遍历左子树； (2) 按后序遍历右子树； (3) 访问根结点,先序遍历： A、 B、 D、 F、 G、 C、 E、 H。
。

【概念|树的概念和定义】19、中序遍历： B、 F、 D、 G、 A、 C、 E、 H。
后序遍历： F、 G、 D、 B、 H、 E、 C、 A,图6.8 二叉树,中序遍历二叉树的递归过程,最早提出遍历问题是对存储在计算机中的表达式求值 。
例如：（a+b*c）-d/e 。
该表达式用二叉树表示如图6.9所示 。
当我们对此二叉树进行先序、中序、后序遍历时 ， 便可获得表达式的前缀、 中缀、 后缀书写形式： 前缀： -+a*bc/de 中缀： a+b*c-d/e 后缀： abc*+de/- 其中中缀形式是算术表达式的通常形式 ， 只是没有括号 。
前缀表达式称为波兰表达式 。
算术表达式的后缀表达式被称作逆波兰表达式 。
在计算机内 ，使用后缀表达式易于求值,图6.9 算术式的二叉树表示 。

来源：(未知)

【学习资料】网址：/a/2021/0323/0021754656.html

标题：概念|树的概念和定义( 三 )