二叉树基础知识

1.二叉树的基础操作

#include#include#include#define Max 20 //结点的最大个数typedef struct node{char data;struct node *lchild,*rchild;}BinTNode; //自定义二叉树的结点类型typedef BinTNode *BinTree; //定义二叉树的指针int NodeNum,leaf; //NodeNum为结点数,leaf为叶子数//基于先序遍历算法创建二叉树//要求输入先序序列,其中加入虚结点"#"以示空指针的位置BinTree CreatBinTree(void){BinTree T;char ch;if((ch=getchar())=='#')return(NULL); //读入#,返回空指针else{T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点T->data=ch;T->lchild=CreatBinTree(); //构造左子树T->rchild=CreatBinTree(); //构造右子树return(T);}}//先序遍历void Preorder(BinTree T){if(T){printf("%c",T->data); //访问结点Preorder(T->lchild); //先序遍历左子树Preorder(T->rchild); //先序遍历右子树}}//中序遍历void Inorder(BinTree T){if(T){Inorder(T->lchild); //中序遍历左子树printf("%c",T->data); //访问结点Inorder(T->rchild); //中序遍历右子树}}//后序遍历void Postorder(BinTree T){if(T){Postorder(T->lchild); //后序遍历左子树Postorder(T->rchild); //后序遍历右子树printf("%c",T->data); //访问结点}}//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法int TreeDepth(BinTree T){int hl,hr,max;if(T){hl=TreeDepth(T->lchild); //求左深度hr=TreeDepth(T->rchild); //求右深度max=hl>hr? hl:hr; //取左右深度的最大值NodeNum=NodeNum+1; //求结点数if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0,即为叶子。

return(max+1);}else return(0);}//主函数void main(){BinTree root;int i,depth;printf("\n");printf("Creat Bin_Tree; Input preorder:"); //输入完全二叉树的先序序列, // 用#代表虚结点,如ABD###CE##F##root=CreatBinTree(); //创建二叉树,返回根结点do{ //从菜单中选择遍历方式,输入序号。printf("\t********** select ************\n");printf("\t1: Preorder Traversal\n"); printf("\t2: Iorder Traversal\n");printf("\t3: Postorder traversal\n");printf("\t4: PostTreeDepth,Node number,Leaf number\n");printf("\t0: Exit\n");printf("\t*******************************\n");scanf("%d",&i); //输入菜单序号(0-4)switch (i){case 1: printf("Print Bin_tree Preorder: ");Preorder(root); //先序遍历break;case 2: printf("Print Bin_Tree Inorder: ");Inorder(root); //中序遍历break;case 3: printf("Print Bin_Tree Postorder: ");Postorder(root); //后序遍历break;case 4: depth=TreeDepth(root); //求树的深度及叶子数printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);printf(" BinTree Leaf number=%d",leaf);break;case 5: printf("LevePrint Bin_Tree: ");Levelorder(root); //按层次遍历break;default: exit(1);}printf("\n");}while(i!=0);}//按层遍历Levelorder( BinTNode *root){BinTNode * q[Max]; //定义BinTNode类型的队列 用于存放节点 队列长最大为20个元素int front=0,rear=0; //初始化队列为空BinTNode *p; //临时节点指针if(root!=NULL){ //将根节点进队 rear=(rear+1)%Max; q[rear]=root; } while(front!=rear){ front=(front+1)%Max; p=q[front]; //删除队首的元素 让两个节点(左右节点)孤立 printf("%c",p->data); //输出队列首元素的值 if(p->left!=null){ //如果存在左孩子节点,则左孩子节点进入队列 rear=(rear+1)%Max; q[rear]=p->left; } if(p->right!=null){ //如果存在右孩子节点,则右孩子节点进入队列 rear=(rear+1)%Max; q[rear]=p->right; } }}。

2.二叉树相关知识

