第一章算法概要课件

第一章算法概要第一章算法概要第一章算法概要第二章基本数据结构及其运算（五）树的基本概念二叉树2020/11/261第二章基本数据结构及其运算（五）树的基本概念二叉树2020/11/2621树的基本概念非线性结构对于结构中的一个结点，可能有多个前趋和多个后继线性表中是有且仅有一个前趋和一个后继1.1树的定义树是以分支关系定义的层次结构。倒生树：树根在上，根上分茎，茎上分叶是族谱、社会组织机构一类实体的逻辑抽象树的基本概念2020/11/263对定义的理解（1）有限集（2）递归定义：树，根，子树（3）有且仅有一个根结点（4）子树是互不相交的有限集（5）树的层次性有且仅有一个根结点除根结点以外的结点有且仅有一个父结点树的定义2020/11/264树是一种数据结构Tree=(D,R)D：元素的集合R：元素关系的集合（父、子关系前件、后件关系）各结点没有或仅有一个父结点有且仅有一个根结点各结点可以有任意个子树树的定义2020/11/2651.2树的术语1）结点2）度与深度根结点没有前驱，仅有后继结点的度：该结点拥有的子树数目。树的度：最大的结点度深度：最大的层次数叶结点(茎)分支结点没有后继，仅有前驱有且仅有一个前驱，可以有多个后继树的术语2020/11/266树的术语孩子兄弟祖先子孙双亲孩子A3）A节点的2020/11/267树的术语4）路径（树枝，分支）从K1出发自上而下到K2所经历的所有结点序列K1K2K3K4K5K6K7K1K4K7K2树上两节点之间的路径有？条2020/11/268树的术语5）有序树与无序树有序树：兄弟有长幼之分，从左至右。交换兄弟位置，变成不同的树。2020/11/269树的术语6）森林不相交的树的集合2020/11/2610二叉树2二叉树2.1、定义二叉树是结点的有限集，或为空，或由根的左、右子树组成，左右子树又分别是符合定义的二叉树。对比树的定义：空二叉树

树的定义中没有空树的概念不多于2个孩子树的节点可以有任意个子树子树有左右之分无序树可不区分左右树的其它定义适用于二叉树：根茎叶、度、路径仍然是递归定义。二叉树是树吗？2020/11/2611二叉树（4）二叉树的形态空树无子树仅有左子树有左右子树仅有右子树2020/11/2612二叉树的性质2.2、二叉树的性质（1）在二叉树的第i层上最多有2i-1个结点第i层的结点数最多是第i-1层的两倍（2）深度为k的二叉树最多有2k-1个结点（3）叶结点数比具有两个孩子的结点数多个1二叉树的数学特性二叉树与二进制之间存在必然联系，进而可以与整个数学发生关联了2020/11/2613二叉树的性质（3）叶结点数比具有两个孩子的结点数多1个设n0为叶结点个数，

n1为具有一个孩子的分支结点个数，

n2为具有两个孩子的分支结点个数，

n为结点总个数结论：n0=n2+1;条件1、n=n0+n1+n2条件2、n=分支的个数+1设为分支的个数为B条件3、B=2n2+n1所以：2n2+n1+1=n0+n1+n22020/11/2614二叉树的性质（4）深度为K的满二叉树，结点个数为2k-1满二叉树：所有的结点要么有两个孩子，要么一个也没有。所有的叶结点都位于同一层。满二叉树：“装满”节点的二叉树半满二叉树：深度为K的二叉树，K－1层是满二叉树，K层节点个数不足2K－1个2020/11/2615二叉树的性质（5）具有n个节点的完全二叉树，深度为

