数据结构 二叉树
如果要在内存中建立一个如下左图这样的树，wield能让每个结点确认是否有左右孩子，我们对它进行扩展，变成如下右图的样子，也就是将二叉树中的每个结点的空指针引出一个虚结点，其值为一个特定值，比如”#”，称之为扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。如前序遍历序列为AB#D##C##。
有了这样的准备，就可以看看如何生成一棵二叉树了。假设二叉树的结点均为一个字符，把刚才前序遍历序列AB#D##C##用键盘挨个输入，实现的算法如下所示。
二叉树建立实现代码一，如下所示。
//创建树//按先后次序输入二叉树中结点的值(一个字符),#表示空树//构造二叉链表表示的二叉树BiTree CreateTree(BiTree t){ char ch; scanf("%c", &ch); if(ch == '#') { t = NULL; } else { t = (BitNode *)malloc(sizeof(BitNode)); if(t == NULL) { fprintf(stderr, "malloc() error in CreateTree.
"); return; } t->data = ch; //生成根结点 t->lchild = CreateTree(t->lchild); //构造左子树 t->rchild = CreateTree(t->rchild); //构造右子树 } return t;} 二叉树建立实现代码二，如下所示。
//创建树方法二int CreateTree2(BiTree *t){ char ch; scanf("%c", &ch); if(ch == '#') { (*t) = NULL; } else { (*t) = (BiTree)malloc(sizeof(BitNode)); if((*t) == NULL) { fprintf(stderr, "malloc() error in CreateTree2.
"); return ERROR; } (*t)->data = ch; CreateTree2(&((*t)->lchild)); CreateTree2(&((*t)->rchild)); } return OK;} 其实建立二叉树，也是利用了递归的原理。只不过在原来应该打印结点的地方，改成生成结点、给结点赋值的操作而已。因此，完全可以用中序或后序遍历的方式实现二叉树的建立，只不过代码里生成结点和构造左右子树的代码顺序交互一下即可。
二叉树的定义：二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。（在某个阶段都是两种结果的情形）
二叉树的特点有：
*每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
*左子树和右子树是有顺序的，次序不能任意颠倒。
*即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树具有五种基本形态：
1.空二叉树。
2.只有一个根结点。
3.根结点只有左子树。
4.根结点只有右子树。
5.根结点既有左子树又有右子树。
1.树的定义
树是一种常见的非线性的数据结构。树的递归定义如下：
树是n(n>0)个结点的有限集，这个集合满足以下条件：
⑴有且仅有一个结点没有前件（父亲结点），该结点称为树的根；
⑵除根外，其余的每个结点都有且仅有一个前件；
⑶除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后件（儿子结点）；
2、结点的分类
在树中，一个结点包含一个元素以及所有指向其子树的分支。结点一般分成三类
⑴根结点：没有前件的结点。在树中有且仅有一个根结点。
⑵分支结点：除根结点外，有后件的结点称为分支结点。分支结点亦是其子树的根；
⑶叶结点：没有后件的结点称为树叶。由树的定义可知，树叶本身也是其父结点的子树。
根结点到每一个分支结点或叶结点的路径是唯一的。
3、有关度的定义
⑴结点的度：一个结点的子树数目称为该结点的度。显
然，所有树叶的度为0。
⑵树的度：所有结点中最大的度称为该树的度。4、树的深度（高度）
树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。
5、有序树和无序树
按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。
6、树的表示方法
树的表示方法一般有两种：
⑴自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。
⑵括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式
（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））
7、树的存储结构一般有两种
⑴静态的记录数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标
⑵动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成
下面是有关二叉树的内容：
二叉树的概念
二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，且其子树有左右之分（次序不能任意颠倒）。
1、二叉树的递归定义和基本形态
二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：
⑴有一个特定的结点称为根；
⑵余下的结点分为互不相交的子集L和R，其中R是根的左子树；L是根的右子树；L和R又是二叉树；
由上述定义可以看出，二叉树和树是两个不同的概念
⑴树的每一个结点可以有任意多个后件，而二叉树中每个结点的后件不能超过2；
⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。
2、二叉树的两个特殊形态
⑴满二叉树： 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。可以验证具有n个叶结点的满二叉树共有2n-1个结点。
⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树
3、二叉树的三个主要性质
性质1：在二叉树的第i（≥1）层上，最多有2i-1个 结点
证明：我们采用数学归纳法证明：当i=1时只有一个根结点，即2i-1=20=1，结论成立。假设第k(i=k)层上最多有2k-1个结点，考虑i=k+1。由归纳假设，在二叉树第k层上最多有2k-1个结点，而每一个结点最多有两个子结点，因此在第k+1层上最多有2．2k-1=2(k+1)-1=2i，结论成立。综上所述，性质1成立。
性质2：在深度为k(k≥1)的二叉树中最多有2k-1个 结点。
证明：由性质1，在二叉树第i层上最多有2i-1个结点，显然，第1层¨第k层的最多结点数为 个结点。证毕。
性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。
证明：设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然n=n0+n1+n2 （1）
由于二叉树中除了根结点外，其余每个结点都有且仅有一个前件。设 b为二叉树的前件个数，n=b+1（2）
所有这些前件同时又为度为1和度为2的结点的后件。因此又有b=n1+2n2 (3)
我们将（3）代入（2）得出n=n1+2n2+1 (4)
比较（1）和（4），得出n0=n2+1,即叶子数比度为2的结点数多1
4、普通有序树转换成二叉树
普通树为有序树T，将其转化成二叉树T’的规则如下：
⑴T中的结点与T’中的结点一一对应，即T中每个结点的序号和值在T’中保持不变；
⑵T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；
⑶T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；
由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。
5、二叉树的存储结构
将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括
⑴一个数据域（data）；
⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。
满二叉树和完全二叉树一般采用顺序存储结构
对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：
⑴值域： data
⑵左指针域： lch
⑶右指针域： rch
这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点
6、二叉树的遍历
二叉树遍历的定义：按照一定的规律不重复地访问(或取出结点中的信息，或对结点作其它的处理)二叉树中的每一个结点。
二叉树遍历的顺序：如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，则只剩下三种组合：LDR（中序遍历）、LRD（后序遍历）、DLR（前序遍历）。
前序遍历的规则如下：
若二叉树为空，则退出。否则
⑴访问处理根结点；
⑵前序遍历左子树；
⑶前序遍历右子树；
特点：由左而右逐条访问由根出发的树支 （回溯法的基础）
中序遍历的规则：
若二叉树为空，则退出；否则
⑴中序遍历左子树；
⑵访问处理根结点；
⑶中序遍历右子树；
后序遍历的规则如下：
若二叉树为空，则退出；否则
⑴后序遍历左子树；
⑵后序遍历右子树；
⑶访问处理根结点；
特点：可统计任一个结点为根的子树的情况（例如子树的权和，最优策略的选择（博弈数））
度最大为2的树
关于2X树的算法也蛮多的,你要的是哪种算法?
用2X搜索树实现字典?
还是就单单2叉树的基本算法?
每个节点拥有的分支节点不超过2个
——个人理解，书上怎么说得我忘了
战苇坤宝： 树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样.树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示.树在计算机领域中也得到广泛应用,如在编译源程序如下时,可用树表示源源程序如下的语法结构.又如在数据库系统中,树型结构也是信息的重要组织形式之一.一切具有层次关系的问题都可用树来描述.满二叉树,完全二叉树,排序二叉树.
色达县13081396619： 数据结构二叉树？
战苇坤宝： 2.viod inorder(bitree){ if(!t) return; else{ inorder(t->lchild); visite(t->data);/*访问根结点*/ inorder(t->rchild); } }
色达县13081396619： 数据结构二叉树 - ？
战苇坤宝： 二叉树的定义:二叉树是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成.(在某个阶段都是两种结果的情形) 二叉树的特点有:*每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点.*左子树和右子树是有顺序的,次序不能任意颠倒.*即使树中某结点只有一棵子树,也要区分它是左子树还是右子树.二叉树具有五种基本形态:1.空二叉树.2.只有一个根结点.3.根结点只有左子树.4.根结点只有右子树.5.根结点既有左子树又有右子树.
色达县13081396619： c语言数据结构:怎么建立一个二叉树? - ？
战苇坤宝： 只要将一个二叉树用“括号表示法”表示出来,然后,用链式存储结构将其各个结点存储就可以了,也就是输入一个二叉树.最后,用中序遍历输出! typedef struct node{ ElemType data;struct node *lchild,*rchild;} BTNode; //创建一个二叉树...
色达县13081396619： 数据结构 二叉树 - ？
战苇坤宝： m-n,根结点算在内.二叉树的根结点是第一棵树的根结点,它的左子结点是第一棵树的最左子结点,右子结点是下一棵树(相当于兄弟结点).一棵树对应的二叉树的根结点右子结点总是为空.
色达县13081396619： 数据结构之二叉树 - ？
战苇坤宝： 兄弟~~~ 我们今天刚上级啦~~ 我的编译成功啦~~ 建立二叉树输出先序中序后序遍历~~ 可以直接输入表达式~~ 就是我们上机没这个要求啊~~ 不过这个应该对你有帮助的·~如下~~#include <stdio.h>#include <malloc.h>#define maxsize 1024#...
色达县13081396619： 数据结构二叉树一道习题① 试找出满足下列条件的二叉树1)先序序列与后序序列相同 2)中序序列与后序序列相同3)先序序列与中序序列相同 4)中序序列... - ？
战苇坤宝：[答案] 我觉得你可以先写出这样的遍历顺序,然后照着序列去画 对于1)只有一个节点就是了呀; 对于2)就只能是每个节点只有左孩子; 对于3)就只能是每个节点只有右孩子; 对于4)可以是只有右孩子; 其实对于上述的那一种都可以是只有一个节点;
色达县13081396619： 在数据结构中什么是二叉树?什么是树?二者有什么区别么? - ？
战苇坤宝： 树是只有一个根结点的n个结点的有限集,二叉树是度为二的树
色达县13081396619： 数据结构中的二叉树是什意思? ？
战苇坤宝： 希望我的回答对你有用. 中文名二叉树外文名BinaryTree概述计算机中数据结构的一种简介每个结点最多有两个子树的树结构1定义2基本概念相关术语存储结构先序遍历后序遍历线索二叉树4实现演示二叉树定义编辑二叉树在图论中是这样定义的:二叉树是一个连通的无环图,并且每一个顶点的度不大于3
色达县13081396619： 计算机,数据结构,二叉树的最小高度,急设某棵树中有2000个结点,则该二叉树的最小高度() - ？
战苇坤宝：[答案] 要想是二叉树的最小高度,那该二叉树为完全二叉树啊,那么对应的高度为:log2(2000)下取整再加1等于11