二叉树 (binary tree) 是另一种树型结构,它的特点是每个结点至多只有二棵子 树 (即二叉树中不存在度大于 2的结点 ),并且,二叉树的子树有左右之分,其次序不能任意颠倒 . 二叉树是一种数据结构 : Binary_tree=(D,R) 其中: D是具有相同特性的数据元素的集合 ;若 D等于空 ,则 R等于空称为空的二叉树 ;若 D等于空则 R是 D上某个二元关系 H的集合,即 R={H},且 (1) D 中存在唯一的称为根的元素 r,它的关系 H下无前驱 ; (2) 若 D-{r}不等于空,则 D-{r}={Dl,Dr},且 Dl交 Dr等于空 ; (3) 若 Dl不等于空 ,则在 Dl中存在唯一的元素 xl,〈 r,xl〉属于 H,且存在 Dl上的关系 Hl属于 H; 若 Dr不等于空 ,则在 Dr中存在唯一的元素 xr,〈 r,xr〉 >属于 H, 且存 Dr上的关 系 Hr属于 H; H={r,xl, ,Hl, Hr}; (4) (Dl, Hl) 是一棵合本定义的二叉树,称为根 r的左子树 ,(Dr,Hr)是一棵符合定义的二叉树,称为根的右子树。

其中,图 6.2 是各种形态的二叉树 . (1) 为空二叉树 (2)只有一个根结点的二叉树 (3)右子树为空的二叉树 (4)左子树为空的二叉树 (5)完全二叉树 二叉树的基本操作: (1)INITIATE(BT ) 初始化操作。置 BT为空树。

(2)ROOT(BT)\ROOT(x) 求根函数。求二叉树 BT的根结点或求结点 x所在二叉树的根结点。

若 BT是空树或 x不在任何二叉树上,则函数值为 “空 ”。 (3)PARENT(BT,x) 求双亲函数。

求二叉树 BT中结点 x的双亲结点。若结点 x是二叉树 BT 的根结点 或二叉树 BT中无 x结点,则函数值为 “空 ”。

(4)LCHILD(BT,x) 和 RCHILD(BT,x) 求孩子结点函数。分别求二叉树 BT中结点 x的左孩 子和右孩子结点。

若结点 x为叶子结点或不在二叉树 BT中,则函数值为 “空 ”。 (5)LSIBLING(BT,x) 和 RSIBING(BT,x) 求兄弟函数。

分别求二叉树 BT中结点 x的左兄弟和右兄弟结点。 若结点 x是根结点或不在 BT中或是其双亲的左 /右子树根 ,则函树值 为 “空 ”。

