Struct TNodet 二叉树的存储表示T ype Data TNode *leftchild 二叉树的链表存储表示 TNode *rightchild; TNode"parent 左孩子指针 右孩子指针 左孩子指针 右孩子指针 leftchild data rightchild leftchild data parent rightchild parent data data leftchild rightchild leftchild 二叉链表 三叉链 tvghtChild 找子女时间o(1) 找子女时间o(1), 找父亲要从根开始,时间o(og2l) 找父亲时间o(1) 16
二叉树的存储表示 ◼ 二叉树的链表存储表示 16 leftChild data rightChild data 左孩子指针 右孩子指针 leftChild rightChild leftChild data rightChild data 左孩子指针 右孩子指针 leftChild rightChild parent parent 二叉链表 三叉链表 找子女时间O(1)， 找父亲要从根开始，时间O(log2 i) 找子女时间O(1)， 找父亲时间O(1) Struct TNode{ Type Data; TNode *leftChild; TNode *rightChild; TNode *parent; };
二叉树的存储表示 n二叉树的链表存储表示 root root root A □△△ ( AN ANA G 区A 二叉树 二叉链表 三叉链表17
二叉树的存储表示 ◼ 二叉树的链表存储表示 17 A B C D G E F root A ʌ A ʌ ʌ root root B ʌ C ʌ D ʌ E ʌ F ʌ ʌ G ʌ A ʌ A ʌ A ʌ A ʌ A ʌ ʌ A ʌ 二叉树 二叉链表 三叉链表
二叉树的存储表示 n二叉树的链表存储表示 root data parent left Child rightChild A 0 A B 3 ( 23456 5 E316 F ee G 静态链表结构 G 二叉树 18
二叉树的存储表示 ◼ 二叉树的链表存储表示 18 A B C D G E F root 二叉树 data parent leftChild rightChild 0 A -1 1 -1 1 B 0 2 3 2 C 1 -1 -1 3 D 1 4 5 4 E 3 -1 6 5 F 3 -1 -1 6 G 4 -1 -1 静态链表结构
二叉树的遍历及其应用 二叉树的遍历就是按某种次序访问树中的结点 次且仅一次 a访问当前结点记为V n访问结点的左子树记为L 访问结点的右子树记为R n遍历次序一般有 前序遍历LR) 中序遍历LVR) 后序遍历(LRV) 19
二叉树的遍历及其应用 ◼ 二叉树的遍历就是按某种次序访问树中的结点 一次且仅一次 访问当前结点记为V 访问结点的左子树记为L 访问结点的右子树记为R ◼ 遍历次序一般有 前序遍历 (VLR) 中序遍历 (LVR) 后序遍历 (LRV) 19