数据结构二叉树的存储结构和遍历-课件

二叉树的存储结构和遍历二叉树的遍历二叉树的存储结构小结和作业顺序存储二叉链表三叉链表链式存储问题的提出递归遍历算法遍历的应用实例二叉树的顺序存储顺序存储是用一组连续的存储单元存放数据顺序存储要求数据是线性结构二叉树是非线性结构如何把二叉树转换为线性结构，而且保持结点之间的父/子关系?二叉树的顺序存储ACGBDEFKLHJIMNO123456789101112131415满二叉树：从上到下，从左往右依次编号二叉树的顺序存储

0123456789101112131415数组的下标，也是结点的编号

0123456789101112131415ABCEFDGHIJKLMNO二叉树的顺序存储ACGBDEFHJI12345678910完全二叉树：从上到下，从左往右依次编号

012345678910ABCEFDGHIJ二叉树的顺序存储ABDCEF一般的二叉树：想象成一个完全二叉树ABDCEF00000000二叉树的顺序存储ABDCEF000000001234567891011121314二叉树的顺序存储ABDCEF1253714

01234567891011121314ABCDEF

0123456789101112131411110010000001如何知道有无数据？#defineMAX_TREE_SIZE100

//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//1号单元存储根结点SqBiTreebt;二叉树的顺序存储#defineMAX_TREE_SIZE100

//二叉树的最大结点数typedefstruct{TElemTypedata[MAX_TREE_SIZE];

charflag[MAX_TREE_SIZE];}

SqBiTree;二叉树的顺序存储适用于一般的二叉树链式存储—二叉链表lchilddatarchild二叉链表的结点结构:左指针域，指向当前结点的左子树数据域，存储当前结点的取值信息右指针域，指向当前结点的右子树指向二叉树根结点头指针：前述二叉树的二叉链表如下所示：AF∧∧E∧C∧D∧∧B∧root链式存储—二叉链表a1a2a3LABDCEF1253714typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针

}BiTNode,*BiTree;lchilddatarchild结点结构:二叉链表的C语言类型描述如下:左指针域数据域右指针域链式存储—二叉链表parent

lchilddatarchild三叉链表的结点结构:指向双亲结点的指针域左指针域数据域右指针域链式存储—三叉链表rootAEF∧∧∧D∧∧C∧B∧∧二叉树的三叉链表表示：链式存储—三叉链表

typedefstructTriTNode{TElemTypedata;structTriTNode*lchild,*rchild;structTriTNode*parent;}TriTNode,*TriTree;三叉链表的C语言类型描述如下:parent

lchilddatarchild结点结构://结点结构//左右孩子指针//双亲指针链式存储—三叉链表问题的提出

在实际应用中，经常需要在二叉树中查找具有某些特征的结点，或者对树中的全部结点逐一进行某种处理，这就提出了二叉树的遍历的问题。问题的提出

定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。作用：遍历的目的是线性化，使二叉树中的结点能够按照某种次序排列在一个线性队列上，便于处理。问题的提出

线性结构的遍历：因为每个结点均只有一个后继，所以只有一条搜索路径。二叉树的遍历：二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。问题的提出二叉树存在下述三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；DLR，LDR，LRD3．先右（子树）后左（子树）的遍历。DRL，RDL，RLD先序（根）遍历左子树右子树根根左子树右子树

若二叉树为空树，则空操作；否则，（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树先序（根）遍历ABCDEFGHKABCDEFGHKABCDEFGHK课堂练习ABDCEFABC写出先序遍历的结果voidPreorder(BiTreeT,void(*visit)(TElemType&e)){//

先序遍历二叉树

1if(!T)return; 2visit(T->data);//访问根结点 3Preorder(T->lchild,visit);//遍历左子树 4Preorder(T->rchild,visit);//遍历右子树

}先序遍历中序（根）遍历左子树右子树根根左子树右子树

