树和二叉树1(定义和性质)解析.ppt

例3： 已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，n3个度为3的结点，nk个度为k的结点，问该树中多少个叶子结点？ 例4： 已知一棵含有n个结点的树中，只有度为0和度为k的结点，求叶子结点数目？ 四、树与二叉树的区别 A．树中结点的最大度数没有限制，二叉树结点最大度数为2。 B ．无明确指出，树没有左、右子树之分，二叉树有明确的左、右子树之分。 二叉树 树 6.2.2 二叉树的存储结构 (1) 顺序存储结构 用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。 #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_TREE_SIZE+1]; // 1号单元存储根结点 SqBiTree bt; 完全二叉树 A B C D E F G H I J K L A[13] L K J I H G F E D C B A 1 2 3 4 5 6 7 8 9 10 11 12 若父结点在数组中i下标处，其左孩子在2*i，右孩子在2*i+1 A B C D E F G ? ? ? ? ? 表示该处没有元素存在仅仅为了好理解 A B C D E ? ? ? ? F G 一般二叉树 1 2 3 4 5 6 7 8 9 10 11 若父结点在数组中i下标处，其左孩子在2*i，右孩子在2*i+1 一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。 一个深度为H且只有H个结点的右单支树需要2h-1个结点存储空间 根据结点结构不同 二叉链表 三叉链表 (2) 链式存储结构 A D E B C F ? ? ? ? ? ? ? root lchild data rchild 结点结构: 1. 二叉链表 typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; lchild data rchild 结点结构: C 语言的类型描述如下: root A D E B C F ? ? ? ? ? ? ? ? 2．三叉链表 parent lchild data rchild 结点结构: typedef struct TriTNode { // 结点结构 TElemType data; struct TriTNode *lchild, *rchild; // 左右孩子指针 struct TriTNode *parent; //双亲指针 } TriTNode, *TriTree; parent lchild data rchild 结点结构: C 语言的类型描述如下: * 定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree) * 结点之间的连线虽然没有方向，但是并不是无向的，隐含了一种方向的关系： * 广义表表示：每棵树的树根放在前边作为广义表的名字 * * 因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。 * 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。 * * 设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