镇江企业网站排名优化,怎么创建一个网站,城乡建设部网站广州市,如何做wap网站树 #x1f388;1.树和二叉树#x1f388;2.树#x1f52d;2.1树的定义#x1f52d;2.2树的4种表示方法#x1f52d;2.3树的基本术语#x1f52d;2.4树的抽象数据类型定义 #x1f388;3.二叉树#x1f52d;3.1二叉树的定义#x1f52d;3.2二叉树的抽象数据类型定义1.树和二叉树2.树2.1树的定义2.2树的4种表示方法2.3树的基本术语2.4树的抽象数据类型定义 3.二叉树3.1二叉树的定义3.2二叉树的抽象数据类型定义3.3满二叉树3.4完全二叉树3.5完全二叉树的特点3.6二叉树的性质3.7二叉树的存储结构3.8完全二叉树的顺序存储3.9一般二叉树的存储结构3.10二叉树的链式存储结构 4.二叉树的类定义及其实现4.1二叉树的类定义4.2二叉树的实现4.2.1创建二叉树4.2.2计算二叉树的高度4.2.3计算二叉树的树叶数4.2.4查找二叉树 1.树和二叉树 树结构是一类重要的非线性结构树型结构是结点之间有分支并且具有明显的层次关系的结构它类似于自然界中的树。树结构在客观世界是大量存在的例如行政组织机构和人类社会的家谱都可以用树来形象表示。 2.树
2.1树的定义 树是n(n0)个结点的有限集T。 若n0称为空树。 若n0则它满足以下两个条件 1.有且仅有一个特定的称为根的结点。 2.其余结点可以分为mm0个互不相交的有限集T1,T2,T3......Tm,其中每个集合本身又是一棵树并称为根的子树。 2.2树的4种表示方法 2.3树的基本术语 结点树中每个元素对应一个结点。每个结点包含一个数据元素及若干指向子树的分支。例如图中的树有11个结点结点D包含3个分支。结点的度结点所拥有的子树的个数称为结点的度。例如结点A和D的度均为3结点B的度为2结点C的度为1结点F的度为0。叶子结点度为0的结点称为叶子结点或称树叶又称终端结点。例如上图所示E,F,G,H,I,K都是叶子结点。分支结点度不为0的结点称为分支结点又称非终端结点。例如上图所示的树A,B,C,D,J都是分支结点。树的度树中所有结点的最大度数称为树的度。例如图所示的树的度为3.双亲结点若结点X有孩子则X为孩子的双亲结点简称双亲。例如在图所示的树中结点H,I,J的双亲是D,根结点A没有双亲树中只有根结点没有双亲。孩子结点若结点X由子树则子树的根结点即为结点X的孩子结点简称孩子。例如结点D有三个孩子H,I,J。兄弟结点同一双亲的孩子结点称为兄弟结点简称兄弟。例如结点H,I,J为兄弟。堂兄弟结点在树中的层次相同但双亲不同的结点称为堂兄弟简称堂兄。例如结点F,G,H为堂兄弟。祖先结点从根结点到结点X所经过分支上的所有结点都称为X的祖先结点简称祖先。例如K的祖先为A,D,J子孙结点结点X的孩子以及这些孩子的孩子都是X的子孙结点。例如结点D的子孙为H,I,J,K结点的层次根结点的层次为1根结点的孩子的层次为2根结点的孩子的孩子的层次为3依次类推。树的深度树中结点的最大层次称为树的深度也称树高。空树的深度为0只有一个根结点的树的深度为1图所示的树的深度为4.路径从树的某个结点X到其子孙结点Y所经过的路线叫做路径路径上经过的边的数称为路径长度。由于树中无回路所以树的路径是唯一的。如图所示的树中从A到结点K的路径是A,D,J,K,路径长度为3.森林m(m)棵互不相交的树构成的集合称之为森林。
2.4树的抽象数据类型定义
ADT Tree{
数据对象D:D为性质相同的数据元素的集合
数据关系R:
若D为空集则称为空树。
若D仅有一个数据元素则R空集否则R空集。
1.在D中存在唯一的称为根的数据元素root,它在关系R下无前驱。
2.存在D-{root}的一个划分{D1,D2,...,Dm}m0,且对于1im存在唯一的数据元素Xi属于Di,有(root,Xi)属于R.
3.对应于D-{root}的一个划分r-{(root,x1),(root,x2),...,(root,Xm)}存在唯一的一个划分{R1,R2,...,Rm}(m0),对于1im,Ri是Di上的二元关系xi,Rii1,2,...,m是一棵符合本定义的树称为根root的子树。基本操作
InitTree(t):构造一棵空树
DestroyTree(t):销毁一棵树
Parent(t,e):求结点e的双亲结点
Sons(t,e):求结点e有所有孩子结点
LeftChild(t,e):返回结点e的右兄弟最左孩子
RightSibling(t,e):返回结点e的右兄弟结点
TraraverseTree(t,visit()):以visit()函数访问树中每个结点
DepthTree(t):返回树的深度
}ADT Tree3.二叉树
3.1二叉树的定义 二叉树是由n(n0)个结点构成的有限集合该集合或者为空集此时称为空二叉树或由一个根结点及两棵互不相交的左右子树组成并且左右子树均是二叉树。二叉树的子树有左右之分其次序不能颠倒。 二叉树的定义也是一个递归定义二叉树可以是空集合根可以有空的左子树或空的右子树。。二叉树不是树的特殊情况它们是两个概念。二叉树中即使只有一棵子树也要进行区分说明它是左子树还是右子树这是二叉树与树的最主要的差别。“二叉树是结点度为2的树”的说法是错误的。二叉树的5种基本形态 3.2二叉树的抽象数据类型定义 3.3满二叉树 一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点是每一层上结点数都是最大结点数。如图所示是一棵深度为4的满二叉树。 3.4完全二叉树 可以对满二叉树的结点进行顺序编号约定编号从根结点开始自上而下从左至右称为层序编号。 如果一棵深度为k且具有n个结点的二叉树它的每个结点都与深度为k的满二叉树中的顺序编号1~n的结点一一对应则称这棵二叉树为完全二叉树。 3.5完全二叉树的特点
叶子结点只能在第k层和第k-1层上出现。对于任意结点若其右子树的深度为l,则其左子树的深度为l或l1。度为1的结点数为0或1。当结点的总数为奇数时度为1的结点数为0当结点的总数为偶数时度为1的结点数为1.
3.6二叉树的性质
二叉树的第i层上至多有2i-1i1个结点。深度为k的二叉树最多有2k-1k1个结点。对于任何一棵二叉树如果其叶子结点数为n0,度为2的结点数为n2则n0n21. 性质3推论对于任何一棵k叉树如果叶子结点数为n0度为1,2...k的结点数分别为n1,n2,...,nk,则n0n22n33n4...(k-1)nk1. 例一棵三叉树中已知度为3的结点数等于度为2的结点数且叶子结点数为10则度为3的结点为多少 n0 n22n313n31 n3 3 一棵具有n个结点的完全二叉树的深度为[log2n]1(以2为底n的对数)。
3.7二叉树的存储结构 二叉树的顺序存储结构是用一组地址连续的存储单元来存放二叉树的数据元素。 二叉树的顺序存储结构类型定义如下
#define MaxSize 100 //二叉树的最大存储容量
typedef ElemType SqBiTree[MaxSize] //用数组存储二叉树的数据元素
SqBiTree bt;3.8完全二叉树的顺序存储 在用数组存储二叉树时必须确定树中各数据元素的存放次序使各数据元素的相应位置反映出数据元素之间的逻辑关系用一组地址连续的存储单元依次自上而下、自左而右地存储完全二叉树的结点元素。 3.9一般二叉树的存储结构 在采用顺序存储时应采用完全二叉树的编号方式没有编号的结点在对应的位置上用#表示。 注对于完全二叉树而言采用顺序存储结构方式是十分合理的它能够充分利用存储空间但对于一般的二叉树而言这种存储方式必然会造成大量空间浪费。在最坏的情况下一棵深度为k且只有k个单分支二叉树却需要长度为2k-1的一维数组来存储。因此一般二叉树常采用链式存储方式。 3.10二叉树的链式存储结构 根据二叉树的定义二叉树的每个结点可以有两个分支分别指向及诶单的左子树和右子树。在二叉树中标准存储方式的结点结构如图所示 其中data表示数据域用来存放数据元素信息。 lchild表示左指针域用来存放指向左孩子的指针当左孩子不存在时为空指针。 rchild表示右指针域用来存放指向右孩子的指针当右孩子不存在时为空指针。 这种链式存储结构通常称为二叉链表。 二叉链表的结点类型定义:
typedef struct BitNode
{ElemType data;//数据元素信息BitNode *lchild;//指向左孩子结点BitNode *rchild;//指向右孩子结点
}BitNode;由二叉树的链式存储结构可知对于具有n个结点的二叉树每个结点有两个指针域共有2n个指针域其中n-1个非空链域n1个空链域。 4.二叉树的类定义及其实现
4.1二叉树的类定义
#include iostream
using namespace std;
typedef struct BitNode
{char data;BitNode* lchild;BitNode* rchild;
}BitNode;
class BiTree
{
private:BitNode* bt;void Rcreate(BitNode* t);//递归创建二叉树void PreTraverse(BitNode* t);//先序遍历递归函数void InTraverse(BitNode* t);//中序遍历递归函数void PostTraverse(BitNode* t);//后序遍历递归函数int BTNodeDepth(BitNode* t);//计算二叉树的树高递归函数int BTNodeLeaf(BitNode* t);//计算二叉树树叶数递归函数BitNode* SearchNode(BitNode* t, char x);//查找值等于x的结点递归函数
public:BiTree(){bt NULL;//创建空树}void RcreateBiTree();//创建二叉树void PreTraverseBiTree();//先序遍历二叉树void InTraverse();//中序遍历二叉树void PostTraverse();//后序遍历二叉树int BTNodeDepthBiTree();//计算二叉树的树高int BTNodeLeafBiTree();//计算二叉树的叶子数BitNode* SearchNodeBit(char x);//查找值等于x的结点
};4.2二叉树的实现
4.2.1创建二叉树 Rcreate()函数递归创建二叉树其过程为读入字符ch若ch.,则创建空二叉树若ch!.则先创建左子树再创建右子树。 void BiTree::Rcreate(BitNode* t)
{char ch;cin ch;if (ch .)t NULL;else{t new BitNode;//申请空间t-data ch;Rcreate(t-lchild);//递归创建左子树Rcreate(t-rchild);//递归创建右子树}
}
void BiTree::RcreateBiTree()
{BitNode* t;Rcreate(t);//递归创建二叉树bt t;//将根结点指针赋值给私有成员bt
}4.2.2计算二叉树的高度 BTNodeDepth()函数递归计算二叉树的树高其过程为判断二叉树t是否为空树若为空树树高则为0。若为非空树则计算左子树的高度m和右子树的高度n;mn,返回m否则返回n. int BiTree::BTNodeDepth(BitNode* t)
{if (t NULL)return 0;else{int m 1 BTNodeDepth(t-lchild);//计算左子树树高度int n 1 BTNodeDepth(t-rchild);//计算右子树树高度if (m n)//比较左右子树高度return m;elsereturn n;}
}
int BiTree::BTNodeDepthBiTree()
{//计算二叉树的高度BitNode* p bt;return BTNodeDepth(p);//调用计算二叉树高度的递归函数
}4.2.3计算二叉树的树叶数 BTNodeLeaf()计算二叉树的树叶数其过程为判断t是否为空树若为空树则树叶数为0若为非空树则计算左子树的树叶数m和右子树的树叶数nmn0时返回1mn!0时返回mn. int BiTree::BTNodeLeaf(BitNode* t)
{//递归算法计算二叉树的树叶数if (t NULL)return 0;else{int m BTNodeLeaf(t-lchild);//计算左子树的树叶数int n BTNodeLeaf(t-rchild);//计算右子树的树叶数if (m n 0)return 1;elsereturn m n;}
}
int BiTree::BTNodeLeafBiTree()
{//计算二叉树的树叶数BitNode* p bt;//读取私有成员指针btreturn BTNodeLeaf(p);//调用二叉树的树叶数的递归函数
}4.2.4查找二叉树 SearchNode()函数在二叉树t中查找值等于x的结点若找到该结点时返回其首地址否则返回NULL.判断t是否为空树若为空树则返回NULL若为非空树则在t-datax时返回t,在t-data!x时在左子树中查找否则在右子树中查找。 BitNode* BiTree::SearchNode(BitNode* t, char x)
{BitNode* p;if (t NULL)return NULL;if (t-data x)return t;else{p SearchNode(t-lchild,x);//递归查找左子树if (p ! NULL)return p;elsereturn SearchNode(t-rchild, x);//递归查找右子树}
}
BitNode* BiTree::SearchNodeBit(char x)
{BitNode* p bt;return SearchNode(p, x);
}好啦关于二叉树的知识到这里并没有结束后期会继续更新二叉树的相关知识欢迎大家持续关注、点赞和评论❤️❤️❤️
