《二叉树的基本知识.ppt》由会员分享，可在线阅读，更多相关《二叉树的基本知识.ppt（36页珍藏版）》请在三一办公上搜索。
1、树,SDUT_ACM 培训,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n1时，其余结点可分为m(m0)个互 不相交的有限集T1,T2,Tm,其中每一 棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系 R：,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,(从根到结点的)路径：,孩子结点、双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点,结点的层次:,树的深度：,由从根到该结点所经分支
2、和结点构成,假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,任何一棵非空树是一个二元组 Tree=（root，F）其中：root 被称为根结点，F 被称为子树森林,森林：,是 m（m0）棵互不相交的树的集合,A,root,F,二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,E,F,G,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,二叉树的五种基本形态：,N,L,R,L,R,空
3、树,只含根结点,N,N,N,右子树为空树,左子树为空树,左右子树均不为空树,二叉树的主要基本操作：,查 找 类,插 入 类,删 除 类,Root(T)/求树的根结点,查找类：,Value(T,cur_e)/求当前结点的元素值,Parent(T,cur_e)/求当前结点的双亲结点,LeftChild(T,cur_e)/求当前结点的最左孩子,RightSibling(T,cur_e)/求当前结点的右兄弟,TreeEmpty(T)/判定树是否为空树,TreeDepth(T)/求树的深度,TraverseTree(T,Visit()/遍历,InitTree(&T)/初始化置空树,插入类：,Create
4、Tree(&T,definition)/按定义构造树,Assign(T,cur_e,value)/给当前结点赋值,InsertChild(&T,&p,i,c)/将以c为根的树插入为结点p的第i棵子树,ClearTree(&T)/将树清空,删除类：,DestroyTree(&T)/销毁树的结构,DeleteChild(&T,&p,i)/删除结点p的第i棵子树,二叉树的重要特性,性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1)性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式
5、：n0=n2+1。,。,性质 4：具有 n 个结点的完全二叉树的深度为 log2n+1性质 5若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1)若 i=1，则该结点是二叉树的根，无双亲,否则，编号为 i/2 的结点为其双亲结点;(2)若 2in，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点,二叉树的存储结构,二、二叉树的链式 存储表示,一、二叉树的顺序 存储表示,#define MAX_TREE_SIZE 100/设二叉
6、树的最大结点数typedef struct ElemType*data;/初始化时分配存储空间 int nodeNum;/二叉树中的结点数目SqBiTree;,一、二叉树的顺序存储表示,/0号单元存储根结点,例如:,A B D,1,4,0,13,2,6,(k+1)2-1=2k+1,C,E,F,二、二叉树的链式存储表示,1.二叉链表,2三叉链表,3双亲链表,root,结点结构:,1.二叉链表,typedef struct/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,结点结构:,C 语言的类型
7、描述如下:,root,2三叉链表,结点结构:,typedef struct/结点结构 TElemType data;struct TriTNode*lchild,*rchild;/左右孩子指针 struct TriTNode*parent;/双亲指针 TriTNode,*TriTree;,结点结构:,C 语言的类型描述如下:,结点结构:,3双亲链表,LRTag,LRRRL,n=6,typedef struct/结点结构 TElemType data;int*parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNode typedef struct/树结构 BPTNo
8、de nodesMAX_NODE_SIZE;int num_node;/树中含结点数目 int root;/根结点的位置 BPTree,树的三种存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟）存储表示法,r=0n=6,data parent,一、双亲表示法:,typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;,#define MAX_TREE_SIZE 100,结点结构:,C语言的类型描述:,typedef struct PTNode nodes MAX_TREE_SIZE;int r,n;/根结点的位
9、置和结点个数 PTree;,树结构:,r=0n=6,data firstchild,二、孩子链表表示法:,-1 0 0 0 2 2 4,parent,typedef struct CTNode int child;struct CTNode*nextchild;*ChildPtr;,孩子结点结构:,C语言的类型描述:,typedef struct Elem data;ChildPtr firstchild;/孩子链的头指针 CTBox;,双亲结点结构,typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;,树结构:,root,三、树的二叉链表(孩子-兄弟）存储表示法,root,typedef struct CSNode Elem data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,C语言的类型描述:,结点结构:,谢谢！,
