数据结构c树与二叉树

《数据结构c树与二叉树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、二叉树定义[二叉树]二叉树（binarytree）t是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。二叉树和树的根本区别是：•二叉树可以为空，但树不能为空。•二叉树中每个元素都恰好有两棵子树（其中一个或两个可能为空）。而树中每个元素可有若干子树。•在二叉树中每个元素的子树都是有序的，也就是说，可以用左、右子树来区别。而树的子树间是无序的。像树一样，二叉树也是根节点在顶部。二叉树左(右)子树中的元素画在根的左(右)下方

2、。在每个元素和其子节点间有一条边。二叉树的特性特性1包含n(n>0)个元素的二叉树边数为n-1。证明:二叉树中每个元素(除了根节点)有且只有一个父节点。在子节点与父节点间有且只有一条边，因此边数为n-1。二叉树的高度（height）或深度（depth）是指该二叉树的层数。特性2若二叉树的高度为h，h≥0，则该二叉树最少有h个元素，最多有2h-1个元素。证明:因为每一层最少要有1个元素，因此元素数最少为h。每元素最多有2个子节点，则第i层节点元素最多为2i-1个，i>0。h=0时，元素的总数为0，也就是20-1

3、。当h>0时，元素的总数不会超过.特性3包含n个元素的二叉树的高度最大为n，最小为[log2(n+1)]。证明:因为每层至少有一个元素，因此高度不会超过n。由特性2，可以得知高度为h的二叉树最多有2h-1个元素。因为n≤2h-1，因此h≥log2(n+1)。由于h是整数，所以h≥[log2(n+1)]。当高度为h的二叉树恰好有2h-1个元素时，称其为满二叉树（fullbinarytree）假设从满二叉树中删除k个元素，其编号为2h-i,1≤i≤k，所得到的二叉树被称为完全二叉树（completebinaryt

4、ree）在完全二叉树中，一个元素与其孩子的编号有非常好的对应关系。其关系在特性4中给出。特性4设完全二叉树中一元素的序号为i,1≤i≤n。则有以下关系成立：1)当i=1时，该元素为二叉树的根。若i>1，则该元素父节点的编号为ëi/2û。2)当2i>n时，该元素无左孩子。否则，其左孩子的编号为2i。3)若2i+1>n，该元素无右孩子。否则，其右孩子编号为2i+1。证明:通过对i进行归纳即可得证。二叉树描述链表描述二叉树最常用的描述方法是用链表或指针。每个元素都用一个有两个指针域的节点表示，这两个域为LeftCh

5、ild和RightChid。除此两个指针域外，每个节点还有一个data域。这种定义为二叉树节点提供了三种构造函数。第一种无参数，初始化时节点的左右孩子域被置为0（即NULL）；第二种有一个参数，可用此参数来初始化数据域，孩子域被置为0；第三种有3个参数，可用来初始化节点的3个域。二叉树的边可用一个从父节点到子节点的指针来描述。指针放在父节点的指针域中。因为包括n个元素的二叉树恰有n-1条边，因此将有2n-(n-1)=n+1个指针域没有值，这些域被置为0。----------------------------

6、----------------------------------------------------------------------------------------------------//链表二叉树的节点类templateclassBinaryTreeNode{friendvoidVisit(BinaryTreeNode*);friendvoidInOrder(BinaryTreeNode*);friendvoidPreOrder(BinaryTreeNode

7、*);friendvoidPostOrder(BinaryTreeNode*);friendvoidLevelOrder(BinaryTreeNode*);//friendintmain(void);public:BinaryTreeNode(){LeftChild=RightChild=0;}BinaryTreeNode(constT&e){data=e;LeftChild=RightChild=0;}BinaryTreeNode(constT&e,BinaryTreeNode*l,Binary

8、TreeNode*r){data=e;LeftChild=l;RightChild=r;}private:Tdata;BinaryTreeNode*LeftChild,//左子树*RightChild;//右子树};------------------------------------------------------------------------------------------