计算机软件技术基础-03 算法和数据结构3

1、计算机软件技术基础3、算法和数据结构算法和数据结构树和二叉树树型结构是一类重要的非线性数据结构。在此类结构中，元素之间存在着明显的分层或嵌套关系，它们通常以各种形式的链表作存储结构，树和二叉树是最常用的树型结构。算法和数据结构树的定义和术语树结构类似一棵倒长的树，结构中含有一个类似“树根”的结点和若干类似“树叶”的结点以及若干分支节点树的形式化定义：树(Tree)是由n(n0)个结点组成的有限集合T其中有一个特定的称为根的结点；其余结点可分为m(m0)个互不相交的有限集T1,T2,T3 ,Tm每一个集合本身又是一棵树，且称为根的子树算法和数据结构树的表示，每进一层次加一个括号，同层之间用逗号分

2、开。例如：(A(B(E,F),C(G),D(H,I,J)，表示下面的树算法和数据结构度双亲（父）结点、子结点叶子结点、分支结点（非叶）兄弟、堂兄弟祖先、子孙层数路径、路径长度结点的基本术语算法和数据结构度：所有结点的最大度数。层数（深度、高度）：所有结点的最大层次。路径长度：从树根到每个结点的路径长度之和。树的基本术语算法和数据结构二叉树的定义和术语二叉树是另一种重要的树形结构，其结构定义为：二叉树(Binary Tree)是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为根的左子树和右子树的、互不相交的二叉树组成。算法和数据结构树和二叉树的区别树和二叉树之间最主要

3、的差别是：二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树算法和数据结构二叉树的性质包含n个(n0)元素的二叉树边数为n-1；若二叉树的高度为h(h=0), 则该二叉树最少有h个结点，最多有2h-1个结点；包含n个元素的二叉树的最大高度为n，最小为log2(n+1)；对于任意非空的二叉树，若叶子结点为n0，度为2的结点数为n2，则n0=n2+1。算法和数据结构两种特殊的二叉树满二叉树：高度为h(h=0), 有2h-1个结点ABDHCEFGIOJLNKM算法和数据结构两种特殊的二叉树完全二叉树：除最后一层外，其余层皆满，且最后一层的结点集

4、中在左边ABDHCEFGIJLK算法和数据结构树的存储结构树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理算法和数据结构二叉树的存储结构通常使用具有2个指针域的链表，LC为左指针域，指向结点的左子树，RC为右指针域，指向结点的右子树。亦可用数组的下标来模拟指针，即开辟三个一维数组DATA，LC和RC分别存放结点的元素及其左、右指针。算法和数据结构树的二叉树表示树转二叉树的方法在树(树林)与二叉树之间有一个自然的一一对应的关系，每一棵都能唯一地转换到它所对应的二叉树。有一个自然的方式把树转换成

5、对应的二叉树：凡是兄弟就用线连接起来；对每个非终端结点，除其最左孩子外，删去该结点与其他孩子结点的连线；再以根结点为轴心，顺时针旋转45度。算法和数据结构树的二叉树表示树转二叉树的方法有一个自然的方式把树转换成对应的二叉树：凡是兄弟就用线连接起来；对每个非终端结点，除其最左孩子外，删去该结点与其他孩子结点的连线；再以根结点为轴心，顺时针旋转45度。算法和数据结构树的二叉树表示树转二叉树的方法有一个自然的方式把树转换成对应的二叉树：凡是兄弟就用线连接起来；对每个非终端结点，除其最左孩子外，删去该结点与其他孩子结点的连线；再以根结点为轴心，顺时针旋转45度。算法和数据结构树的二叉树表示二叉树转树的

6、方法二叉树转为树的方式，基本上是树转二叉树的逆过程：如果二叉树某结点是其双亲的左孩子，则把他的右子孙都与其双亲结点链接；删除二叉树中所有结点与其右孩子的连线；再以根结点为轴心，对树进行旋转整理。ABEHCIFJGDABEHCIFJGD算法和数据结构树的二叉树表示二叉树转树的方法二叉树转为树的方式，基本上是树转二叉树的逆过程：如果二叉树某结点是其双亲的左孩子，则把他的右子孙都与其双亲结点链接；删除原二叉树中所有结点与其右孩子的连线；再以根结点为轴心，对树进行旋转整理。ABEHCIFJGDABEHCIFJGD算法和数据结构树的二叉树表示二叉树转树的方法二叉树转为树的方式，基本上是树转二叉树的逆过程

7、：如果二叉树某结点是其双亲的左孩子，则把他的右子孙都与其双亲结点链接；删除原二叉树中所有结点与其右孩子的连线；再以根结点为轴心，对树进行旋转整理。ABEHCIFJGDABEHCIFJGD算法和数据结构树和二叉树的遍历对于树形结构的运算很多，但最重要、使用最为广泛的是遍历。遍历一个树形结构就是按一定的次序，系统地访问该结构中的所有结点，使每个结点恰被访问一次。我们将重点讨论二叉树的遍历树的遍历根据树的递归定义，有两种遍历树的方法：先根(次序)遍历：若树中只有一个根结点，则访问树的根结点；否则，首先访问树的根结点，然后依次先根遍历每棵子树。后根(次序)遍历：若树中只有一个根结点，则访问树的根结点；

8、否则，首先依次后根遍历每一棵子树，然后访问树的根结点。算法和数据结构二叉树的遍历分析二叉树的结构特性可知，一棵非空的二叉树是由根结点、左子树、右子树三个基本部分组成，则遍历二叉树只要依次遍历这三部分即可。于是，可以有三种遍历方式：前序遍历； 中序遍历； 后序遍历。算法和数据结构二叉树的遍历ABEHCIFJGD使用前序遍历，则处理顺序为：ABEFCGDHIJ前序遍历二叉树的算法（DLR）为：若二叉树不空，则依次进行下列操作： a) 访问根结点； b) 前序遍历左子树； c) 前序遍历右子树。算法和数据结构二叉树的遍历中序遍历二叉树的算法（LDR）为：若二叉树不空，则依次进行下列操作： a) 中序

