数据结构树的讲解.pptx

6．4树和森林

6.4.1树的存储结构一、双亲表示法（顺序存储）//-----------树的双亲表存储表示----------//#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;//双亲位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}PTree;

双亲表示法举例RADEFCBGKHR-1A0B0C0D1E1F3G6H6K60123456789数组下标:*便于涉及双亲的操作；*求结点的孩子时需要遍历整棵树。

6.4.1树的存储结构

二、孩子表示法（顺序存储）#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intchild1;//第1个孩子位置域intchild2;//第2个孩子位置域......intchildd;//第d个孩子位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}PTree;

孩子表示法举例RADEFCBGKH0123456789数组下标:*便于涉及孩子的操作；求双亲不方便；*采用同构的结点，空间浪费。R1A4B0C6D0E0F7G0H0K023500000000089000000

孩子链表存储表示（链式存储）typedefstructCTNode{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根的位置}CTree;

孩子链表存储表示举例RADEFCBGKH0123456789数组下标:*便于涉及孩子的操作；*求结点的双亲时不方便。RAB/CD/E/FG/H/K/123/45/6/789/T.nodes[];T.n=10;T.r=0;

例1:设树T以孩子链表为存储结构,

寻找值为x的双亲结点的算法如下:Statusparent(CtreeT,TElemTypex){//当值为x的结点不存在时返回-2;//当值为x的结点为根结点时返回-1,//否则返回x结点的双亲结点的下标值.if(T.nodes[T.r].data==x)return–1;