[log2n]+1完全二叉树：特殊的半满二叉树，最后一层节点从左至右依次排列，没有间断。如果对节点数为n的完全二叉树自上而下，从左至右依次编号，则节点i的父结点为[i/2]123456若2i≤n，则i的左后继是2i；若2i>n,则i无左后继若2i＋1≤n，则i的右后继是2i＋1；若2i>n,则i无右后继2020/11/2616完全二叉树关于完全二叉树的其他描述形式如果对满二叉树的节点从上至下，从左至右连续编号，具有n个节点的完全二叉树各节点与同样深度的满二叉树的前n个节点一一对应叶节点仅位于下两层，对任一节点，若其右子树的深度为1，则其左子树的深度不小于12020/11/2617二叉树满二叉树半满二叉树完全二叉树非完全二叉树半满二叉树半满二叉树非完全二叉树2020/11/2618二叉树的遍历2.3、二叉树的操作2.3.1遍历操作分支及根的遍历顺序ABC中根遍历中序遍历AC先根遍历先序遍历B后根遍历后序遍历AABBCC以根被访问顺序来划分不同的遍历方法在子树的访问顺序中始终以左子树优先特点：左根右根左右左右根2020/11/2619二叉树的遍历1）中根遍历（中序遍历）ABCDEFGHIJKLMNOPQFGCEHBDJIALNPOQMK左根右2020/11/2620二叉树的遍历2）先根遍历（先序遍历）ABCDEFGHIJKLMNOPQABCFGEHDIJKLMNOPQ根左右2020/11/2621二叉树的遍历3）后根遍历（后序遍历）ABCDEFGHIJKLMNOPQGFHECJIDBPQONMLKA左右根2020/11/2622思考：第一个被遍历的节点，最后一个被遍历的节点，课堂练习写出这颗二叉树的三种遍历顺序ABCDEFGHIJKLMNOPQ3、后根遍历（左右根）ABCFGEHDIJKLMNOPQGFHECJIDBPQONMLKA1、中根遍历（左根右）2、先根遍历（根左右）FGCEHBDJIALNPOQMK2020/11/2623树的存储2.4树的存储2.4.1连续顺序存储K1K2K5K4K6a[0]a[1]a[2]a[3]a[4]连续线性的下标不能很好的反映树的分支关系（非线性）2020/11/2624DATA子树123树的存储2.4.2、链接存储－－多重链表树的节点对应于链表的结点树节点间的分支关系用结点间的指针描述结点可能有多个指针－－多重链表，每个指针描述对应节点的一个分支关系有且仅有一个根结点不同的指针指向不同的子树根结点一个子树有仅有一个根结点问题，一个结点里究竟该有多少个指针呢？2020/11/2625顺序存储二叉树2.5.1顺序存储二叉树将完全二叉树从上到下，从左到右编号后，结点号码可作为数组的下标，从而将完全二叉树顺序存储下来。当给出任意结点i，我们可以知道它的父结点为[i/2]，两个孩子分别为2i和2i＋1。一般的二叉树相对于同样深度的完全二叉树，缺失了部分结点，在顺序存储时，这些位置要空出来。以维持结点编号之间的父子换算关系如此存放，将浪费较多空间2020/11/2626顺序存储二叉树例HACBDEGFIKJMOUP123456789101112131415AHBCEDFGKIMJOPUa[1]a[15]HACBEGFIUPM123456789101112131415AHBCEFGIMPUa[1]a[15]数组的下标可以体现逻辑关系2020/11/2627用链表实现二叉树2.5.2用链表实现二叉树二叉树链表结点的定义structBtnode{Tdata;Btnode

*Lchild;Btnode

*Rchild;

};dataLchileRchild左孩子，左子树右孩子，右子树2020/11/2628用链表实现二叉树二叉树的链表结构dLRdLRdLRdLRdLRdLRdLRdLR2020/11/2629二叉树的建立2.5.3建立二叉树设输入次序：（以先根为序）ABC__DEF__G___H_I_JK__L__ABC__DEF__G___H_I_JK__L__每一个空格“_”表示一个空指针利用先根遍历算法框架，建立二叉树根据输入的情况，将新节点放在指定的位置，然后从新节点开始下一个过程2020/11/2630二叉树的建立template<classT>voidBinary_Tree<T>::creat_Binary_Tree(Tend){Btnode<T>*p;Tx;cin>>x;if(x==end)return;createanewnodep;p->d=x;p->lchild=NULL;p->rchild=NULL;p=newBtnode<T>;根据输入，生成新链点，主要包括申请链点空间输入新元素生成整个树的根BT=p;

creat(p,1,end);creat(p,2,end);return;}以先根遍历算法为基础递归生成二叉树2020/11/2631二叉树的建立template<classT>staticcreat(Btnode<T>*p,intk,Tend){Btnode<T>*q;Tx;cin>>x;if(x!=end){q=newBtnode<T>;q->d=x;q->lchild=NULL;q->rchild=NULL;if(k==1)p->lchild=q;if(k==2)p->rchild=q;creat(q,1,end);creat(q,2,end);}return;}2020/11/2632二叉树的遍历中根遍历算法算法实现分析遍历过程：从根开始ABC1、找到B，但不访问B2、根据B找到A，访问A3、再回到B、访问B4、根据B找到C，访问C方法一、利用栈来实现回朔回到回溯X2020/11/2633ABCDEFGHIJKLMNOPQ1、树（子树）根入栈，不访问2、左子树入栈，左子树的各子树根依次入栈即反复进行步骤13、当左子树为空时，出栈，访问根结点4、根节点右子树入栈（新树入栈，到步骤1去遍历右子树）5、当右子树为空时，出栈，访问（祖先）爷结点，将爷结点的右子树入栈（新树入栈，回到步骤1)总结：树入栈后一直朝左走（一路进栈），走不动时出栈并访问节点。同时将该节点右子树入栈。如果其右子树为空，就再出栈一个节点，访问，出栈节点右子树入栈ABCFGEHD2020/11/2634利用递归的遍历算法方法二：利用递归调用来实现回溯中根遍历递归算法template<classT>staticintrav(Btnode<T>*p){if(p!=NULL){intrav(p->lchild);cout<<p->d<<"";intrav(p->rchild);}return0;}左根右2020/11/2635后根遍历递归算法template<classT>staticpostrav(Btnode<T>*p){if(p!=NULL){postrav(p->lchild);postrav(p->rchild);cout<<p->d<<"";}return;}左右根利用递归的遍历算法2020/11/2636利用递归的遍历算法先根遍历递归算法template<classT>staticpretrav(Btnode<T>*p){if(p!=NULL){cout<<p->d<<"";pretrav(p->lchild);pretrav(p->rchild);}return;}根左