第二章线性表4.1树的基本概念校长(根目录)\例3树是由n(n>0)个结点组成的有限集合,它满足以下两个条件:1、有且只有一个特定的称为根的结点；2、其余结点可分成m>0个不相交的子集T1,T2,…,Tm,其中每一个子集Ti又为一棵树，分别称之为根的子树。J1.文氏图表示法2.凹入表示法1.结点的度：2.树的度：7.树林(森林):m0棵不相交的树组成的树的集合.一.多重链表结构2.不定长结点的多重链表结构二.三重链表结构一.二叉树的定义二叉树的基本形态：二.两种特殊形态的二叉树1.一棵非空二叉树的第i层最多有2i–1个结点(i1)。2.深度为h的非空二叉树最多有2h-1个结点.3.若非空二叉树有n0个叶结点,有n2个度为2的结点,则n0=n2+15.若对具有n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为i的结点具有以下性质:(1)当i=1,则编号为i的结点为二叉树的根结点;若i>1,则编号为i的结点的双亲结点的编号为i/2.(2)若2i>n,则编号为i的结点无左子树;若2in,则编号为i的结点的左子树的根的编号为2i.(3)若2i+1>n,则编号为i的结点无右子树;若2i+1n,则编号为i的结点的右子树的根的编号为2i+1.一.二叉树的顺序存储结构1对于一般二叉树,只须在二叉树中“添加”一些实际上二叉树中并不存在的“虚结点”(可以认为这些结点的数据信息为空),使其在形式上成为一棵“完全二叉树”,然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组BT[2h-1]中。A二.二叉树的链式存储结构(二叉链表)在类C语言中，一个链结点的描述为：一.什么是二叉树的遍历常用的二叉树的遍历方法:1.前序遍历2.中序遍历3.后序遍历二.前序遍历voidpreorder(bitree*t){if(t!=NULL){printf(“%c\n”,t->data);preorder(t->lchild);preorder(t->rchild);}}三.中序遍历voidinorder(bitree*t){if(t!=NULL){inorder(t->lchild);printf(“%c\n”,t->data);inorder(t->rchild);}}四.后序遍历voidpostorder(bitree*t){if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf(“%c\n”,t->data);}}A