《数据结构》 (java版) 课件 6树和森林的存储和遍历

一、双亲表示法二、链式表示法三、邻接表树的存储结构四、二叉链表(孩子兄弟表示法)顺序存储-双亲法ABCDEFGdata-1000225parentABCDEFG0123456顺序存储-双亲法双亲法实际上是根据数组元素的下标找下一个数据，下标就是链表的next有多条链：B->AE->C->AC->A....ABCDEFGpublic

classNode<T>{ Tdata;

intparent;}data-1000225parentABCDEFG0123456用数组实现的链表heada1a2a0a0a1a224-1012345下标数据下一个数据的位置head=0树的链式存储a.结点同构b.结点异构树的每个结点的子树数不一样，如何设计结构？链式存储如何描述节点有可变个引用，java和c有不同的表达方式public

classNode<T>{ Tdata; Node<?>[]subtrees;

publicNode(Tdata,int

m){

this.data=data;

subtrees=newNode<?>[m]; }}

struct

Node{

int

data;

struct

Node*subtrees[]; };

struct

Node*p=(struct

Node*)malloc(sizeof(struct

Node)+sizeof(struct

Node*)*3);

struct

Node*q=(struct

Node*)malloc(sizeof(struct

Node)); q->data=100; p->data=200; p->subtrees[0]=q;

printf("%d\n",p->data);

printf("%d\n",p->subtrees[0]->data);

free(q);

