3非线性结构一树的定义和基本操作例1:树根：A子树：T1={B,E,F}T2={C,I}T3={D,G,H,J}节点节点的度叶子（终端节点）分支节点孩子双亲(父节点)兄弟堂兄弟祖先子孙层次深度森林父节点：每一个节点只有一个前件，称为父节点。子节点：每一个节点可以有多个后件，都称为该节点的子节点。根节点：没有前件的节点只有一个，称为树的根节点。叶子节点：没有后件的节点称为叶子节点。节点的度：一个节点所拥有的后件个数称为该节点的度。度树的度：所有节点中的最大度称为树的度。树的深度：树的最大层次称为树的深度。子树:在树中，以某节点的一个子节点为根构成的树称为该节点的一棵子树。A(2)嵌套集合表示法树的应用树的应用二、二叉树具有3个节点的树和二叉树的所有不同形态。(1)具有3个节点的树有2种不同的形态，(2)具有3个节点的二叉树有5种不同的形态，针对满二叉树和设完全二叉树，设共有n个节点。如果从根节点开始，按层序（每一层从左到右）用自然数1，2，…，n给节点进行编号，则对于编号为k(k＝1，2，…，n)的节点有以下结论：(1)若k＝1，则该节点为根节点，它没有父节点；若k＞1，则该节点的父节点编号为INT(k/2)。(2)若2k≤n，则编号为k的节点的左子节点编号为2k；否则该节点无左子节点（显然也没有右子节点）。(3)若2k＋1≤n，则编号为k的节点的右子节点编号为2k＋1；否则该节点无右子节点。三遍历二叉树二叉树的遍历是要确定访问各节点的顺序,以便不重不漏地访问到二叉树的所有节点。实际就是将二叉树这种非线性结构按某种需要转化为线性序列，以便以后在对二叉树进行某种处理时直接使用。Preorder(TREENODE*p){if(p==NULL)return;printf(“%c”,p->data);if(p->lchild!=NULL)preorder(p->lchild);if(p->rchild!=NULL)preorder(p->rchild);}inorder(TREENODE*p){if(p==NULL)return;if(p->lchild!=NULL)inorder(p->lchild);printf(“%c”,p->data);if(p->rchild!=NULL)inorder(p->rchild);}postorder(TREENODE*p){if(p==NULL)return;if(p->lchild!=NULL)postorder(p->lchild);if(p->rchild!=NULL)postorder(p->rchild);printf(“%c”,p->data);}voidpreorder(JD*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}(2)非递归算法（中序遍历）非递归算法（中序遍历）【例】如果一棵二叉树的中序遍历序列为：ABCDE；后序遍历序列为：DECBA；构建这棵树。二叉排序树的生成P43依次读入给定序列中的每一个元素：(1)若当前的二叉排序树为空，则读入的元素为根节点；(2)若读入的元素值小于根节点值，则将元素插入到左子树中；(3)若读入的元素值不小于根节点值，则将元素插入到右子树中。无论是插入到左子树还是右子树，同样按照上述方法处理。【例】有10个数构成的序列{190，381，12，40，410，394，540，760，85，476}；根据算法思想构建一棵二叉排序树。(p44)树转换成二叉树：方法：用孩子兄弟存储法存储二叉树，自然实现转换得到二叉树的特点：根节点缺右支森林转换成二叉树：方法：将每棵树转换为二叉树将第二棵树的根节点接在第一棵的右支上，将第三棵树的根节点接在第二棵的右支上，如此类推。1、将树转换成二叉树加线：在亲兄弟之间加一连线(不包括堂兄弟）抹线：对每个节点，除了其左孩子外，去除其与其余孩子之间的关系旋转：以树的根节点为轴心，将整树顺时针转45°2、将二叉树转换成树加线：若p节点是双亲节点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将节点按层次排列，形成树结构3、森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根节点用线相连以第一棵树根节点为二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树型结构4、二叉树转换成森林抹线：将二叉树中根节点与