中国著名特级教师教学思想录34

《中国著名特级教师教学思想录34》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树和图西安交通大学计教中心ctec.xjtu.edu.cn树的递归定义:树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足：1）其中有一个特定的元素称为T的根root。2）除根以外的集合可被划分为m个不相交的子集T1，T2，…，Tm，其中每个子集都是树。它们称为根root的子树。GACFDEB树的一般形式与树相关的术语•结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。•结点的度：结点拥有的非空子树的个数。•树的度：树中所有结点的度的最大值。•叶子结点：没有非空子树的结点。•分支结

2、点：至少有一个非空子树的结点。•孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。•兄弟结点：具有相同父结点的结点互为兄弟结点。•结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。•树的深度：树中结点所在的最大层次。•有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。•森林：由零棵或有限棵互不相交的树组成的集合。二叉树的定义二叉树可以是空树，当二叉树非空时，其中有一个根元素，余下的元素组成两个互不相交二叉树

3、，分别称为根的左子树和右子树。二叉树是有序树，也就是说任意结点的左、右子树不可交换。而一般树的子树间是无序的。特殊形式的二叉树满二叉树：当二叉树每个分支结点的度都是2，且所有叶子结点都在同一层上，则称其为满二叉树。完全二叉树：从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树。满二叉树可看作是完全二叉树的一个特例。AFC满二叉树GDBEAC完全二叉树DBE二叉树有下列重要性质：（1）在二叉树的第k层上至多有2k-1个结点(k≥1)证明：当k=1时，命题显然成立。假定k=n-1时命题成立，则第n层（k=

4、n）的结点数最多是第n-1层的2倍，所以第n层最多有2*2n-2=2n-1个结点。命题成立。（2）深度为h的二叉树上至多含2h-1个结点(h≥1)证明：根据性质1容易知道深度为h的二叉树最多有20+21+…+2h-1个结点，即最多有2h-1个结点。（3）包含n(n>0)个结点的二叉树总的分支数为n-1证明：二叉树中除了根结点之外每个元素有且只有一个父结点。在所有子结点与父结点间有且只有一个分支，即除根外每个结点对应一个分支，因此二叉树总的分支数为n-1。（4）任何一棵二叉树，若含有n0个叶子结点、n2个度为2的结点，则必存在关系式n

5、0=n2+1证明：设二叉树含有n1个度为1的结点，则二叉树结点总数显然为：n0+n1+n2（2-2）再看看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为：1+n1+2n2（2-3）由（2-2）（2-3）两式可知：n0=n2+1（5）具有n个结点的完全二叉树的深度为[log2(n)]+1证明：假设二叉树的深度为h，则必有2h-1-1

6、，从而得到h-1≤log2(n)n，则该结点无左孩子。否则，编号为2i的结点为其左孩子结点；③若2i+1>n，则该结点无右孩子。否则，编号为2i+1的结点为其右孩子结点。证明通过对i进行归纳即可得证。二叉树的链式存储结点定义：structBinTreeNode{ElemTypedata;structB

7、inTreeNode*leftChild,*rightChild;};这里leftChild和rightChild分别为某一结点指向其左孩子和右孩子的指针。对于叶子结点或一个新生成的结点而言，其左孩子和右孩子指针都应为空值。二叉树的链式存储ABC∧∧D∧∧E∧∧利用这种结点形式存储的树一般称为二叉链表。从根结点出发，可以访问二叉树的任何结点。为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。二叉树的常用算法包括：获取根结点指针、判断树是否为空、插入或删除结点、插入或删除子树、二叉树遍历等。二叉树类可描

8、述如下：classBinTree{public:BinTreeNode*root;//定义根结点指针BinTree(){root=NULL;}//构造函数，定义空树//判断树是否为空boolIsEmpty(){returnroot==