树 概念 2011.pptVIP

编程中出现的问题 建立一个空的工程或者hello world 然后从工程出发，向工程中添加文件，.h,.cpp,etc 提示：注意窗口左下侧的file list中包含的文件。 一个工程中只能出现一个main()函数。 .H文件不能重复包含 指针变量和普通变量 typedef struct node{ DataType elem; struct node *next; }NODE; Void InsertAfter(NODE *D,DataType item ) Void main() { NODE *p,node_A; } New 类似于malloc p=new NODE; p1=new NODE(10); delete 类似于free delete p; delete [ ]p1; 第五章树(1) 概念 层次结构（非线性结构） 树(tree)的定义 定义：树是 n(n≥0)个结点的有限集T，其中 有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点: 树中至少有一个结点——根(root) 树中各子树是互不相交的集合 基本术语 结点(node)——表示树中的元素 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 结点的层次(level) ——从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest) ——m(m0)棵互不相交的树的集合 路径 根节点到某节点之间 两节点之间 路径是唯一的 路径的长度 结点的深度 (depth)，高度(height) 树的深度，高度 结点的祖先 结点后代 有向树： (１) 有确定的根； (２) 树根和子树根之间为有向关系。 有序树： 子树之间存在确定的次序关系。 无序树： 子树之间不存在确定的次序关系。 树的一个例子  森林：是m（m≥0）棵互不相交的树的集合 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点，F 被称为子树森林 树与线性结构比较 线性结构 第一个数据元素(无前驱) 最后一个数据元素(无后继) 其它数据元素(一个前驱、一个后继) 树型结构 根结点(无前驱) 多个叶子结点(无后继) 其它数据元素 (一个前驱、多个后继) 二叉树 定义 二叉树 或为空树； 或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。 二叉树的五种基本形态： 二叉树的性质 性质 1 ：在二叉树的第 i层上至多有2i-1 个结点。 (i≥1)用归纳法证明 性质 2 ：深度为 k 的二叉树上至多含2k-1 个结点（k≥1） 性质 3 :对任何一棵二叉树，若它含有n0叶子结点n2 个度为 2的结点，则必存在关系式：n0=n2+1 证明: 设二叉树上结点总数 n = n0+n1+n2 二叉树上分支总数 b = n1+2n2 b = n-1 = n0+n1+n2-1 两类特殊的二叉树 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。 完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应 性质 性质 4 ：具有 n 个结点的完全二叉树的深度为 [log2n+1] 性质 性质 5 ：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1至 n的编号，则对完全二叉树中任意一个编号为 i的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲, 否则编号i/2的结点为双亲结点 (2)若 2in，则该结点无左孩子否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。 树的存储结构 二叉树的顺序存储表示 二叉树的链式存储表示 顺序存储结构 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点:结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树 建立二叉树的顺序存储结构 void MakeSeqBTree(SeqList *L) { char ch; ch=getchar(); while(ch!=‘\n’) { if (ch!=‘ ‘) InsertRear(L,ch); ch=getchar();