资源描述：
《树与二叉树基本操作.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构 树及基本操作树的基本概念空树：不含结点的树。非空树：至少含一个节点的树。只有一个根结点，其余结点分为m棵互不相交的子树，每棵子树又都是一棵树。（递归定义）ABCDEFGHIAABACBACBACBACBACBAGCBAFGCBAEFGCBADEFGCBADEFGCBADEFGCBAHDEFGCBAIHDEFGCBA树的二元组定义K={A,B,C,D,E,F,G,H,I}R={,,,,,,,}IHDEFGCBA例2、表达式树a*b+(c-d/e)*f/cab-f
2、**+ed树的表示方法：1、树形图2、二元组3、目录结构4、集合图5、凹入表6、广义表树的基本术语结点的度：结点的儿子数（注意不包括孙子）树的度：树中所有结点的度的最大值分支结点（非终端结点）：度大于0的结点叶子结点（终端结点）：度为0的结点孩子结点：某结点的后继叫该结点的孩子。双亲结点（父结点）：某结点的前驱叫该结点的父亲。显然，根结点没有双亲，叶结点没有孩子。结点的层数：根为第一层，其儿子为第二层，孙子为第三层，以此类推。树的深度（高度）：结点的最大层数。森林：互不相交的树的集合。对于每个分支结点，其子树的集合就是森林。IHDEFGCBA二叉树
3、的定义树的度不超过2的有序树，非常重要的数据结构。IHDFGCBA二叉树的性质性质1：二叉树第i层上至多有2^(i-1)个结点（i≥1）性质2：深度为h的二叉树至多有2^h-1个结点。满二叉树：各层结点均达到2^(i-1)完全二叉树：除最后一层外，其余各层均满，且最后一层的结点集中在左边。给完全二叉树的结点从上到下，从左到右依次标号，则完全二叉树的标号性质有：性质1：若i<=(ndiv2),则i为分支结点，否则为叶子结点。性质2：在N个结点的完全二叉树中，若ｎ为奇数，则，所有分支都有左右儿子，若ｎ为偶数，则n/2的结点只有左儿子，没有右儿子。其他结
4、点有左右儿子。性质3：标号为i的结点，其左儿子为2i，右儿子为2i+1性质4：若标号为i的结点有双亲，则i>1且其双亲结点为（idiv2）二叉树的性质完全二叉树的深度性质：N个结点的完全二叉树，其深度为trunc(log2n)+1理想平衡树：二叉树中，除最后一层外，其余层都是满的，则称此树为理想平衡树。满二叉树是特殊的完全二叉树，完全二叉树是特殊的理想平衡树。FDEGCBADECBAEGCBA满二叉树完全二叉树理想平衡树完全二叉树理想平衡树理想平衡树二叉树的存储结构1、线性存储顺序存储二叉树，首先将二叉树按照完全二叉树中对应的位置进行标号，然后，以
5、每个结点的标号为下标，将对应的值存储到一个一维数组中。IHDFGCBA可见：完全二叉树用顺序存储极好，但一般二叉树容易造成空间浪费。二叉树的存储结构2、动态链接存储，三个域的节点：或者再添加一个指向父亲的指针。Typepnode=^tnode;tnode=recorddata:elementtype;left,right:pnode;end;3、静态链接存储Typetnode=recorddata=elementtype;left,right:integer;end;Vara:array[1..maxl]oftnode;IHDFGCBA存放的顺序是
6、任意的1．建立一棵二叉树Procedurepre_crt(Varbt:tree)；{按先序次序输入二叉树中结点的值，begin生成二叉树的单链表存储结构}read(ch)；ifch=‘’Thenbt:=Nil{’’表示空树}elsebeginNew(bt)；{建根结点}bt^.data:=ch；pre_crt(bt^.lchild)；{建左子树}pre_crt(bt^.rchild)；{建右子树}end；end；2．删除二叉树Proceduredis(Varbt:tree)；beginIfbt<>Nilthenbegindis(bt^.lchild
7、)；{删左子树}dis(bt^.rchild)；{删右子树}dispose(bt)；{释放父结点}end；end；3．插入一个结点到二叉树中procedureinsert(varbt:tree；n:Integer)；beginifbt=Nilthenbegin{空树，则为根结点}new(bt)；bt^.data:=n；bt^.lchild:=Nil；bt^.rchild:=Nil；endelseIfnbt^.datatheninsert(bt^.rchild
8、,n)；{>，右}end；4．在二叉树中查找一个数，找到返回该结点,否则返回nilFunctionfind(bt:tree