free(p);ABCDEFGBCEFGADrootABCDEFG二叉链表-孩子兄弟表示法ABCDEFGroot=0n=7data123firstchild456顺序＋链式存储：邻接表ABCDEFG0123456孩子链表：找孩子方便，如何找双亲？ABCDEFGroot=0n=7Parent0A1B2C3D4E5F6G123-1000225456datafirstchild顺序＋链式存储：邻接表树的存储课堂练习ABCDEFGHIJKABCDEFGHIJABCDEFGHIJ森林=>二叉树ABCDEFGHIJABCDEFGHIJGIJHBCDAEF森林=>二叉树GIJHBCDAEFABCDEFGHIJ二叉树=>森林ABCDEFGHIJABCDEFGHIJ二叉树=>森林ACBEFDGHIJK森林=>二叉树课堂练习树和森林的遍历一、树的遍历二、森林的遍历三、树的遍历的应用树的先根遍历若树不空，则先访问根结点，然后依次（？）先根遍历各棵子树。ABCDEFGHIJKABCDEFGHIJKABEFCDGHIJK先根遍历序列为：课堂练习BCDEFHAGJKABCDEFGHIJK树的后根遍历若树不空，则先依次后根遍历各棵子树，然后访问根结点。ABCDEFGHIJKAEFBCIJKHGD后根遍历序列为：课堂练习BCDEFHAGJKABCDEFGHIJK树的层次遍历若树不空，则自上而下自左至右访问树中每个结点。ABCDEFGHIJKABCDEFG按层次遍历序列为：HIJK树的先根遍历和二叉树遍历的对应关系BCDEFGABCEDGFA结论：先根对应先序先根遍历ABEFCDGBCDEFGABCEDGFA后根遍历EFBCGDA结论：后根对应中序树的后根遍历和二叉树遍历的对应关系BEFFECDGHIJKIKJHGDC森林的遍历1.森林中第一棵树的根点；2.森林中第一棵树的子森林；3.森林中其它树构成的森林。森林可以分解成三部分：B森林的先序遍历若森林不空，则1）访问森林中第一棵树的根结点;依次从左至右对森林中的每一棵树进行先根遍历。2）先序遍历森林中第一棵树的子树森林;3）先序遍历森林中(除第一棵树之外)其余树构成的森林。ABDCEGFHIJKABCDEFGHIJK先序遍历序列为：ABCDEFGHIKJ森林的先序遍历ABDCEGFHIJK森林对应的二叉链表ABDCEGFHIJK课堂练习ACBEFDGHIJK森林的中序遍历森林不空，则中序遍历森林中第一棵树的子树森林依次从左至右对森林中的每一棵树进行后根遍历。访问森林中第一棵树的根结点中序遍历森林中(除第一棵树之外)其余树构成的森林中序遍历序列为：ABCEDGFKIJH森林的中序遍历ABDCEGFHIJKABCDEFGHIJKABDCEGFHIJKABDCEGFHIJK课堂练习ACBEFDGHIJK遍历的对应关系先根遍历后根遍历树二叉树森林先序遍历先序遍历中序遍历中序遍历求树的深度BCDEFGA1、如果为空，则树的深度为02、否则，求出每棵子树的深度3、从所有子树的深度中取最大，然后加1，即为树的深度。intDepth(TreeT){//只考虑逻辑结构if(!T)return(0);for(p=T1,T2,…Tn){//每棵子树d[p]=Depth(p)a=max(d[1],d[2],…d[n])return(a+1)}求树的深度BCDEFGABCEDGFA求树的深度AG∧∧D∧C∧BE∧D∧∧逻辑结构存储结构求树的深度

//树以二叉链表存储，求树的深度

public

inttreeDepth(){

returntreeDepth(root); }

private

inttreeDepth(Node<T>t){

if(t==null)

return0;

int

depth=0; Node<T>child=t.left;

while(child!=null){

int

cdepth=treeDepth(child);

depth=depth<cdepth?cdepth:depth;

child=child.right; }

return

depth+1; }求树的深度

//树以二叉链表存储，求树的深度

public

inttreeDepth(){

returntreeDepth(root); }

private

inttreeDepth(Node<T>t){

if(t==null)

return0;

int

depth=0; Node<T>child=t.left;

while(child!=null){

int

cdepth=treeDepth(child);

depth=depth<cdepth?cdepth:depth;

child=child.right; }

return

depth+1; }求树的深度

//利用树的后序遍历等同于对应的二叉树的中序遍历

//注意：方法的返回值是t和各右兄弟子树的最大深度

//由于树使用二叉链表存储时，根没有兄弟子树，所以，得到的是树的深度

private

inttreeDepth0(Node<T>t){

if(t==null)

return0;

int

left=treeDepth0(t.left);

int

depth=left+1;//这棵树的深度

int

right=treeDepth0(t.right);//各右兄弟子树的最大深度

return

depth<right?right:depth; }BCEDGFABCDEFGAABCDEFGHIJKABEABFACADGHIADGHJADGHK求根到所有叶子结点的路径左图的输出结果为：对树先根遍历(深度优先)，设立一个栈，保存先根遍历经过的结点T1、T为叶子结点，则栈中存放的是从根到T的父结点的路径2、将T压栈，栈中存放的是从根到T的路径3、递归访问T的子树4、将T出栈求根到所有叶子结点的路径BCDEFGABCEDGFA求根到所有叶子结点的路径

public

voidtreeRootToLeafPath(){

if(root==null)

return; Deque<Node<T>>stack=newLikedList<>(); treeRootToLeafPath(root,stack); }求根到所有叶子结点的路径

public

voidtreeRootToLeafPath(Node<T>t,Deque<Node<T>>stack){

if(t.left==null){//叶子结点，打印栈中的数据

for(Node<T>p:stack) System.out.print(p.data+""); System.out.println(t.data);

return; }

stack.offerLast(t);//Deque默认的栈是head端，这里使用tail端的栈 Node<T>child=t.left;

while(child!=null){//先根遍历各子树 treeRootToLeafPath(child,stack);

child=child.right; }

stack.pollLast();//回溯，返回父结点，记得出栈 }求根到所有叶子结点的路径

//利用树的先序遍历等同于对应的二叉树的先序遍历

public

voidtreeRootToLeafPath0(Node<T>t,Deque<Node<T>>stack){

if(t==null)

return;

stack.offerLast(t);

if(t.left==null){//叶子结点，打印栈中的数据

for(Node<T>p:stack) System.out.print(p.data+""); System.out.println();

stack.pollLast(); }//前面t.left==null后，会多调用遍历左子树，但是保持了先序遍历的模式 treeRootToLeafPath(t.left,stack); treeRootToLeafPath(t.right,stack); }求根到所有叶子结点的路径

public

voidtreeRootToLeafPathNonRecursively(){//非递归,先根遍历的次序

if(root==null)

return; Deque<Node<T>>stack=newLinkedList<>(); Node<T>cur=root;

for(;;){//处理每一棵树

while(cur.left!=null){//一直往左，找到cur最左边的叶子结点

stack.offerLast(cur);

cur=cur.left; }

for(Node<T>p:stack)//输出叶子结点 System.out.print(p.data+""); System.out.println(cur.data);

while(cur.right==null){//没有兄弟结点，回溯到父结点

if(stack.isEmpty())

return;

cur=stack.pollLast(); }

cur=cur.right;//处理cur的兄弟结点 } }求根到所有叶子结点的路径

public

voidtreeRootToLeafPath1(){

classPath{ Deque<Node<T>>stack=newArrayDeque<>();

publ