二叉树或为空树;或是由一个根结 点加上两裸分别称为左子树和右子树 的、互不交的二叉树组成。 右子树 根结点厂 A E D 左子时
二叉树或为空树；或是由一个根结 点加上两棵分别称为左子树和右子树 的、互不交的二叉树组成。 A B C D E F G H K 根结点 左子树 右子树 E F
如持 只含視点 树均不 为如 右子树为空树左子村为空 N N N R R
二叉树的五种基本形态： N 空树 只含根结点 N N N L R R 右子树为空树 L 左子树为空树 左右子 树均不 为空树
二的意点 二叉树每个结点的孩子都有左右之分,每个 结点都有左右两个子树。 Q 三个节点的二叉树(五裸) ①每个结点最多只有两裸子树不存在度大于2的结点) ②左子树和右子树次序不能颠倒有序树)
二叉树的注意点 • 二叉树每个结点的孩子都有左右之分，每个 结点都有左右两个子树。 A B C C B A C B A C B A 三个节点的二叉树（五棵） ①每个结点最多只有两棵子树(不存在度大于2的结点)； ②左子树和右子树次序不能颠倒(有序树)
3、事宗 层为结深结双结孩叶树结支包结 第点度点亲点子子数点 的数 点 的 层层该墨孩三据显 次 结 项 5 它 的 结 的 为 表 0⊙@@@ 为 算层点的给给娇 子的子0 第点天结树的 起次的根点 很 即上层的那个结点直接前物 即根结点Q没有前驱 层 称为该 有的子 其子树的分 的元素 双亲 孩子 即下层结点的子树的根接后继 兄弟—同双亲下的同层结点(孩子之间互称兄弟 堂兄弟一即双亲位于同一层的结点(但并同双亲) 祖先 即从根到该结点所经分支的所有结点 子孙 即该结点下层子御中的任结点
2、基本术语 1. 结 点(node)—— 表 示 树 中 的 元 素 ， 包 括 数 据 项 及 若 干 指 向 其 子 树 的 分 支 2. 结 点 的 度(degree)—— 结 点 拥 有 的 子 树 数 3. 叶 子(leaf)—— 度 为 0 的 结 点 4. 孩 子(child)—— 结 点 子 树 的 根 称 为 该 结 点 的 孩 子 5. 双 亲(parents)—— 孩 子 结 点 的 上 层 结 点 叫 该 结 点 的 双 亲 6. 深 度—— 树 中 结 点 的 最 大 层 次 数 7. 结 点 的 层 次—— 从 根 结 点 算 起 ， 根 为 第 一 层 ， 它 的 孩 子 为 第 二 层 ， …… 1 2 3 11 4 5 8 9 12 6 7 10 ——即根结点(没有前驱) ——即上层的那个结点(直接前驱) ——即下层结点的子树的根(直接后继) ——同一双亲下的同层结点（孩子之间互称兄弟） ——即双亲位于同一层的结点（但并非同一双亲） ——即从根到该结点所经分支的所有结点 ——即该结点下层子树中的任一结点 根 双亲 孩子 兄弟 堂兄弟 祖先 子孙
结点A的度:3 结点B的度:2 结点M的度:0 B 结点A的孩子:B,C,D 结点B的孩子:E。F QO○ 树的度:3 树的深度:4 叶子:K,L,F,G,M,I,J 结点双亲:D 结点B,C,D为兄弟 结点L的双亲:E 结点K,L为兄弟 结点A的层次:1 结点F,G为堂兄弟 结点M的层次:4 结点A是结点F,G的祖先
A B C D E F G H I J K L M 结点A的度：3 结点B的度：2 结点M的度：0 叶子：K，L，F，G，M，I，J 结点A的孩子：B，C，D 结点B的孩子：E，F 结点I的双亲：D 结点L的双亲：E 结点B，C，D为兄弟 结点K，L为兄弟 树的度：3 结点A的层次：1 结点M的层次：4 树的深度：4 结点F，G为堂兄弟 结点A是结点F，G的祖先