二叉树的周游.ppt
《二叉树的周游.ppt》由会员分享,可在线阅读,更多相关《二叉树的周游.ppt(43页珍藏版)》请在三一文库上搜索。
1、5-2 二叉树,5.1 二叉树的概念 5.2 二叉树的周游 5.3 二叉树的存储结构 5.4 二叉搜索树 5.5 堆与优先队列 5.6 Huffman树及其应用 5.7 二叉树知识点总结,主要内容,5.2 二叉树的周游,5.2.1 抽象数据类型 5.2.2 深度优先周游二叉树 5.2.3 广度优先周游二叉树,5.2.1 抽象数据类型,一般情况下需要二叉树的各个结点存储必要的信息,对二叉树的操作和运算也主要集中在访问二叉树的结点信息上。 例如访问某个结点的左子结点、右子结点、父结点,或者访问结点存储的数据。 从二叉树的应用角度来看,有时还需要遍历二叉树的每个结点。,5.2.1 抽象数据类型,在二
2、叉树的抽象数据类型中,定义了二叉树基本操作的集合,在具体应用中可以以此为基础进行扩充 为了强调抽象数据类型与存储无关,在此并没有具体规定该抽象数据类型的存储方式,5.2.1 抽象数据类型,【代码5.1】 二叉树结点的抽象数据类型(ADT) template class BinaryTreeNode friend class BinaryTree / 声明二叉树类为结点类的友元类,以便访问私有数据成员 private: T info; / 二叉树结点数据域 public: BinaryTreeNode(); / 缺省构造函数 BinaryTreeNode(const T / 子树构造结点,5.2
3、.1 抽象数据类型,T value() const; / 返回当前结点的数据 BinaryTreeNode* leftchild() const; / 返回当前结点左子树 BinaryTreeNode* rightchild() const; / 返回当前结点右子树 void setLeftchild(BinaryTreeNode* l) / 设置当前结点的左子树 void setRightchild(BinaryTreeNode* r) ; / 设置当前结点的右子树 void setValue(const T,5.2.1 抽象数据类型,【代码5.2】 二叉树的抽象数据类型 template
4、class BinaryTree private: BinaryTreeNode* root; / 二叉树根结点 public: BinaryTree() root = NULL; / 构造函数 BinaryTree() DeleteBinaryTree(root); / 析构函数 bool isEmpty() const; / 判定二叉树是否为空树 BinaryTreeNode* Root()return root; / 返回二叉树根结点,5.2.1 抽象数据类型,BinaryTreeNode* Parent(BinaryTreeNode *current); / 返回当前结点的父结点 Bi
5、naryTreeNode* LeftSibling(BinaryTreeNode *current); / 返回当前结点的左兄弟 BinaryTreeNode* RightSibling(BinaryTreeNode *current); / 返回当前结点的右兄弟 void CreateTree(const T / 删除二叉树或其子树 ;,遍历(周游)二叉树,遍历是树结构的一种常用的、重要的运算,是树的其它运算的基础。 遍历 按一定的规律,走遍二叉树的每个结点,使每个结点被访问一次,且只被访问一次。,遍历的过程就是把非线性结构的二叉树中的结点排成一个线性序列的过程。,遍历方式 深度优先遍历 按
6、根、左子树、右子树三个部分进行访问 广度优先遍历(逐层遍历) 从根节点开始,向下逐层访问每个节点,在每一层次上,从左到右访问每个节点。,5.2.2 深度优先周游二叉树,设t表示当前结点,L表示左子树,R表示右子树,则对这三个部分进行访问的组合共有6种, tLR tRL LtR LRt RtL RLt 若限定先左后右,则只有tLR,LtR,LRt三种,分别称为先序遍历,中序遍历,后序遍历。,基于二叉树的递归定义,这三种深度优先周游的递归定义 (1) 前序法(tLR次序,preorder traversal)。其递归定义是 访问根结点; 按前序周游左子树; 按前序周游右子树。 (2) 中序法(Lt
7、R次序,inorder traversal)。其递归定义是 按中序周游左子树; 访问根结点; 按中序周游右子树。 (3) 后序法(LRt次序,postorder traversal)。其递归定义是 按后序周游左子树; 按后序周游右子树; 访问根结点。,5.2.2 深度优先周游二叉树,5.2.2 深度优先周游二叉树,深度周游如下二叉树 前序序列是:A B D E G C F H I 中序序列是:D B G E A C H F I 后序序列是:D G E B H I F C A,图5.5 二叉树示例,5.2.2 深度优先周游二叉树,二叉树的周游算法与表达式的“前缀”和“后缀”表示法之间有着密切的联
8、系。例如图5.6是表达式A+B(C+D)的二叉树表示。按照前序方式周游,运算符出现在前面,参与运算的对象紧跟在其后,这样就形成了前缀表达式(波兰式): + A B + C D 按照中序方式周游,得到的结果是去掉括号的中缀表达式: A + B C + D 下面是后序方式周游的结果,得到的是后缀表达式(逆波兰式): A B C D + +,图5.6 表达式树,若二叉树为空,则返回;否则,(1) 访问根结点;,(2) 先序遍历左子树;,(3) 先序遍历右子树;,A B C,先序遍历,begin,end,先序遍历顺序:,A,B,D,F,G,C,E,H,先序遍历演示,【算法5.3】 深度优先周游二叉树或
9、其子树 template void BinaryTree:PreOrder (BinaryTreeNode *root) / 前序周游二叉树或其子树 if (root != NULL) Visit(root-value(); / 访问当前结点 PreOrder(root-leftchild(); / 前序周游左子树 PreOrder(root-rightchild(); / 前序周游右子树 ,先序遍历递归算法,递归算法转化为非递归算法,递归算法优点 形式简洁,可读性好,正确性容易得到证明,可以给程序的编制和调试带来很大的方便。 递归算法缺点 递归调用比非递归调用消耗的时间与存储空间多,运行的效
10、率较低。,所有的递归算法都可转化成相应的非递归算法。 将递归算法改成相应的非递归算法需要一个栈来记录调用返回的路径。通过分析递归调用的执行过程,并观察栈的变化就可得到相应的非递归算法。,先序遍历的非递归实现,先序的非递归程序实现: 1、根结点进栈 2、结点出栈,被访问 3、结点的右、左儿子(非空)进栈 4、反复执行 2、3 ,至栈空为止。,先序遍历的非递归实现,B,C,D,E,L,A,先序:A、L、B、E、C、D,e.g:,A出栈访问,L出栈访问,B出栈访问,E出栈访问,C出栈访问,D出栈访问后,栈空结束,A进栈,C、L 进栈,E、B 进栈,D进栈,给出先序遍历的非递归实现的代码,先序遍历的非
11、递归实现,template void BinaryTree:PreOrderWithoutRecursion(BinaryTreeNode *root) using std:stack; / 使用STL中的栈 stack* aStack; BinaryTreeNode *pointer = root; aStack.push(NULL); / 栈底监视哨 while (pointer) / 或者!aStack.empty() Visit(pointer-value(); / 访问当前结点 if (pointer-rightchild() != NULL) / 非空右孩子入栈 aStack.pu
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 周游
链接地址:https://www.31doc.com/p-2553050.html