《数据结构精品课程ppt11.ppt》由会员分享，可在线阅读，更多相关《数据结构精品课程ppt11.ppt（40页珍藏版）》请在金锄头文库上搜索。
1、1,1. Property of Binary Tree,性质1：在二叉树的第i层上至多有 2i 个节点。 性质2：高度为k的二叉树的最大结点数为： 性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为能，则n0n21。 （证明： n=n0+n1+n2 n=n1+2n2+1 n0=n2+1） 性质4：具有n个结点的完全二叉树的高度为：,2,Property of Binary Tree,性质5：如果对一棵有n个结点的完全二叉树（其深度为）的结点按层次编号，则对任一结点i(1in) ，有 如果i=0，则结点i是二叉树的根，无双亲；若i0，其双亲parent（i）是结点 ； 如果2i
2、1n，则结点i无左孩子（结点i为叶子结点），否则左孩子为2i1； 如果2i2n，则结点i无右孩子（结点i为叶子结点），否则右孩子为2i2,3,2. Using Tree Scan Algorithm,1.Computing the tree leaf: Template Void countleaf(tnode *t, int ,4,Using Tree Scan Algorithm,2.Computing the depth of a tree: Template Int depth(tnode *t) if(t=NULL)depthval=-1; else depthleft=depth(
3、t-left) ; depthright=depth(t-right); depthval=1+ (depthleftdepthright?depthleft:depthright); return depthval; ,5,Using Tree Scan Algorithm,3. Computing the onechild branch Template void CountOneChild(tnode* t,int ,6,Using Tree Scan Algorithm,4. Computing the onechild node Template int CountOneChild(
4、tnode* t) int count=0; if(t!=NULL) if(t-left=NULL ,7,Using Tree Scan Algorithm,5. Creating Binary Tree Template Tnode* CreatingBTree() tnode* t; char ch; cinch; if(ch= )t=NULL; else t=new tnode(ch) ; t-left=CreatingBTree(); t-right=CreatingBTree(); return t; ,8,Using Tree Scan Algorithm,6.Printing B
5、inary Tree/转向打印二叉树(逆时针转90度打印) template void print(tnode * node_ptr, int depth) if (node_ptr != NULL) print(node_ptr-right, depth+1); cout nodeValue left, depth+1); ,9,Binary-Tree Scan Algorithm-non recursive,深度优先搜索：Depth-first search （使用栈） 广度优先搜索：Breadth-first search（使用队列） template / 中序遍历 void Inord
6、er(tnode *t) stack * s; tnode *p; s.push(t); while(!s.empty() while(s.top()p=s.top(); s.push(p-left); s.pop(); if(!s.empty() p=s.top(); coutnodeValue; s.pop(); s.push(p-right); ,10,Binary-Tree Scan Algorithm-non recursive,template / 前序遍历 void Preorder(tnode *t) stack * s; tnode *p; s.push(t); while(
7、!s.empty() while(s.top() p=s.top(); coutnodeValue; s.push(p-left); s.pop(); if(!s.empty() p=s.top(); /已访问过 s.pop(); s.push(p-right); ,11,Binary-Tree Scan Algorithm-non recursive,template / 后序遍历 void Preorder(tnode *t) stack * s; tnode *p,*pre=NULL; s.push(t); while(!s.empty() while(s.top()p=s.top();
8、 s.push(p-left); s.pop(); if(!s.empty() p=s.top(); if(p-right=NULL|p-right=pre)/如果p没有右孩子或者其右孩子刚刚被访问过; coutnodeValue; s.pop(); pre=p; s.push(NULL); else s.push(p-right); ,12,3. 线索二叉树,线索二叉树（将非线性结构表示为线性结构）,13,4. 二叉查找树（二叉搜索树）,template class BST public: BST(); bool empty() const; bool search(const DataTy
9、pe ,14,二叉查找树（二叉搜索树）,typedef BinNode * BinNodePointer; void search2(const DataType ,15,二叉查找树 实现,template inline BST:BST(): myRoot(0) template inline bool BST:empty() const return myRoot = 0; ,16,二叉查找树 实现,template /public bool BST:search(const DataType ,17,二叉查找树 实现,template /private void BST:search2(c
10、onst DataType ,18,二叉查找树 实现,template /public inline void BST:insert(const DataType ,19,二叉查找树 实现,template /public void BST:remove(const DataType /到达替代节点 ,20,二叉查找树 实现,/处理替代节点 及只有一个子节点或没有子节点的情况 BST:BinNodePointer subtree = x-left; if (subtree = 0) subtree = x-right; if (parent = 0) myRoot = subtree; els
11、e if (parent-left = x) parent-left = subtree; else parent-right = subtree; delete x; ,21,二叉查找树 实现,template /public inline void BST:inorder(ostream ,22,二叉查找树 实现,template /private void BST:inorderAux(ostream ,23,5. The Stree Iterator,class iterator friend class stree; friend class const_iterator; publ
12、ic: iterator () bool operator= (const iterator,24,The Stree Iterator (中序遍历),iterator,25,. Traversal with iterator,复习List遍历方法： List traversal Exmaple: Int arr=1,2,3,4,5; Int arrsize=sizeof(arr)/sizeof(int); List intList(arr,arr+arrsize); List:iterator iter=intList.begin(); while(iter!=intList.end() c
13、out*iter“ ”; iter+; ,26,BST iterator,template void removeDuplicates(vector ,27,7. AVL Tree,AVL(平衡树)是由Adelson-Velskii and Landis（前苏联科学家） 于1962年首先提出的，所以又称AVL树。 定义：若一棵二叉树中每个结点的左右子树的高度至多相差1，则称此树是AVL树。 平衡因子（balance factor）=每个结点的左子树高度右子树高度。平衡因子只能是1，0，1。 最小不平衡子树：是指离插入点最近，且平衡因子绝对值大于1的结点作为根的子树。 调整原则：调整后仍保持二叉
14、排序树的性质不变。,28,AVL Tree 调整,1、LL型调整操作 2、RR型调整操作 3、LR型调整操作 4、RL型调整操作 LL RR LR RL 调整（旋转）原则：使中间值成为根点,K,D,A,K,M,X,K,P,L,K,D,F,29,AVL Tree 调整,30,AVL Tree 调整,45,23,9,90,98,18,0,-1,2,0,-1,2,68,调整原则1 确定调整结点：从底向上，碰到的第一个平衡因子绝对值大于1的结点，就是要调整的第一个不平衡结点。,3,31,AVL Tree 调整,方案1,调整原则2 确定调整类型：以不平衡结点为目标向下查找导致不平衡性的关键路径，即最长路
15、径。,32,AVL Tree 调整,18,23,90,98,18,0,1,1,0,-1,1,68,45,0,调整原则3 确定调整目标：以不平衡点开始向下连续三个结点（处于关键路径上），取中值结点为新平衡二叉树的根，旋转调整。,方案1,33,AVL Tree 调整,45,9,90,98,18,0,0,2,0,-1,1,68,23,0,23,9,90,98,18,0,1,1,0,-1,1,68,45,0,调整原则3 确定调整目标：以不平衡点开始向下连续三个结点（处于关键路径上），取中值结点为新平衡二叉树的根，旋转调整。,方案2,34,AVL Tree Example,35,AVL Tree Example,36,AVL Tree Example,37,AVL Tree 调整,B,C,1,0,-1,-1,2,A,0,Ra,Lb,Rc,Lc,new,h,h+1,h+1,38,AVL Tree 调整,B,C,1,0,-1,-1,2,A,0,Ra,Lb,Rc,Lc,new,39,AVL Tree 调整,B,C,0,-1,0,0,A,0,Ra,Lb,Rc,Lc,new,h+
