数据结构与算法分析第5讲 树与二叉树.ppt
Chapter5
TreeBinaryTree;树的类型定义;数据对象D：;;结点;(从根到结点的)路径;结点的层次;任何一棵非空树是一个二元组
Tree=（root，F）
其中root被称为根结点
F被称为子树森林;(１)有确定的根
(２)树根和子树根之间为有向关系;对比树型结构和线性结构的结构特点;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;基本操作：;Root(T)//求树的根结点;InitTree(T)//初始化置空树;ClearTree(T)//将树清空;二叉树的类型定义
;二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成;二叉树的五种基本形态;二叉树的主要基本操作;
Root(T)Value(T,e)Parent(T,e)
LeftChild(T,e)RightChild(T,e)
LeftSibling(T,e)RightSibling(T,e)
BiTreeEmpty(T)BiTreeDepth(T);PreOrderTraverse(T,Visit())
InOrderTraverse(T,Visit())
PostOrderTraverse(T,Visit())
LevelOrderTraverse(T,Visit());
InitBiTree(T)
Assign(T,e,value)
CreateBiTree(T,definition)
InsertChild(T,p,LR,c);
ClearBiTree(T)
DestroyBiTree(T)
DeleteChild(T,p,LR);二叉树
的重要特性;性质1：
在二叉树的第i层上至多有2i-1个结点。(i≥1);性质2：
深度为k的二叉树上至多含2k-1个结点（k≥1）。;性质3：
对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。;两类特殊的二叉树：;性质4：
具有n个结点的完全二叉树的深度为?log2n?+1。;性质5：;二叉树的存储结构;#defineMAX_TREE_SIZE100
//二叉树的最大结点数
typedefTElemTypeSqBiTree[MAX_
TREE_SIZE];
//0号单元存储根结点
SqBiTreebt;;完全二叉树的一般二叉树的
数组表示数组表示;A;单支树;A;typedefstructBiTNode{//结点结构
TElemTypedata;
structBiTNode*lchild,*rchild;
//左右孩子指针
}BiTNode,*BiTree;;链表表示;A;typedefstructTriTNode{//结点结构
TElemTypedata;
structTriTNode*lchild,*rchild;
//左右孩子指针
structTriTNode*parent;//双亲指针
}TriTNode,*TriTree;;二叉链表的静态结构;
二叉树遍历
(BinaryTreeTraversal);顺着某一条搜索路径巡访二叉树
中的结点，使得每个结点均被访问一
次，而且仅被访问一次;“遍历”是任何类型均有的操作，
对线性结构而言，只有一条搜索路
径(因为每个结点均只有一个后继)，
故不需要另加讨论。而二叉树是非
线性结构，每个结点有两个后继，
则存在如何遍历即按什么样的搜索
路径遍历的问题;对“二叉树”而言，可以有三条搜索路径;设访问根结点记作V
遍历根的左子树记作L
遍历根的右子树记作R