二叉树的主要性质 证明:这里证明(2),(1)和(3)即可由结论(2)推得。对于i=0,由完全二 叉树的定义,其左孩子的编号是1,如果1>n-1,即不存在编号为1的 结点,此时结点设没有左孩子。其右孩子的编号只能是2,如果2>n-1, 此时结点设没有右孩子。 对于0分两种情况讨论 (1)设第层的第一个结点编号为(此时有=21),则其左孩子必为第j+ 1层的第一个结点,其编号为2-1=2i+1,如果2i+1>n-1,那么 设没有左孩子;其右孩子必为第j+1层第二个结点,其编号为2+2。 (2)假设第层的某个结点编号为,若它有左孩子,那么它的左孩子必然 是第j+1层中的第2[i-(2-1)个,那么其左孩孑的编号就是(21-1 )+2[i-(2-1)=2i+1;如果结点右孩子,那么其右孩孑的编号 必是2i+2。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 二叉树的主要性质 证明：这里证明(2)，(1) 和(3)即可由结论(2)推得。对于i = 0，由完全二 叉树的定义，其左孩子的编号是1，如果1>n-1，即不存在编号为1的 结点，此时结点i没有左孩子。其右孩子的编号只能是2，如果2>n-1， 此时结点i没有右孩子。 对于i>0分两种情况讨论： (1)设第j层的第一个结点编号为i(此时有i = 2j -1)，则其左孩子必为第j + 1层的第一个结点，其编号为2 j+1 - 1 = 2i + 1，如果2i + 1 > n - 1，那么 i没有左孩子；其右孩子必为第j + 1层第二个结点，其编号为2i + 2。 (2)假设第j层的某个结点编号为i，若它有左孩子，那么它的左孩子必然 是第j + 1层中的第2[i - (2j - 1)]个，那么其左孩子的编号就是（2 j+1 – 1 ） + 2[i - (2j - 1)] = 2i + 1；如果结点i有右孩子，那么其右孩子的编号 必是2i + 2
52二叉树的抽象数据类型 521抽象数据类型 522深度优先周游二叉树 523广度优先周游二叉树 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5.2 二叉树的抽象数据类型 ◼ 5.2.1 抽象数据类型 ◼ 5.2.2 深度优先周游二叉树 ◼ 5.2.3 广度优先周游二叉树
521抽象数据类型 口一般情况下需要二叉树的各个结点存储所需 要的信息,对二叉树的操作和运算也主要集 中在访问二叉树的结点信息上 口例如访问某个结点的左子结点、右子结点、父结 点,或者访问结点存储的数据。 口从二叉树的应用角度来看,有时还需要遍历 二叉树的每个结点。 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5.2.1 抽象数据类型 一般情况下需要二叉树的各个结点存储所需 要的信息，对二叉树的操作和运算也主要集 中在访问二叉树的结点信息上。 ❑ 例如访问某个结点的左子结点、右子结点、父结 点，或者访问结点存储的数据。 从二叉树的应用角度来看，有时还需要遍历 二叉树的每个结点
521抽象数据类型 在二叉树的抽象数据类型中,定义了二叉树 基本操作的集合,在具体应用中可以以此为 基础进行扩充 为了强调抽象数据类型与存储无关,在此并 没有具体规定该抽象数据类型的存储方式 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5.2.1 抽象数据类型 ◼ 在二叉树的抽象数据类型中，定义了二叉树 基本操作的集合，在具体应用中可以以此为 基础进行扩充 ◼ 为了强调抽象数据类型与存储无关，在此并 没有具体规定该抽象数据类型的存储方式
521抽象数据类型 代码5.1】二叉树结点的抽象数据类型(ADT) template <class T class Binary lreeNode friend class binary Tree<T ∥/声明二叉树类为结点类的 友元类,以便访问私有数据成员 private T info ∥/二叉树结点数据域 public Binary TreeNodeo ∥/缺省构造函数 Binary TreeNode(const T& ele) ∥/给定数据的构造函数 Binary TreeNode(const T& ele, Binary TreeNode<t>*l Binary TreeNode<T>*r);∥子树构造结点 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 5.2.1 抽象数据类型 【代码5.1】 二叉树结点的抽象数据类型(ADT) template <class T> class BinaryTreeNode { friend class BinaryTree<T>; // 声明二叉树类为结点类的 友元类，以便访问私有数据成员 private: T info; // 二叉树结点数据域 public: BinaryTreeNode(); // 缺省构造函数 BinaryTreeNode(const T& ele); // 给定数据的构造函数 BinaryTreeNode(const T& ele,BinaryTreeNode<T> *l, BinaryTreeNode<T> *r); // 子树构造结点