(6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点 x为根,二叉树 LBT和 RBT分别为左, 右子树的二叉树。

(7)INS_LCHILD(BT,y,x) 和 INS_RCHILD(BT,x) 插入子树操作。将以结点 x为根且右子树为空的二叉树 分别置为二叉树 BT中结点 y的左子树和右子树。

若结点 y有左子树 /右子树,则插入后是结点 x的右子树。 (8)DEL_LCHILD(BT,x) 和 DEL-RCHILD(BT,x) 删除子树操作。

分别删除二叉树 BT中以结点 x为根的左子树或右子树。 若 x无左子树或右子树,则空操作。

(9)TRAVERSE(BT) 遍历操作。按某个次序依此访问二叉树中各个结点,并使每个结点只被访问一次。

(10)CLEAR(BT) 清除结构操作。将二叉树 BT置为空树。

5.2.2 二叉树的存储结构 一 、顺序存储结构 连续的存储单元存储二叉树的数据元素。例如图 6.4(b)的完全二叉树 , 可以向量 (一维数组 ) bt(1:6)作它的存储结构,将二叉树中编号为 i的结点的数据元素存放在分量 bt[i]中 ,如图 6.6(a) 所示。

但这种顺序存储结构仅适合于完全二叉树 ,而一般二叉树也按这种形式来存储 ,这将造成存 贮浪费。如和图 6.4(c)的二叉树相应的存储结构图 6.6(b)所示,图中以 “0”表示不存在此结点 . 二、链式存储结构 由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构成 ,则表 示二叉树的链表中的结点至少包含三个域 :数据域和左右指针域 ,如图 (b)所示。

有时 ,为了便于找 到结点的双亲 ,则还可在结点结构中增加一个指向其双亲受的指针域,如图 6.7(c)所示。 5.3 遍历二叉树 遍历二叉树 (traversing binary tree)的问题, 即如何按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。

其中常见的有三种情况:分别称之为先 (根 )序遍历,中 (根 )序遍历和后 (根 )序遍历。 5.3.1 前序遍历 前序遍历运算:即先访问根结点,再前序遍历左子树,最后再前序遍历右子树。

前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如: 按前序遍历此二叉树的结果为: Hello!How are you? proc preorder(bt:bitreprtr) if (bt<>null)[ print(bt^); preorder(bt^.lchild); preorder(bt^.rchild);] end; 5.3.2 中序遍历 中序遍历运算:即先中前序遍历左子树,然后再访问根结点,最后再中序遍历右子树。

中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如: 按中序遍历此二叉树的结果为: a*b-c proc inorder(bt:bitreprtr) if (bt<>null)[ inorder(bt^.lchild); print(bt^); niorder(bt^.rchild);] end; 5.3.3 后序遍历 后序遍历运算:即先后序遍历左子树,然后再后序遍历右子树,最后访问根结点。

后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如: 按后序遍历此二叉树的结果为: Welecome to use it! proc postorder(bt:bitreprtr) if (bt<>null)[ postorder(bt^.lchild); postorder(bt^.rchild);] print(bt^); end; 五、例: 1.用顺序存储方式建立一棵有31个结点的满二叉树,并对其进行先序遍历。

2.用链表存储方式建立一棵如图三、4所示的二叉树,并对其进行先序遍历。 3.给出一组数据:R={10.18,3,8,12,2,7,3},试编程序,先构造一棵二叉树,然后以中序遍历访问所得到的二叉树,并输出遍历结果。

3.关于二叉树的知识,急需高人解答

2 二叉树1.二叉树的基本形态: 二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态: (1)空二叉树——(a); (2)只有一个根结点的二叉树——(b); (3)只有右子树——(c); (4)只有左子树——(d); (5)完全二叉树——(e) 注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。

2.两个重要的概念: (1)完全二叉树——只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树; (2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。 3.二叉树的性质 (1) 在二叉树中,第i层的结点总数不超过2^(i-1); (2) 深度为h的二叉树最多有2^h-1个结点(h>=1),最少有h个结点; (3) 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2, 则N0=N2+1; (4) 具有n个结点的完全二叉树的深度为int(log2n)+1 (5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系: 若I为结点编号则 如果I<>1,则其父结点的编号为I/2; 如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子; 如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。

(6)给定N个节点,能构成h(N)种不同的二叉树。 h(N)为卡特兰数的第N项。

h(n)=C(n,2*n)/(n+1)。 4.二叉树的存储结构: (1)顺序存储方式 type node=record data:datatype l,r:integer; end; var tr:array[1..n] of node; (2)链表存储方式,如: type btree=^node; node=record data:datatye; lchild,rchild:btree; end; 5.普通树转换成二叉树:凡是兄弟就用线连起来,然后去掉父亲到儿子的连线,只留下父母到其第一个子女的连线。

二叉树很象一株倒悬着的树,从树根到大分枝、小分枝、直到叶子把数据联系起来,这种数据结构就叫做树结构,简称树。树中每个分叉点称为结点,起始结点称为树根,任意两个结点间的连接关系称为树枝,结点下面不再有分枝称为树叶。

结点的前趋结点称为该结点的"双亲",结点的后趋结点称为该结点的"子女"或"孩子",同一结点的"子女"之间互称"兄弟"。 二叉树:二叉树是一种十分重要的树型结构。

它的特点是,树中的每个结点最多只有两棵子树,即树中任何结点的度数不得大于2。二叉树的子树有左右之分,而且,子树的左右次序是重要的,即使在只有一棵子树的情况下,也应分清是左子树还是右子树。

定义:二叉树是结点的有限集合,这个集合或是空的,或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。 (三)完全二叉树 对满二叉树,从第一层的结点(即根)开始,由下而上,由左及右,按顺序结点编号,便得到满二叉树的一个顺序表示。

据此编号,完全二叉树定义如下:一棵具有n个结点,深度为K的二叉树,当且仅当所有结点对应于深度为K的满二叉树中编号由1至n的那些结点时,该二叉树便是完全二叉树。图4是一棵完全二叉树。

4.计算机二级公共基础知识完全二叉树

只有最下面的两层结点度能够小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

完全二叉树定义:

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

完全二叉树是由 满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

一棵二叉树至多只有最下面的一层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树。

完全二叉树特点:

叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;

出于简便起见,完全二叉树通常采用 数组而不是 链表存储,其 存储结构如下:

var tree:array[1..n]of longint;{n:integer;n>=1}

5.计算机二级公共基础知识完全二叉树

首先得知道什么是完全二叉树,完全二叉树是除最下面一层外,每一层的结点数均达到最大值,在最下面一层上只缺少右边的若干结点。(注意和满二叉树的区分)

下图就是一个完全二叉树。

根据二叉树的性质,在任意一个二叉树中,度为0的结点(叶子结点)总是比度为2的结点多一个。如图中,6、7、8、9、10为叶子结点,共5个;度为2的结点有1、2、3、4,共4个。

根据完全二叉树的特征可以推断出,在完全二叉树中,最多就有一个度为1的结点。此外,如果完全二叉树共有偶数个结点,则其中有一个度为1的结点;如果完全二叉树共有奇数个结点,则它只有度为2和度为0的结点,没有度为1的结点。

所以,如果完全二叉树的总结点数为偶数,则:度为2的结点+度为1的结点=度为0的结点,如果完全二叉树的总结点数为奇数,则:度为2的结点+1=度为0的结点

上面的都是推导过程,以下是结论。推导过程可以理解一下,结论最好记住。

因此对于完全二叉树而言,如果他的结点个数为偶数N,则该二叉树中,叶子结点个数=非叶子结点个数=N/2。

如果他的结点个数为奇数M,则该二叉树中,叶子结点个数=非叶子结点个数+1=(M+1)/2。

本题中,二叉树共有700个结点,是偶数,所以叶子结点数=700/2=350。

二叉树基础知识

转载请注明出处生活知识网 » 二叉树基础知识

资讯

公共基础知识财务题库

阅读(27)

本文主要为您介绍公共基础知识财务题库,内容包括。2008年福建会计从业资格考试《财经法规与会计职业道德》答案 一.单选 1。D 取鲜摆绞肢悸扮溪堡娄2。A 3。B 4。C 5。C 6。

资讯

电气相关基础知识

阅读(26)

本文主要为您介绍电气相关基础知识,内容包括电气安全基础知识内容呢?,电气基本知识?,电气自动化基础知识。电力行业,电气工程及其自动化专业名词解释: 三相交流电:由三个频率相同、电势振幅相等、相位差互差120°角的交流电路组成的电力系统,叫

资讯

卫生专业基础知识药学

阅读(23)

本文主要为您介绍卫生专业基础知识药学,内容包括什么是医药卫生专业基础知识,医药卫生专业基础知识包括哪些内容,医疗卫生系统考试药学专业考什么哪些科目。医药卫生专业基础知识一般包括生理、生化、解剖、药理、病理、诊断、伦理学等。医

资讯

内科护士常见基础知识

阅读(27)

本文主要为您介绍内科护士常见基础知识,内容包括护理基础知识1000题的内容简介,护士必须知道的常识?,内科护理学常考哪些重点。《护理基础知识1000题》参照普通高等教育“九·五”、“十一五”国家规划教材《基础护理学》、《外科护理学》

资讯

网络安全工程师基础知识

阅读(26)

本文主要为您介绍网络安全工程师基础知识,内容包括网络安全工程师要学些什么?,成为网络安全工程师,初期必须掌握的知识,网络安全工程师主要做些什么,要具备什么技能?。您好,网络安全工程师学习内容:计算机应用、计算机网络、通信、信息安全等

资讯

文笔和编导的基础知识

阅读(28)

本文主要为您介绍文笔和编导的基础知识,内容包括编导的文学常识,关于编导,编导的基础知识有那些??。第一部分 考试环节及科目 考试环节 广播电视编导专业术科考试由笔试和面试两个环节组成,满分300分,其中笔试满分160分,面试满分140

资讯

安全生产基础知识论文

阅读(28)

本文主要为您介绍安全生产基础知识论文,内容包括企业安全方面论文,论文内容:围绕着“认真贯彻《安全许可证条例》,积极开展安全生产,关于安全的论文160字。加强特种作业人员培训工作的重要意义的思考 特种作业人员培训的特殊性决定着必须对

资讯

基础乐理知识ppt

阅读(27)

本文主要为您介绍基础乐理知识ppt,内容包括音乐基本知识资料,基本的乐理知识,乐理基本知识。和语言一样,不同民族都有过自己创立并传承下来的记录音乐的方式---记谱法。各民族的记谱方式各有千秋,但是目前被更广泛使用的是五线谱和简谱

资讯

放射技士基础知识点

阅读(29)

本文主要为您介绍放射技士基础知识点,内容包括。计算机X线摄影 CR computed radiography数字X线摄影 DR digital radiography直接数字X线摄影

资讯

农村农业基础知识题库

阅读(26)

本文主要为您介绍农村农业基础知识题库,内容包括。试题答案: (1)追根溯源:水稻、粟 (2)历史回眸:①春秋时期,由于铁农具和牛耕技术的使用和推广,极大地促进了农业的发展; ②唐朝,农

资讯

金融基础知识课后答案

阅读(25)

本文主要为您介绍金融基础知识课后答案,内容包括。个人信用信息基础数据库,就是一般所说的 个人征信系统。如楼主所说的情况,在该系统的信用卡记录中,有可能会产生2次逾期还款记录。但有些银行

资讯

光圈快门基础知识

阅读(27)

本文主要为您介绍光圈快门基础知识,内容包括数码摄影,光圈与快门速度详解.!,摄影基础知识光圈快门如何配合使用,谁能普及一下相机镜头光圈和快门的知识。光圈与快门常识 ------------------------------------------------------------

资讯

贷款基础知识试题

阅读(27)

本文主要为您介绍贷款基础知识试题,内容包括基础会计借贷题目,会计基础有关借贷的题目,信贷员考试试题谁有啊急求。收到客户预交订货款500 000元时,收入未实现,待实际发货时再确认收入。 借:银行存款 500000 贷:应收账款 5000002、电

资讯

通信标准基础知识

阅读(23)

本文主要为您介绍通信标准基础知识,内容包括中国新出的通信标准是什么?,学习通信最基础需要什么知识,通信工程师的标准是什么?。通信技术,又称通信工程(也作 信息工程、电信工程,旧称远距离通信工程、弱电工程)是电子工程的重要分支,同时也是其

资讯

公共基础知识财务题库

阅读(27)

本文主要为您介绍公共基础知识财务题库,内容包括。2008年福建会计从业资格考试《财经法规与会计职业道德》答案 一.单选 1。D 取鲜摆绞肢悸扮溪堡娄2。A 3。B 4。C 5。C 6。

资讯

电气相关基础知识

阅读(26)

本文主要为您介绍电气相关基础知识,内容包括电气安全基础知识内容呢?,电气基本知识?,电气自动化基础知识。电力行业,电气工程及其自动化专业名词解释: 三相交流电:由三个频率相同、电势振幅相等、相位差互差120°角的交流电路组成的电力系统,叫

资讯

卫生专业基础知识药学

阅读(23)

本文主要为您介绍卫生专业基础知识药学,内容包括什么是医药卫生专业基础知识,医药卫生专业基础知识包括哪些内容,医疗卫生系统考试药学专业考什么哪些科目。医药卫生专业基础知识一般包括生理、生化、解剖、药理、病理、诊断、伦理学等。医

资讯

内科护士常见基础知识

阅读(27)

本文主要为您介绍内科护士常见基础知识,内容包括护理基础知识1000题的内容简介,护士必须知道的常识?,内科护理学常考哪些重点。《护理基础知识1000题》参照普通高等教育“九·五”、“十一五”国家规划教材《基础护理学》、《外科护理学》

资讯

网络安全工程师基础知识

阅读(26)

本文主要为您介绍网络安全工程师基础知识,内容包括网络安全工程师要学些什么?,成为网络安全工程师,初期必须掌握的知识,网络安全工程师主要做些什么,要具备什么技能?。您好,网络安全工程师学习内容:计算机应用、计算机网络、通信、信息安全等

资讯

文笔和编导的基础知识

阅读(28)

本文主要为您介绍文笔和编导的基础知识,内容包括编导的文学常识,关于编导,编导的基础知识有那些??。第一部分 考试环节及科目 考试环节 广播电视编导专业术科考试由笔试和面试两个环节组成,满分300分,其中笔试满分160分,面试满分140

资讯

安全生产基础知识论文

阅读(28)

本文主要为您介绍安全生产基础知识论文,内容包括企业安全方面论文,论文内容:围绕着“认真贯彻《安全许可证条例》,积极开展安全生产,关于安全的论文160字。加强特种作业人员培训工作的重要意义的思考 特种作业人员培训的特殊性决定着必须对

资讯

综合基础知识整理笔记

阅读(28)

本文主要为您介绍综合基础知识整理笔记,内容包括我文综基础知识几乎为零,帮我整理高中所有政史地的笔记,要特别特,公务员综合知识笔记怎么写?好多知识点啊,高中文综知识重点。建议你把文综课本看一遍,知识点理一遍吧。把班上成绩好的同学的