Java基础复习笔记08数据结构-二叉树和二叉树的遍历.doc

《Java基础复习笔记08数据结构-二叉树和二叉树的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途Java基础复习笔记08数据结构-二叉树和二叉树的遍历刘岩Email:suｈuanzheｎg７７84877@１6３.com1.二叉树一般的树限制比较少，所以才提出了具有特色的二叉树的概念。二叉树顾名思义,每个节点最多有两个子节点,分别叫做左子节点和右子节点。有了这个限定性后，就可以干很多树不能干的事情了。如果树的所有层，除了最后一层的节点外都是两个子节点，那么称这个树为满二叉树。如下图若设二叉树的高度为h，除第h层外,其它各层(1~h-1)的结点数都达到最大个数,第h层所有的节点都连续集中在最左

2、边，这就是完全二叉树。2.二叉树的操作二叉树具有为指定节点增加子节点操作、判断树是否为空、返回根节点、返回指定节点的父节点，返回指定节点的左子节点、返回指定节点的右子节点、返回树的深度、返回指定节点的位置。3.二叉树的延伸其实二叉树只是一个引子,计算机界很多的算法都是根据二叉树所展开的,比如排序二叉树、红黑树、哈夫曼树、线索二叉树等等。个人收集整理勿做商业用途1.顺序实现二叉树下面我们来看看二叉树的顺序实现方式,顺序实现二叉树就是利用数组存储所有的二叉树的节点。代码如下packaｇedateStructｅｒ．tｒee．

3、biｎaryＴreｅ;/＊**顺序二叉树*　*　@auｔhorliuyan*/publｉcｃlassArrayＢinaｒｙTree＜T>{ﻩ//树的默认深度priｖatestaｔｉcfｉnaｌiｎtＤefTreeDｅeｐ=4；//节点数组ﻩprｉｖatｅ　Ｏbjｅct[]datａs；//指定的树的深度ﻩpriｖateｉnttｒeeＤeep；//　实际的数组个数ﻩｐｒivateiｎtａｒrａｙＳize；/**ﻩ*默认构造函数*／ﻩpubｌicAｒｒayBinaryＴｒeｅ()　{ﻩﻩ//　设置默认的树深度ｔrｅeＤｅeｐ

4、　=　ＤefTreeDeeｐ；/／　2的DefTｒeeDｅｅp次方-1个数组元素ﻩﻩａrraySiｚe=(ｉnｔ)　Ｍａｔh.ｐow(2，　ＤefＴreeDeep）-1;ﻩdatａs　＝neｗObjeｃt[ａｒｒaｙSize］;ﻩ}/**ﻩ　*指定深度构建二叉树*@paramdeepﻩ　＊/ｐubｌiｃArrａyBｉnaryTｒｅe(inｔ　deep)｛ﻩﻩ/／按指定深度ﻩｔｒｅeＤeep=deep；arraySize=(ｉnt）　Maｔh.ｐow(2,treeDeeｐ)-　1;个人收集整理勿做商业用途datas=ne

5、wＯｂject[arraｙSiｚe];}ﻩ/*＊ﻩ　*指定深度和指定根节点构建二叉树　*@paramｄeepﻩ　*　@parａmｄａtaﻩ＊/pｕblicＡrrayBinarｙTrｅe(ｉnｔdeep,Ｔ　daｔa)　｛ﻩ//按指定深度ﻩﻩtreｅＤeeｐ=　ｄeep；ﻩﻩａｒraySｉze=(ｉnt)Ｍaｔh.ｐｏw（2,treｅDeep）-１;dａtａs=　newObｊect[arｒayＳｉzｅ]；ﻩdaｔaｓ[0]=dａta;ﻩ｝ﻩ/**ﻩ*为指定节点索引增加子节点*@param　inｄeｘ＊@paraｍ　dａt

6、ａ　*@ｐarａmiｓLｅｆt　*　＠rｅtｕｒnﻩ＊／ﻩpublｉcbooleaｎaddNｏdｅ(ｉｎtiｎdex,　T　ｄatａ,boｏlｅanisLefｔ){ﻩif(index*2+2＞arｒaySize

7、

8、datａs[index]==nulｌ)｛ﻩﻩｔhｒowneｗRuntimeＥxception("标记无效＂);ﻩ}if(iｓLeｆt){ﻩﻩﻩdaｔａs[inｄｅx*　2　+1]　=　daｔａ；ﻩﻩ}eｌse{ﻩdａtａs[iｎdｅx*2+　2]=dａta;ﻩ}ﻩrｅturｎtｒｕｅ；ﻩ}/**ﻩ　＊判断二叉

9、树是否为空ﻩ*ﻩ*@ｒeｔｕrｎﻩ　*/ﻩｐuｂｌicbooleanisEｍpty(){ﻩretｕrn　arrayＳｉzｅ==0;ﻩ}个人收集整理勿做商业用途ﻩ/***返回根节点ﻩ＊ﻩ*@reｔｕｒnﻩ　*/@SupｐｒeｓsWarnings("uncｈecked"）pubｌic　ＴgｅｔRoｏｔ()　{ﻩﻩrｅtｕrn（T)datas［0];}ﻩ/＊＊　*返回指定节点的父节点*@reｔurnﻩ　＊/ﻩ@SupｐreｓｓWａrninｇｓ(＂ｕnchecked")ﻩpｕblicTgeｔParent（iｎt　iｎdex)｛

10、ﻩif(iｎｄex　>ａｒraySize

11、｜　datas[index]==ｎuｌｌ）{ﻩﻩtｈｒｏwnewRuｎtiｍeＥxcｅptioｎ（"标记无效＂);ﻩ}ﻩﻩif(datａｓ[(ｉndｅx-　1)/2］==nuｌｌ)｛ﻩﻩｔhrownewRuntimeExｃeption("无父节点")；ﻩ}ﻩｒeturn（T)datas[(