数据结构 二叉树
二叉树是指一个树的父节点最多只有两个子节点构成的树，树是不限制子节点的个数的。
二叉树是树的一种特例，是树的子集。
三个节点是无法表示出二叉树和树的区别的，需要三个以上的节点。
二叉树的表示如下图。
树的表示如下图。
扩展资料：
树图是一种数据结构，由n (n>=1)个有限节点组成具有层次关系的集合。它被称为树是因为它看起来像一棵倒立的树，意思是它的根是向上的，叶子是向下的。它具有以下特点:
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每个非根节点都有且只有一个父节点；除了根之外，每个子树还可以分为多个不相交的子树。
相关术语
节点的度：节点中包含的子树数称为节点的度；
叶节点或终端节点：度为0的节点称为叶节点；
非终端节点或分支节点:度不为0的节点;
父节点或父节点：如果一个节点包含子节点，该节点称为子节点的父节点；
子节点或子节点：一个节点包含的子树的根节点称为该节点的子节点；
同级节点：具有相同父节点的节点称为同级节点。
树度:在树中，最大节点的度称为树的度;
节点层次结构:从根开始，根是第一层，根的子节点是第二层，依此类推。
树的高度或深度：树中节点的最大级别；
表亲节点：父节点在同一层的节点是彼此的表亲；
节点的祖先：从根节点到该节点所经过的分支的所有节点；
子代：根于某一节点的子树中的任何节点称为该节点的子代。
森林:以m (m>=0)相交的树的集合称为森林;
参考资料：百度百科-树（数据结构）
二叉树的基本操作 C语言实现/*程序实现内容 1．采用二叉树链表作为存储结构，建立二叉树； 2．对二叉树分别按先、中、后序以及按层次遍历，输出相应的访问序列； 3．计算二叉树的深度，统计所有叶子结点总数及树中包含的结点总数。*/ #include"stdio.h" #include"string.h" #include"malloc.h" #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); } } //DLR 先序遍历 void Preorder(BinTree T) { if(T) { printf("%c",T->data); //访问结点 Preorder(T->lchild); //先序遍历左子树 Preorder(T->rchild); //先序遍历右子树 } } //LDR 中序遍历 void Inorder(BinTree T) { if(T) { Inorder(T->lchild); //中序遍历左子树 printf("%c",T->data); //访问结点 Inorder(T->rchild); //中序遍历右子树 } } //LRD 后序遍历 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); } //利用“先进先出”（FIFO）队列，按层次遍历二叉树 void Levelorder(BinTree T) { int front=0,rear=1; BinTNode *cq[Max],*p; //定义结点的指针数组cq cq[1]=T; //根入队 while(front!=rear) { front=(front+1)%NodeNum; p=cq[front]; //出队 printf("%c",p->data); //出队，输出结点的值 if(p->lchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->lchild; //左子树入队 } if(p->rchild!=NULL){ rear=(rear+1)%NodeNum; cq[rear]=p->rchild; //右子树入队 } } } //主函数 main() { BinTree root; int i,depth; printf("
"); printf("Creat Bin_Tree; Input preorder:"); //输入完全二叉树的先序序列， // 用#代表虚结点，如ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点 do { //从菜单中选择遍历方式，输入序号。 printf("********** select ************
"); printf("1: Preorder Traversal
"); printf("2: Iorder Traversal
"); printf("3: Postorder traversal
"); printf("4: PostTreeDepth,Node number,Leaf number
"); printf("5: Level Depth
"); //按层次遍历之前，先选择4，求出该树的结点数。 printf("0: Exit
"); printf("*******************************
"); scanf("%d",&i); //输入菜单序号（0-5） 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("
"); } while(i!=0);
二叉树的根结点是第一棵树的根结点，它的左子结点是第一棵树的最左子结点，右子结点是下一棵树（相当于兄弟结点）。一棵树对应的二叉树的根结点右子结点总是为空。
m-n
右红信润： 先介绍一下树:1.树的定义 树是一种常见的非线性的数据结构.树的递归定义如下: 树是n(n>0)个结点的有限集,这个集合满足以下条件: ⑴有且仅有一个结点没有前件(父亲结点),该结点称为树的根; ⑵除根外,其余的每个结点都有且仅...
中卫市13792591050： 数据结构中什么是二叉树？
右红信润： 树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序如下时,可用树表示源源程序如下的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.满二叉树,完全二叉树,排序二叉树.
中卫市13792591050： 数据结构二叉树？
右红信润： 2.viod inorder(bitree){ if(!t) return; else{ inorder(t->lchild); visite(t->data);/*访问根结点*/ inorder(t->rchild); } }
中卫市13792591050： 数据结构二叉树 - ？
右红信润： 二叉树的定义:二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成.(在某个阶段都是两种结果的情形) 二叉树的特点有:*每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点.*左子树和右子树是有顺序的,次序不能任意颠倒.*即使树中某结点只有一棵子树,也要区分它是左子树还是右子树.二叉树具有五种基本形态:1.空二叉树.2.只有一个根结点.3.根结点只有左子树.4.根结点只有右子树.5.根结点既有左子树又有右子树.
中卫市13792591050： 在数据结构中什么是二叉树?什么是树?二者有什么区别么? - ？
右红信润： 树是只有一个根结点的n个结点的有限集,二叉树是度为二的树
中卫市13792591050： c语言数据结构:怎么建立一个二叉树? - ？
右红信润： 只要将一个二叉树用“括号表示法”表示出来,然后,用链式存储结构将其各个结点存储就可以了,也就是输入一个二叉树.最后,用中序遍历输出! typedef struct node{ ElemType data;struct node *lchild,*rchild;} BTNode; //创建一个二叉树...
中卫市13792591050： 数据结构之二叉树 - ？
右红信润： 兄弟~~~ 我们今天刚上级啦~~ 我的编译成功啦~~ 建立二叉树输出先序中序后序遍历~~ 可以直接输入表达式~~ 就是我们上机没这个要求啊~~ 不过这个应该对你有帮助的·~如下~~#include <stdio.h>#include <malloc.h>#define maxsize 1024#...
中卫市13792591050： 数据结构二叉树一道习题① 试找出满足下列条件的二叉树1)先序序列与后序序列相同 2)中序序列与后序序列相同3)先序序列与中序序列相同 4)中序序列... - ？
右红信润：[答案] 我觉得你可以先写出这样的遍历顺序,然后照着序列去画 对于1)只有一个节点就是了呀; 对于2)就只能是每个节点只有左孩子; 对于3)就只能是每个节点只有右孩子; 对于4)可以是只有右孩子; 其实对于上述的那一种都可以是只有一个节点;
中卫市13792591050： 数据结构二叉树一棵二叉树中共有70 个叶子结点与80 个度为1的结点,则该二叉树中的总结点数为多少?其计算公式是什么? - ？
右红信润：[答案] 已知公式 1结点总数n=n0+n1+n2 2 n0 = n2+1 得到n=2n0+n1-1 no = 70 n1 = 80 n = 219
中卫市13792591050： 数据结构中的二叉树是什意思? ？
右红信润： 希望我的回答对你有用. 中文名二叉树外文名BinaryTree概述计算机中数据结构的一种简介每个结点最多有两个子树的树结构1定义2基本概念相关术语存储结构先序遍历后序遍历线索二叉树4实现演示二叉树定义编辑二叉树在图论中是这样定义的:二叉树是一个连通的无环图,并且每一个顶点的度不大于3
