45二叉树的实现 用指针实现二叉树 451用指针实现二叉树 ■非线性结构最自然的方法是链接的方法 452空间开销分析 指针left和 right,分别指向结点的左子女 453用数组实现完全二叉树 和右子女 454穿线二叉树 空指针 张写 用指针实现二叉树 用指针实现二叉树 其他的链接表示法 z区 例如“三叉链表 增加一个指向父母的指针 parent 具有“向上”访问的能力 h I 叔有。轨印当究 张鲁写 前有,聊脂究 用指针实现二叉树 用指针实现二叉树 扩展二叉树结点抽象数据类型 BinaryTreeNode,.为每 个元素结点添加left和rght左右子结点结构 //以后序周游的方式删除二叉树或其子树 if(root /二叉树结点指向左子树的指针 DeleteBinaryTree(root->left)}//递归删除左子树 Delete Binary Tree(root-> right);//递归删除右子树 /二叉树结点指向左子树的指针 Delete root/删除根结点 d inaryTreeNode <Tss right, 真大_血单 大息9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 4.5 二叉树的实现 „ 4.5.1 用指针实现二叉树 „ 4.5.2 空间开销分析 „ 4.5.3 用数组实现完全二叉树 „ 4.5.4 穿线二叉树 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 用指针实现二叉树 „ 非线性结构最自然的方法是链接的方法 „ 指针left和right，分别指向结点的左子女 和右子女 „ 空指针 left info right 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 用指针实现二叉树 A B C E F D G H I A B ∧ C ∧ D ∧ ∧ E F ∧ G ∧ ∧ H ∧ ∧ I ∧ t 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 用指针实现二叉树 „ 其他的链接表示法 „ 例如“三叉链表” „ 增加一个指向父母的指针parent „ 具有“向上”访问的能力 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 用指针实现二叉树 „ 扩展二叉树结点抽象数据类型BinaryTreeNode,为每 个元素结点添加left和right左右子结点结构 private: //二叉树结点指向左子树的指针 BinaryTreeNode<T>* left; //二叉树结点指向左子树的指针 BinaryTreeNode<T>* right; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 用指针实现二叉树 template<class T>void BinaryTree<T>:: DeleteBinaryTree(BinaryTreeNode<T>* root) {//以后序周游的方式删除二叉树或其子树 if(root){ DeleteBinaryTree(root->left);//递归删除左子树 DeleteBinaryTree(root->right);//递归删除右子树 Delete root;//删除根结点 } };