《[2017年整理]《数据结构》第四讲_185008216》由会员分享，可在线阅读，更多相关《[2017年整理]《数据结构》第四讲_185008216（31页珍藏版）》请在金锄头文库上搜索。
1、数据结构 2012.2课程大纲第1讲 数据结构应用、概念、以及课程基础 第2讲 线性表-链表、队列 第3讲 堆栈、非线性数据结构-二叉树 第4讲 二叉树、堆 第5讲 哈夫曼树与k-d树 第6讲 检索操作 第7讲 分块检索与哈希表 第8讲 排序 第9讲 算法分析与图的基本概念 第10讲 图结构 第11讲 图应用 第12讲 高级数据结构内容-索引技术第四讲 二叉树、堆l 非线性数据结构-二叉树 概念 数据结构的效率 二叉树的基本概念 二叉树的基本性质 完全二叉树 定义在二叉树上的操作 遍历 节点计数 层次遍历二叉树 二叉排序树 定义 二叉排序树的节点插入 二叉排序树的节点删除 寻找被删除节点的中序
2、后继 二叉排序树的生成演示l 堆结构 堆的定义 建堆方法 最大堆建堆方法 建堆的起点 建堆程序 把元素插入到一个堆中 堆应用 l 哈夫曼树 树结构分类 等概率检索的最佳二叉树 树的路径与检索效率 等概率下的最佳检索树下次课内容线性结构链表的效率找粉色球需要爬高6层高度13找灰色球需要爬高7层找绿色球需要爬高8层找黄色球需要爬高9层123456789找红色球需要爬高10层10找橙色球需要爬高11层1112找月亮爬高12层13摘花冠需要爬高13层每次搜寻都从根开始，寻找任 何一球的概率相等，平均每次 检索的比较次数是多少？平均搜寻次数=(6+7+8+13)/8=63/8链头节点非线性结构二叉树的效
3、率1234567891011 121314找粉色球需 要搜寻4层找灰色球需 要搜寻4层摘花冠需 要搜寻4层每次搜寻都从根开始，寻找任何 一球的概率相等，平均每次检索 的比较次数是多少？ 平均搜寻次数=8*4/815树的基本概念树根root根的子树有一个分叉，节点度=1节点度=0，叶子深度=2深度=3最大的节点度数是树的度有三个分叉，节点度=3最大的节点层次是树的深度节点指针域与节点度无 关,指针域个数是树的度节点同构树的指针域个数R节点数n树的度k共有10个节点无需指向root, 故仅需9个指针空指针域m= n(k-1)+1R=30m=30-9n个节点，只需n-1个指针k越大,指针域浪费越 多
4、二叉树的基本概念二叉树它或为空树，或由一个根节点和两棵互不相交的左右子树组成。 树根root根的左子树左子树的根右子树的根根的右子树树的定义是递归的叶子的度为0树的度为2这棵子树没有度为1的节点二叉树链式存储结构左指针域右指针域数据域指针域非空，还有孩子指针域空，无后继孩子二叉树基本性质（1）（1）第i层上至多有2i-1个节点 第1层有21-1个节点第2层有22-1个节点第3层有23-1 个节点第4层6个节点left)； printf(“%d”，root-info)；inorder(root-right)；递归过程中子树根为空返回一棵二叉树由一组左、右子树构成分解：遍历一棵二叉树的任务可看成遍
5、历一组子树，每一 子树仍然是左、右子树构成，直至左、右子树为空后返回 。中序遍历，访问一棵左子树直至为空，访问叶子，访问右子树。否则遍历左子树访问根遍历右子树遍历子树的问题是互相 独立，且与原问题形式 相同，同一个函数、参 数不同的逐级调用-分 治算法与递归后序遍历的二叉树结点计数int counter(struct tree *root) int i=0; if(!root)return(0); i+=counter(root-left); i+=counter(root-right); return(+i); 对左子树结点累计对右子树结点累计对子树根结点累计如何设计一个 前序形式？前序遍历
6、中序遍历后序遍历中序遍历的的二叉树结点计数struct tree *inorder(struct tree *root,int *n) if(!root)return(0); inorder(root-left,n); *n+=1; printf(“%d,“,root-key); inorder(root-right,n); 利用中序遍历对二叉树中的节点计数树根指针使用指针返回参数值该地址里的内容加一计数中序输出二叉树节点序列遍历右子树遍历左子树通过引用对二叉树中的节点计数 struct tree *inorder_ref(struct tree *root,int inorder_ref(r
7、oot-left,rn); rn+=1; printf(“%d,“,root-key); inorder_ref(root-right,rn); 获得参数别名继续向下传递参数别名参数值加一引用使参 数传递清 晰注意，n是地址层次遍历二叉树输入根节点指针，按照第1层至第h层的顺序 （每层从左至右）遍历二叉树所有节点。 访问根访问左子树访问右子树访问左孙1访问左孙2访问右孙1访问右孙2最近的节点先访问队列结构排列出要被访问节点的所有子孙a1 a2 a3 按排列顺序访问节点a4 a5 已知节点所有的子孙，可以舍弃它a6 a7 if(root-left)左根入队if(root-right)右根入队输出
8、根队头元素出队层次遍历二叉树程序设计问题struct tree *stackM,*x;出入队元素是指针，因此队是指针型数组int queue_out(int *rx=pfront;front +=1; return(0);要返回参数值，需要 定义为指针的指针queue_out(front,rear,stack,要返回参数值，需要传递指针 变量的地址，就是指针的指针指针出队队满提示队操作正常提示层次遍历二叉树程序设计（引用 ）void layer_traversal(struct tree *root) struct tree *stackM,*x,* int front=0,rear=0, i
9、f(root)printf(“%d,“,root-key); if(root-left)queue_in(front,rrear,stack,root-left); if(root-right)queue_in(front,rrear,stack,root-right); while(rear!=front) queue_out(rfront,rear,stack,rx); printf(“%d,“,x-key); if(x-left)queue_in(front,rrear,stack,x-left); if(x-right)queue_in(front,rrear,stack,x-righ
10、t); 对指针x的引用定义队头和队尾指针及引用遍历操作左根指针入队右根指针入队队非空，继续遍历过程当前的根出队遍历操作左根指针入队右根指针入队int queue_out(int rx=pfront;front +=1;return(0);指针引用指针出队这是一个指针的队列二叉排序树定义与性质 二叉排序树或者是空树，或者任一节点具有下列性质：若左子树不空，则左子树每一节点的关键码均小于它的根节点关键码；若它右子树不空，则右子树每一节点的关键码均大于它的根节点关键码；其左右子树也分别是二叉排序树。 4523531224907845235312249078左子树结点的值 都小于根的值右子树结点的值
11、都大于根的值树的形状依赖于 节点输入顺序输入的节点总是被 插入到叶子位置每次从根节点开始 搜寻要插入或者删 除的节点位置 二叉排序树节点插入输入:45struct tree *root;/指示二叉树根节点的指针s=(struct tree*)malloc(sizeof(tree);45输入23s=(struct tree*)malloc(sizeof(tree);23输入5353s=(struct tree*)malloc(sizeof(tree); s=(struct tree*)malloc(sizeof(tree);输入12if(s-keykey)root-left=s;12if(!ro
12、ot)s-left=0;s-right=0;root=s;if(s-keyroot-key)root-right=s;新结点总是插 入到叶子位置二叉树节点插入程序struct tree *addtree(struct tree *root，struct tree *r，struct tree *s) if(!r) r=s; r-left=NULL; r-right=NULL; if(!root)return(r); if(r-keykey)root-left=r; elseroot-right=r; return(root); else if(s-keykey)addtree(r,r-left
13、,s); else if(s-keyr-key)addtree(r,r-right,s); root是当前节点r的父亲 待插入节点r为空，S被插在根或叶子上空树被插入根、非空被插入到叶子 空树时返回当前节点是根 若是叶子，小于根入左节点大于根入右节点r非空且非叶子，则开始递归寻找叶子 关键码小于父节点递归搜索左子树 否则搜索右子树 rootrrr-leftr-right二叉排序树节点删除45235338432010221541被删节点P度为0 释放节点free(p)被删节点P度为1 Fleft=Pleft; pp被删节点P度为2 p为保持有序,用p右子 树的最小节点s取代psS左分支必空三种情
14、况：被删节点的度=0；度=1；度=2F左指针置空512free(p)双亲指针置空 33二叉排序树节点删除程序 struct tree *removehelp(struct tree *root,int key)struct tree *p,*q,*temp;if(!root)return(NULL);if(root-key=key)if(root-left=root-right)free(root);return(NULL);elseif(root-left =NULL)p=root-right;free(root);return(p);elseif(root-right =NULL)p=ro
15、ot-left;free(root);return(p);else temp=deletemin(root-right);root-key=temp-key;return(root);elseif(root-keyright=removehelp(root-right,key);else root-left=removehelp(root-left,key);return(root);找到被删节点 对叶子直接删除 被删节点左分枝空 被删节点右分枝空 删除右子树最小节点 被删节点在右子树，递归寻找 它指向右子树最小节点 与被删节点p交换 返回新根root 被删节点在左子树，递归寻找 被删节点度=2 root获得s的值删除二叉树最小节点struct tree *deletemin(struct tree *if(!root)return(0);if(root-left)return(deletemin(root-left);else temp=root;root=root-right;return(temp);被删节点父指针的引用， 它是父指针的值。递归搜索到左分支为空的节点sroot是被删节点s的父节点的左指针的引用； 让它指向被删节点右端注意，返回的 是指向被删节 点s的指针S当前roottemproot是被删节点s的父节点的左指针，它（的值）指
