《二叉树的基本知识.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 的结点一一对应。,二叉树的
3、五种基本形态：,N,L,R,L,R,空树,只含根结点,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, Vis
4、it() ) / 遍历,InitTree(&T) / 初始化置空树,插入类：,CreateTree(&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 ： 深度为
5、 k 的二叉树上至多含 2k-1 个结点（k1） 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,。,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 性质 5 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 i/2 的结点为其双亲结点; (2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点
6、， 否则，编号为2i+1 的结点为其右孩子结点,二叉树的存储结构,二、二叉树的链式 存储表示,一、 二叉树的顺序 存储表示,#define MAX_TREE_SIZE 100 / 设二叉树的最大结点数 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. 二叉
7、链表,typedef struct / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,结点结构:,C 语言的类型描述如下:,root,2三叉链表,结点结构:,typedef struct / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,结点结构:,C 语言的类型描述如下:,结点结构:,3双亲链表,
8、LRTag,L R R R L,n = 6,typedef struct / 结点结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct / 树结构 BPTNode nodesMAX_NODE_SIZE; int num_node; / 树中含结点数目 int root; / 根结点的位置 BPTree,树的三种存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟） 存储表示法,r=0 n=6,data parent,一、双亲表示法:,typedef s
9、truct PTNode Elem data; int parent; / 双亲位置域 PTNode;,#define MAX_TREE_SIZE 100,结点结构:,C语言的类型描述:,typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;,树结构:,r=0 n=6,data firstchild,二、孩子链表表示法:,-1 0 0 0 2 2 4,parent,typedef struct CTNode int child; struct CTNode *nextchild; *ChildPtr;,
10、孩子结点结构:,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语言的类型描述:,结点结构:,谢谢！,