若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树中序（根）遍历ABCDEFGHKABCDEFGHKABDCEHGKF中序遍历voidInorder(BiTreeT,void(*visit)(TElemType&e)){//

中序遍历二叉树

1if(!T)return; 2Inorder(T->lchild,visit);//遍历左子树 3visit(T->data);//访问结点 4Inorder(T->rchild,visit);//遍历右子树}后序（根）遍历左子树右子树根根左子树右子树

若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后序（根）遍历ABCDEFGHKABCDEFGHKADCBHKGFEvoidPostorder(BiTreeT,void(*visit)(TElemType&e)){//

后序遍历二叉树

1if(!T)return; 2Postorder(T->lchild,visit);//遍历左子树 3Postorder(T->rchild,visit);//遍历右子树 4visit(T->data);//访问结点}后序遍历课堂练习写出三种遍历的结果ABECDABCDEFGHK先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A三种遍历的比较1、如果不考虑visit，三种遍历的算法在结构上是一样的，因此，压栈和出栈的过程相同。三种遍历的比较2、三种遍历的执行过程是不一样的（visit的位置不一样）。3、由前序序列和中序序列，或者后序和中序序列可以唯一确定一颗二叉树ABCDEFGHK先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A三种遍历的比较3、复制二叉树4、建立二叉树2、查询二叉树中某个结点应用举例1、统计二叉树中结点的个数遍历访问了每个结点一次且仅一次设置一个全局变量count=0统计二叉树中结点的个数将visit改为:count++统计二叉树中结点的个数voidPreOrder

(BiTreeT){}if(!T)return;count++;Preorder(T->lchild);Preorder(T->rchild);voidPreorder(BiTreeT,void(*visit)(TElemType&e)){//

先序遍历二叉树

1if(!T)return; 2visit(T->data);//访问结点 3Preorder(T->lchild,visit);//遍历左子树 4Preorder(T->rchild,visit);//遍历右子树

}统计二叉树中结点的个数intcount=0;main()PreOrder(T);printf(”%d”,count);}{递归思想:如果是空树，返回0统计二叉树中结点的个数求出左子树的结点的个数m求出右子树的结点的个数n返回m+n+1统计二叉树中结点的个数int

CountNode(BiTreeT){//返回指针T所指二叉树中所有叶子结点个数}if(!T)return0;//空树m=CountNode(T->lchild);n=

CountNode(T->rchild);return(m+n+1);求二叉树的深度课堂练习：空树的深度为0，求二叉树的深度intDepth(BiTreeT){//

返回二叉树的深度}if(!T)return(0);depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);returndepthval;查询二叉树中的某个结点给定指向二叉树的根结点的指针T和x，在T中查找数据元素的值等于x的结点，如果找到，则返回一个指针，指向这个结点，否则，返回空指针。ABECDTX="C"查询二叉树中的某个结点1.在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回指向根结点的指针2.否则在左子树中进行查找,若找到,则返回指针3.否则继续在右子树中进行查找,若找到,则返回指针,否则返回空指针查询二叉树中的某个结点BiTreeSearch(BiTreeT,TElemTypex)

{}if(!T)return(NULL);if(T->data==x)return(T)；

if(p)//返回值不是空指针，则表示x在左子树中 return(p);else

return(Search(T->rchild,x))

;p=Search(T->lchild,x);复制二叉树(练习)给定一棵二叉树，T指向其根结点，复制一棵二叉树，返回一个指向新树根结点的指针根元素T右子树根元素NEWT左子树右子树左子树复制二叉树1、如果T为空，则返回空指针2、复制根结点，p指向新结点3、复制左子树，pl指向左子树的根4、复制右子树，pr指向右子树的根5、p->lchid=pl，p->rchild=pr6、返回p复制二叉树BitreeCopy(BitTreeT){if(!T)return(NULL);p=newBiNode;p->data=T->datapl=Copy(T->lchild);pr=Copy(T->rchild);p->lchild=pl;p->rchild=pr;return(p);}以下列字符串表示ABC

D

建立二叉树以字符串的形式“根左子树右子树”定义一棵二叉树以空白字符“”表示1）空树2）只含一个根结点的二叉树A以字符串