数据结构与算法设计PPT (23).pdf

第6章树6.3 二叉树的存储结构及实现二叉树的抽象数据类型template classBinaryTreepublic:BinaryTree();BinaryTree(BinTreeNode*lch,BinTreeNode*rch,Typeitem);intIsEmpty();BinTreeNode*Parent();BinTreeNode*LeftChild();BinTreeNode*RightChild();intInsert(const Type&item);intFind(const Type&item)const;TypeGetData()const;const BinTreeNode*GetRoot()const;二叉树的存储结构 链式存储结构 每个结点=数据单元+两个孩子指针 通过指向根节点的指针访问所有节点 静态链式存储结构 每个结点=数据单元+两个孩子存储的下标 根结点在下标为0的为位置 顺序存储结构 A 0=根节点 A 1，A 2=A 0的孩子结点 A 3，A 4，A 5，A 6=A 1和A 2的孩子结点二叉树的链式存储结构template class BiTNode TElemType data;BiTNode *leftchild,*rightchild;/指向左孩子右孩子的指针;Typedef BiTNode*BiTree;DataParentLeftchildrightchild D DA AB B C C E E F F A AF FE EA AB BC CD DD D A A B B F F 一个二叉链表种有n+1 空指针.B BC CD D二叉树的三叉链表template class BiTNode TElemType data;BiTNode *leftchild,*rightchild,*parent;/pointers to left and right child;ABDFECADEBCFA B C D E F#define MAX_TREE_SIZE 100typedef TElemType SqBiTreeMAX_TREE_SIZESqBiTree bt;01 2 3 4 5 6 7 mA012345BCDEF二叉树的顺序存储结构非完全二叉树的顺序存储0 1 2.3.4 5.6 7 8 9 10 mABC D EF GAEGADEG0957CBDFFCB二叉链表的静态结构二叉树的链式存储结构的实现 二叉树结点 二叉树的二叉链表 二叉树的操作的实现template class BinaryTree;template Class BinTreeNode friend class BinaryTree;private:BinTreeNode*leftChild,*rightChild;Type data;public:BinTreeNode():leftChild(NULL),rightChild(NULL)BinTreeNode(Type item,BinTreeNode*left=NULL,BinTreeNode*right=NULL):data(item),leftChild(left),rightChild(right)二叉树的结点的定义Type GetData()const return data;BinTreeNode*GetLeft()const return leftChild;BinTreeNode*GetRight()const return rightChild;void SetData(const Type&item)data=item;void SetLeft(BinTreeNode *L)leftChild=L;void SetRight(BinTreeNode *R)rightChild=R;二叉树的结点的定义template class BinaryTree public:BinaryTree():root(NULL)BinaryTree(Type value):RefValue(value),root(NULL)virtual BinaryTree()destroy(root);virtual int IsEmpty()return root=NULL?1:0;二叉树类的定义与实现Data StructureSoftware College Northeastern Universityvirtual BinTreeNode *Parent(BinTreeNode *current)return root=NULL|root=current？NULL:Parent(root,current);virtual BinTreeNode *LeftChild(BinTreeNode *current)return current!=NULL?currentleftChild:NULL;virtual BinTreeNode *RightChild(BinTreeNode *current)return current!=NULL?currentrightChild:NULL;二叉树类的定义与实现virtual int Insert(const Type&item);virtual int Find(const Type&item)const;const BinTreeNode *GetRoot()const return root;friend istream&operator (istream&in,BinaryTree&Tree)friend ostream&operator (ostream&out,BinaryTree&Tree)private:BinTreeNode *root;Type RefValue;二叉树类的定义与实现BinTreeNode *Parent(BinTreeNode *start,BinTreeNode *current);int Insert(BinTreeNode*&current,const Type&item);void Traverse(BinTreeNode*current,ostream&out)constint Find(BinTreeNode*current,const Type&item)constvoid destroy(BinTreeNode*current);二叉树类的定义与实现分治法 在军事上，“分而治之”是一种策略 在计算机科学中，“分而治之”是一种将问题分解为一个或多个子问题的编程技术“分而治之”通常通过递归来实现分治法程序结构 问题分解 将问题分解为多个子问题 解决 对子问题进行求解（通过递归调用求解）解的合并 使用子问题的解进行计算得到问题的解 由于二叉树的定义是递归的，所以对它的处理可以采用递归程序设计 一个二叉树的递归定义 为空 不为空，可以分解成一个根结点根的作孩子为根的左子树根的右孩子为根的右子树 处理过程可采用分治法假设一个变量current指向二叉树的根结点(1)current=NULL 递归终结条件的处理(2)Current!=NULL处理根递归调用处理左孩子为根的左子树递归调用处理右孩子为根的右子树二叉树操作实现template void BinaryTree:destroy(BinTreeNode*current)if(current!=NULL)destroy(currentleftChild);destroy(currentrightChild);delete current;二叉树类的析构函数的实现template BinTreeNode *BinaryTree:Parent(BinTreeNode*start,BinTreeNode *current)if(start=NULL)return NULL;if(startleftChild=current|startrightChild=current)return start;BinTreeNode *p;if(p=Parent(startleftChild,current)!=NULL)return p;else return Parent(startrightChild,current);二叉树类的求双亲函数实现template voidBinaryTree:Traverse(BinTreeNode *current,ostream&out)const if(current!=NULL)out currentdata ;Traverse(currentleftChild,out);Traverse(currentrightChild,out);二叉树类输出的实现template istream&operator(istream&in,BinaryTree&Tree)Type item;cout “构造二叉树:n;cout “输入数据(用 Tree.RefValue item;while(item!=Tree.RefValue)Tree.Insert(item);cout “输入数据(用 Tree.RefValue item;return in;二叉树类的输入实现template ostream&operator(ostream&out,BinaryTree&Tree)out “二叉树的前序遍历.n;Tree.Traverse(Tree.root,out);out endl;return out;二叉树类的遍历实现