9、遍历左子树； b) 访问根结点； c) 中序遍历右子树。使用中序遍历，则处理顺序为：EFBGCHIJDAABEHCIFJGD算法和数据结构二叉树的遍历后序遍历二叉树的算法（LRD）为：若二叉树不空，则依次进行下列操作： a) 后序遍历左子树； b) 后序遍历右子树； c) 访问根结点。使用后序遍历，则处理顺序为：FEGJIHDCBAABEHCIFJGD算法和数据结构二叉树遍历的运算已知某二叉树的前序遍历序列为: ABDEGCFHIJ，中序遍历序列为：DBGEAHFIJC，写出该二叉树后序遍历的序列。ABDHCIGJEF算法和数据结构二叉树的实现二叉树的结构定义struct BiTreeNode

10、 int data; / 信息域 TreeNode *lchild; / 左孩子 TreeNode *rchild; / 右孩子;struct BiTree BiTreeNode *root;算法和数据结构二叉树的操作插入左孩子首先根据制定的结点值创建新结点，接着把原来的左孩子作为新节点的左孩子，然后把新结点链接到指定的位置。插入右孩子void InsertLeftChild(BiTreeNode *p, int d) BiTreeNode *node = (BiTreeNode*)malloc(sizeof(BiTreeNode); node-data = d; node-rchild =

11、NULL; node-lchild = p-lchild; p-lchild = node; 算法和数据结构二叉树的操作删除二叉树从根结点开始，递归删除左子树，再递归删除右子树，最后删除根结点。void DeleteBiTree(BiTreeNode *root) if (root = NULL) return; DeleteBiTree(root-lchild); DeleteBiTree(root-rchild); free(root); 算法和数据结构二叉树的操作删除左孩子删除左孩子也就是把左子树全部删除。删除右孩子void DeleteLeftChild(BiTreeNode *p) DeleteBiTree(p-lchild); p-lchild = NULL; 算法和数据结构二叉树的应用计算表达式 5+6*(9-4)+8/2 (5+(6*(9-4)+(8/2)(6*(9-4)+(8/2)(8/2)(6*(9-4)(9-4)算法和数据结构二叉树的应用计算表达式+54+6*/9-82算法和数据结构二叉树的应用计算表达式算法和数据结构二叉树的应用计算表达式算法和数据结构二叉树的应用增删和快速查找 10，6，12，7，-1，37，24，-9，3 用数组