性质5如将一棵有个结点的完全二叉树自 顶向下，同一层自左向右连续给结点编号1， : 2,,n,则有以下关系 √若i=1,则i无双亲 √若i>1,则i的双亲为i/2」 √若2*i<=n,则i的左子女为2*i √若2*计1<=n,则i的右子女为2*计1 √若i为奇数，且i!=1, 则其左兄弟为i-1 若i为偶数，且i!=n, 则其右兄弟为计1 16
• 性质5 如将一棵有n个结点的完全二叉树自 顶向下，同一层自左向右连续给结点编号1, 2, …, n，则有以下关系： ✓ 若i = 1, 则 i 无双亲 ✓ 若i > 1, 则 i 的双亲为i／2 ✓ 若2*i <= n, 则 i 的左子女为 2* i ✓ 若2*i+1 <= n, 则 i 的右子女为2*i+1 ✓ 若 i 为奇数, 且i != 1, 则其左兄弟为i-1 ✓ 若 i 为偶数, 且i != n, 则其右兄弟为i+1 1 2 3 4 8 5 6 7 9 10 16
二叉树的抽象数据类型 template <class T> class Binary Tree f /对象：结点的有限集合，二叉树是有序树 public: BinaryTree O; /构造函数 BinaryTree (BinTreeNode<T>*lch, BinTreeNode<T>*rch,T item); /构造函数，以item为根，lch和rch为左、右子 /树构造一棵二叉树 int Height O; 川求树深度或高度 int Size O; 川求树中结点个数 17
二叉树的抽象数据类型 template <class T> class BinaryTree { //对象: 结点的有限集合, 二叉树是有序树 public: BinaryTree (); //构造函数 BinaryTree (BinTreeNode<T> *lch, BinTreeNode<T> *rch, T item); //构造函数, 以item为根, lch和rch为左、右子 //树构造一棵二叉树 int Height (); //求树深度或高度 int Size (); //求树中结点个数 17
bool IsEmpty O; /判二叉树空否？ BinTreeNode<T>*Parent (BinTreeNode<T>*t); /求结点t的双亲 BinTreeNode<T>*LeftChild (BinTreeNode<T>*t); 川求结点t的左子女 BinTreeNode<T>*RightChild (BinTreeNode<T>*t); /求结点t的右子女 bool Insert (T item); /川在树中插入新元素 bool Remove (T item); 川在树中删除元素 bool Find (T&item); /判断item是否在树中 bool GetData (T&item); ∥取得结点数据 18
bool IsEmpty (); //判二叉树空否？ BinTreeNode<T> *Parent (BinTreeNode<T> *t); //求结点 t 的双亲 BinTreeNode<T> *LeftChild (BinTreeNode<T> *t); //求结点 t 的左子女 BinTreeNode<T> *RightChild (BinTreeNode<T> *t); //求结点 t 的右子女 bool Insert (T item); //在树中插入新元素 bool Remove (T item); //在树中删除元素 bool Find (T& item); //判断item是否在树中 bool GetData (T& item); //取得结点数据 18
BinTreeNode<T>*GetRoot ( /取根 void PreOrder (void (*visit)(BinTreeNode<T>*t)); /前序遍历，VSit是访问函数 void InOrder (void (*visit)(BinTreeNode<T>*t)); /中序遍历，VSit是访问函数 void PostOrder (void (*visit)(BinTreeNode<T>*t)); /∥后序遍历，(*vSit)是访问函数 void LevelOrder (void (*visit)(BinTreeNode<T>*t)); /川层次序遍历，VSit是访问逯数 }; 19
BinTreeNode<T> *GetRoot (); //取根 void PreOrder (void (*visit) (BinTreeNode<T> *t)); //前序遍历, visit是访问函数 void InOrder (void (*visit) (BinTreeNode<T> *t)); //中序遍历, visit是访问函数 void PostOrder (void (*visit) (BinTreeNode<T> *t)); //后序遍历, (*visit)是访问函数 void LevelOrder (void (*visit)(BinTreeNode<T> *t)); //层次序遍历, visit是访问函数 }; 19
二叉树的顺序表示 1011 121314 12345678910 12346789 1214 完全二叉树 一般二叉树 的顺序表示 的顺序表示 20
完全二叉树 一般二叉树 的顺序表示 的顺序表示 二叉树的顺序表示 1 1 2 3 4 5 6 7 8 9 10 14 1 2 3 4 6 7 8 9 12 14 2 4 8 9 10 5 6 7 3 1 2 3 4 6 7 8 9 12 5 10 11 13 20