软件技术基础09--树结构

1、软件技术基础软件技术基础制作主讲段景山树的基本概念树的基本概念有且仅有一个根结点除根结点以外的结点有且仅有一个父结点树的定义树的定义树的定义树的定义树的术语树的术语l(3)结点的关系结点的关系树的术语树的术语树的术语树的术语树的术语树的术语树的术语树的术语树的存储树的存储连续线性的下标不能很好的反映树的分支关系（非线性）树的存储树的存储二叉树二叉树仍然是递归定义。二叉树是树吗？二叉树二叉树二叉树的性质二叉树的性质1二叉树的数学特性二叉树与二进制之间存在必然联系，进而可以与整个数学发生关联了二叉树的性质二叉树的性质设n0为叶结点个数， n1为具有一个孩子的分支结点个数， n2为具有两个孩子的分支

2、结点个数， n为结点总个数条件1、 n = n0 + n1 + n2条件2、 n = 分支的个数 + 1设为分支的个数为B条件3、 B = 2 n2 + n1所以： 2n2 + n1 + 1 = n0 + n1 + n2二叉树的性质二叉树的性质二叉树的性质二叉树的性质完全二叉树完全二叉树二叉树二叉树顺序存储二叉树顺序存储二叉树顺序存储二叉树顺序存储二叉树101112131415用链表实现二叉树用链表实现二叉树dataLchileRchild根结点指针用链表实现二叉树用链表实现二叉树dLRdLRdLRdLRdLRdLRdLRdLR二叉树的遍历二叉树的遍历以根被访问顺序来划分不同的遍历方法在子树的

3、访问顺序中始终以左子树优先特点：二叉树的遍历二叉树的遍历ABCDEFGHIJKLMNOPQF G C E H B D J I A L N P O Q M K左左 根根 右右二叉树的遍历二叉树的遍历ABCDEFGHIJKLMNOPQA B C F G E H D I J K L M N O P Q根根 左左 右右二叉树的遍历二叉树的遍历ABCDEFGHIJKLMNOPQG F H E C J I D B P Q O N M L K A左左 右右 根根课堂练习课堂练习ABCDEFGHIJKLMNOPQA B C F G E H D I J K L M N O P QG F H E C J I D

4、B P Q O N M L K AF G C E H B D J I A L N P O Q M K二叉树的遍历二叉树的遍历ABC方法一、利用栈来实现回朔方法一、利用栈来实现回朔回到回到回溯回溯XABCDEFGHIJKLMNOPQABCFGE HDwhile( ! end_of(tree).while( ! end_of(tree) if( p != NULL )push(stack , p)p = p-Lchild; elsep = pop(stack);process(p);p = p-Rchild; ABCF GEwhile( ! end_of(tree) if( p != NULL )

5、push(stack , p)p = p-Lchild; elsep = pop(stack);process(p);p = p-Rchild;isEmpty(stack)ABCDEFGHIJKLMNOPQAP指针指针K_NULLNULLwhile( ! empty(tree) if( p != NULL )push(stack , p)p = p-Lchild; elsep = pop(stack);process(p);p = p-Rchild;ABCDEFGHIJKLMNOPQAP指针指针KNULLvoid inorder( tree)tnode_type * p;create_stac

6、k( stack );p = tree-root;访问结点访问结点while( p != NULL | ! empty(stack) )if ( p != NULL)push(stack, p);p = p - Lchild;elsep = pop(stack);process(p);p = p-Rchild;中根遍历算法（法一）中根遍历算法（法一）void preorder( tree)tnode_type * p;create_stack( stack );p = tree-root;while( p != NULL | ! empty(stack) )if ( p != NULL)pro

7、cess(p);push(stack, p);p = p - Lchild;elsep = pop(stack);process(p);p = p-Rchild;先根遍历算法先根遍历算法后根遍历算法在基本框架上如何更动以完成void postorder( tree)tnode_type * p;create_stack( stack );p = tree-root;while( p != NULL | ! empty(stack) )if ( p != NULL)push(stack, p);p = p - Lchild;elsep = pop(stack);p = p-Rchild; pro

8、cess( p )放到哪里？放到哪里？后根遍历后根遍历利用递归的遍历算法（重要）利用递归的遍历算法（重要）左左 根根 右右左左 根根 右右左左 右右 根根利用递归的遍历算法利用递归的遍历算法利用递归的遍历算法利用递归的遍历算法根根 左左 右右ABC中根遍历中根遍历中序遍历中序遍历先根遍历先根遍历先序遍历先序遍历后根遍历后根遍历后序遍历后序遍历利用递归的遍历算法利用递归的遍历算法二叉树的遍历二叉树的遍历二叉树的建立（上机练习）二叉树的建立（上机练习）ABC_DEF_G_H_I_JK_L_利用先根遍历算法框架，建立二叉树根据输入的情况，将新节点放在指定的位置，然后从新节点开始下一个过程二叉树的建立

9、（上机练习）二叉树的建立（上机练习）二叉树的建立（上机练习）二叉树的建立（上机练习）二叉树的建立（上机练习）二叉树的建立（上机练习）node * create_node（ch） node * p; p = (node *)malloc(sizeof(node); p-data = ch; p-Lchild = NULL; p-Rchile = NULL; return p;二叉树的建立（上机练习）二叉树的建立（上机练习）根据输入，生成新链点，主要包括申请链点空间输入根元素生成整个树的根以先根遍历算法为基础递归生成二叉树二叉树的操作二叉树的操作BCDFGEHnew哪一种插入方式更合理？法2维持遍

10、历顺序一致二叉树的插入二叉树的插入课堂练习课堂练习右右左左根根二叉树的删除二叉树的删除del左左右右爷爷二叉树的删除二叉树的删除左左右右左左右右爷爷爷爷deldeldel左左右右爷爷二叉树删除二叉树删除 课堂练习课堂练习ABCDEFGHIJKLMNOP左左右右爷爷FGHIJKLMNOPdel左左右右爷爷二叉树删除二叉树删除 课堂练习课堂练习二叉树的重构二叉树的重构F G C E H B D J I A L N P O Q M KA B C F G E H D I J K L M N O P QFGCEHBDJILNPOQMK二叉树的重构二叉树的重构树与二叉树的转换树与二叉树的转换1243567123456788森林与二叉树的转换森林与二叉树的转换树的应用树的应用树的应用树的应用树的应用树的应用树的应用树的应用树的应用树的应用220615树的应用树的应用树的应用树的应用57245724572452722242 3652734321 4623435271 35树的应用树的应用5724657241