性质5如将一棵有n个结点的完全二叉树自 顶向下,同一层自左向右连续给结点编号1, 2,…,,则有以下关系: √若i=1,则i无双亲 若>1,则i的双亲为i/2」 √若2<=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 i ∥/对象:结点的有限集合,二叉树是有序树 public: Binary Tree o; /构造函数 Binary Tree(Bin TreeNode<t>*Ich, Bin Treenode<t>*rch, t item) /构造函数,以iem为根,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 /判二叉树空否? Bin Treenode<t>*Parent Bin TreeNode<t> *t); /结点t的双亲 BinTreeNode<t> *LeftChild(Bin Treenode<t>t) /结点t的左子女 BinTreeNode<t> *RightChild binTreeNode<t>*t; /)结点t的右子女 bool Insert(T item) ∥/在树中插入新元素 bool remove( T iten);∥在树中删除元素 bool Find( t& item) /￥断tem是否在树中 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
Bin treenode<t> *Getroot o 取根 void PreOrder(void(*visit)(BinTreeNode<t>*t)) /前序遍历,Visi是访问函数 void InOrdervoid(visit) BinTreenode<t>*t); /中序遍历,ViSi是访问函数 void PostOrder(void(visit)( BinTreeNode<t>*t) ∥l后序遍历,(*VisI)是访问函数 void LevelOrder(void(visit)( Bin Treenode<t>*)); ∥层次序遍历,ViSi是访问函数 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
三叉树的顺序表示 3 8 10 1314 12345678b023464 完全二叉树 一般二叉树 顺序表示 的顺序表示
完全二叉树 一般二叉树 的顺序表示 的顺序表示 二叉树的顺序表示 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