二叉树节点英文

二叉树 (binary tree) 是另一种树型结构，它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 )，并且，二叉树的子树有左右之分，其次序不能任意颠倒 . 二叉树是一种数据结构 : Binary_tree=(D,R) 其中： D是具有相同特性的数据元素的集合 ;若 D等于空 ,则 R等于空称为空的二叉树 ;若 D等于空则 R是 D上某个二元关系 H的集合，即 R={H}，且 (1) D 中存在唯一的称为根的元素 r，它的关系 H下无前驱 ; (2) 若 D-{r}不等于空，则 D-{r}={Dl,Dr}，且 Dl交 Dr等于空 ; (3) 若 Dl不等于空 ,则在 Dl中存在唯一的元素 xl,〈 r,xl〉属于 H，且存在 Dl上的关系 Hl属于 H； 若 Dr不等于空 ,则在 Dr中存在唯一的元素 xr,〈 r,xr〉 >属于 H, 且存 Dr上的关 系 Hr属于 H； H={r,xl,＜ r,xr＞ ,Hl, Hr}; (4) (Dl, Hl) 是一棵合本定义的二叉树，称为根 r的左子树 ,(Dr,Hr)是一棵符合定义的二叉树，称为根的右子树。 其中，图 6.2 是各种形态的二叉树 . (1) 为空二叉树 (2)只有一个根结点的二叉树 (3)右子树为空的二叉树 (4)左子树为空的二叉树 (5)完全二叉树 二叉树的基本操作： (1)INITIATE(BT ） 初始化操作。置 BT为空树。 (2)ROOT(BT)\ROOT(x) 求根函数。求二叉树 BT的根结点或求结点 x所在二叉树的根结点。 若 BT是空树或 x不在任何二叉树上，则函数值为 “空 ”。 (3)PARENT(BT,x) 求双亲函数。求二叉树 BT中结点 x的双亲结点。若结点 x是二叉树 BT 的根结点 或二叉树 BT中无 x结点，则函数值为 “空 ”。 (4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子结点函数。分别求二叉树 BT中结点 x的左孩 子和右孩子结点。 若结点 x为叶子结点或不在二叉树 BT中，则函数值为 “空 ”。 (5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函数。分别求二叉树 BT中结点 x的左兄弟和右兄弟结点。 若结点 x是根结点或不在 BT中或是其双亲的左 /右子树根 ,则函树值 为 “空 ”。 (6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点 x为根，二叉树 LBT和 RBT分别为左， 右子树的二叉树。 (7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子树操作。将以结点 x为根且右子树为空的二叉树 分别置为二叉树 BT中结点 y的左子树和右子树。若结点 y有左子树 /右子树，则插入后是结点 x的右子树。 (8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 删除子树操作。分别删除二叉树 BT中以结点 x为根的左子树或右子树。 若 x无左子树或右子树，则空操作。 (9)TRAVERSE(BT) 遍历操作。按某个次序依此访问二叉树中各个结点，并使每个结点只被访问一次。 (10)CLEAR(BT) 清除结构操作。将二叉树 BT置为空树。 5.2.2 二叉树的存储结构 一 、顺序存储结构 连续的存储单元存储二叉树的数据元素。例如图 6.4(b)的完全二叉树 , 可以向量 (一维数组 ) bt(1:6)作它的存储结构，将二叉树中编号为 i的结点的数据元素存放在分量 bt[i]中 ,如图 6.6(a) 所示。但这种顺序存储结构仅适合于完全二叉树 ,而一般二叉树也按这种形式来存储 ,这将造成存 贮浪费。如和图 6.4(c)的二叉树相应的存储结构图 6.6(b)所示，图中以 “0”表示不存在此结点 . 二、 链式存储结构 由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点至少包含三个域 :数据域和左右指针域 ,如图 (b)所示。有时 ,为了便于找 到结点的双亲 ,则还可在结点结构中增加一个指向其双亲受的指针域，如图 6.7(c)所示。 5.3 遍历二叉树 遍历二叉树 (traversing binary tree)的问题， 即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。 其中常见的有三种情况：分别称之为先 (根 )序遍历，中 (根 )序遍历和后 (根 )序遍历。 5.3.1 前序遍历 前序遍历运算：即先访问根结点，再前序遍历左子树，最后再前序遍历右子树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如： 按前序遍历此二叉树的结果为： Hello!How are you? proc preorder(bt:bitreprtr) if (bt<>null)[ print(bt^); preorder(bt^.lchild); preorder(bt^.rchild);] end; 5.3.2 中序遍历 中序遍历运算：即先中前序遍历左子树，然后再访问根结点，最后再中序遍历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如： 按中序遍历此二叉树的结果为： a*b-c proc inorder(bt:bitreprtr) if (bt<>null)[ inorder(bt^.lchild); print(bt^); niorder(bt^.rchild);] end; 5.3.3 后序遍历 后序遍历运算：即先后序遍历左子树，然后再后序遍历右子树，最后访问根结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如： 按后序遍历此二叉树的结果为： Welecome to use it! proc postorder(bt:bitreprtr) if (bt<>null)[ postorder(bt^.lchild); postorder(bt^.rchild);] print(bt^); end; 五、例： 1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。 2.用链表存储方式建立一棵如图三、4所示的二叉树，并对其进行先序遍历。 3.给出一组数据：R={10.18,3,8,12,2,7,3}，试编程序，先构造一棵二叉树，然后以中序遍历访问所得到的二叉树，并输出遍历结果。 4.给出八枚金币a,b,c,d,e,f,g,h，编程以称最少的次数，判定它们蹭是否有假币，如果有，请找出这枚假币，并判定这枚假币是重了还是轻了。 中山纪念中学三鑫双语学校信息学竞赛组编写 2004.7.15

满二叉树：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

节点：

就是一个图中的0、1、2~~14，这些就叫节点。

叶子节点：

就是没有子节点的节点，比如图中的7、8、9~~14这些，0、1、2、3这些就不是叶子节点。

拓展：二叉树相关术语

树的结点（node）：包含一个数据元素及若干指向子树的分支；

孩子结点（child node）：结点的子树的根称为该结点的孩子；

双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；

兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；

祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的深度：树中最大的结点层

结点的度：结点子树的个数

树的度： 树中最大的结点度。

叶子结点：也叫终端结点，是度为 0 的结点；

分枝结点：度不为0的结点；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；

满二叉树：如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。

如图:

树叶：没有子树的结点称作二叉树的树叶或终端结点。（上图中7—14为树叶）

分支结点：即非终端的结点

树叶和分支结点就是二叉树的结点。

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。国内教程定义：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

满二叉树（Full Binary Tree）是这样一颗二叉树，除最后一层无任何子结点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点，节点数达到最大值，且所有叶子结点必须在同一层上。满二叉树的性质:一颗满二叉树深度为h，最大层数为k，则：k=h；它的叶子数是：2^(h-1)第k层的结点数是：2^(k-1)总结点数是：2^k-1数据结构:指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：Data_Structure=(D,R)，其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。

特殊的树，树

首先理解概念：前序遍历：访问根结点的操作发生在遍历其左右子树之前。中序遍历：访问根结点的操作发生在遍历其左右子树之中(间)。后序遍历：访问根结点的操作发生在遍历其左右子树之后。来看你的题目：1.由后序遍历CGEBHFJIDA可知根为A2.在中序遍历CBGEAFHDIJ中找到A，可知（左）CBGE--A--FHDIJ（右）对左右支分别重复上述步骤，即在后序遍历中观察CBGE的相对位置可知B为根，则有C--B--GE在后序遍历中观察FHDIJ的相对位置可知D为根，则有FH--D--IJ……由此可得出树的结构，进而得出先序遍历为ABCEGDFHIJ