求数据结构树与二叉树转换C语言代码

1. 求数据结构树与二叉树转换C语言代码

那个叫二叉树啊
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
    一、树的概述
 树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。
（一）树的定义
 树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(ROOT)的结点；

⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。


树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树

1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。

2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；

3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合就为森林；

4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。

5.树的表示

树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：

(A(B(E(K,L),F),C(G),D(H(M),I,J)))

5. 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，则无右儿子。

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是一棵完全二叉树。
    三、二叉树的遍历
    遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
    设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。

(1)先序遍历

访问根；按先序遍历左子树；按先序遍历右子树

(2)中序遍历

按中序遍历左子树；访问根；按中序遍历右子树

(3)后序遍历

按后序遍历左子树；按后序遍历右子树；访问根

2. 数据结构二叉树C语言

二叉树是一种非常重要的数据结构。本文总结了二叉树的常见操作：二叉树的构建，查找，删除，二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历)，二叉搜索树的构造等。
1. 二叉树的构建
  二叉树的基本构建方式为:添加一个节点，如果这是一棵空树，则将该节点作为根节点；否则按照从左到右、先左子树后右子树的顺序逐个添加节点。比如依次添加节点:1,6,10,2,7,11，则得到的二叉树为:

在这里，我们需要借助一个链表来保存节点，以实现二叉树的顺序插入，具体做法如下：
1.0 初始化一个用来保存二叉树节点的空链表；
1.1 插入一个节点，
①如果该树是一棵空树，则将该节点作为根节点，并且将该节点添加到链表中；
②如果该树不为空，取得链表第一个节点的值(注意不是链表的头节点)。如果该节点左子树为空，则将待插入节点添加到左子树，并且将左子树添加到链表；否则将待插入节点添加到右子树，将右子树添加到链表。此时，父节点的左右子树都不为空，将该父节点(即链表第一个节点)
弹出。
按照这样的顺序，我们就可以完成二叉树节点的顺序插入。

2. 二叉搜索树的构建
   二叉搜索树是这样一棵树：对于任意一个节点，其左子树的值均小于父节点的值；右子树的值均大于父节点的值。从二叉树的根节点开始，对于其左右子树均按照这样的方式递归插入，即可以得到一棵二叉搜索树。二叉搜索树具有很好的性质，因为它的有序性，如果在二叉搜索树中查找一个元素可以按照类似二分查找的方式进行；对于二叉搜索树，如果采用中序遍历则可以得到按照值递增排列的节点。二叉搜索树的具体构建方式如下：
插入一个节点：
2.1如果当前节点本身值为空，则将插入节点直接作为当前节点；
2.2如果当前节点本身值不为空，
①比较插入节点的值与当前节点的值，如果插入节点值小于当前节点值，则将该节点递归插入左子树；
②比较插入节点的值与当前节点的值，如果插入节点值大于当前节点值，则将该节点递归插入右子树；
③ 如果插入节点的值等于当前节点的值，则直接返回(即二叉搜索树每个节点的值都是不同的)。【摘要】
数据结构二叉树C语言【提问】
二叉树是一种非常重要的数据结构。本文总结了二叉树的常见操作：二叉树的构建，查找，删除，二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历)，二叉搜索树的构造等。
1. 二叉树的构建
  二叉树的基本构建方式为:添加一个节点，如果这是一棵空树，则将该节点作为根节点；否则按照从左到右、先左子树后右子树的顺序逐个添加节点。比如依次添加节点:1,6,10,2,7,11，则得到的二叉树为:

在这里，我们需要借助一个链表来保存节点，以实现二叉树的顺序插入，具体做法如下：
1.0 初始化一个用来保存二叉树节点的空链表；
1.1 插入一个节点，
①如果该树是一棵空树，则将该节点作为根节点，并且将该节点添加到链表中；
②如果该树不为空，取得链表第一个节点的值(注意不是链表的头节点)。如果该节点左子树为空，则将待插入节点添加到左子树，并且将左子树添加到链表；否则将待插入节点添加到右子树，将右子树添加到链表。此时，父节点的左右子树都不为空，将该父节点(即链表第一个节点)
弹出。
按照这样的顺序，我们就可以完成二叉树节点的顺序插入。

2. 二叉搜索树的构建
   二叉搜索树是这样一棵树：对于任意一个节点，其左子树的值均小于父节点的值；右子树的值均大于父节点的值。从二叉树的根节点开始，对于其左右子树均按照这样的方式递归插入，即可以得到一棵二叉搜索树。二叉搜索树具有很好的性质，因为它的有序性，如果在二叉搜索树中查找一个元素可以按照类似二分查找的方式进行；对于二叉搜索树，如果采用中序遍历则可以得到按照值递增排列的节点。二叉搜索树的具体构建方式如下：
插入一个节点：
2.1如果当前节点本身值为空，则将插入节点直接作为当前节点；
2.2如果当前节点本身值不为空，
①比较插入节点的值与当前节点的值，如果插入节点值小于当前节点值，则将该节点递归插入左子树；
②比较插入节点的值与当前节点的值，如果插入节点值大于当前节点值，则将该节点递归插入右子树；
③ 如果插入节点的值等于当前节点的值，则直接返回(即二叉搜索树每个节点的值都是不同的)。【回答】
3.二叉搜索树的查找
  二叉搜索树的查找类似于二分查找。具体步骤如下：
3.1 从根节点开始，比较查找值与当前节点值的大小：
① 如果当前节点值为空，则说明无法查找到该值，直接返回；
②如果当前节点值等于查找值，则查找成功；
③如果查找值小于当前节点的值，则递归查找左子树；
④如果查找值大于当前节点的值，则递归查找右子树。

4. 二叉搜索树的删除
   二叉搜索树的删除与查找基本类似，不同之处在于如果查找到了待删除的节点，则将该节点直接删除之后，还要进行如下操作保证删除节点之后的二叉树仍是一棵二叉搜索树：
①如果该删除节点没有左右子树，则直接删除该节点；
②如果该删除节点只有左子树(右子树)，则将删除节点的父节点直接指向其左子树(右子树);
③如果该删除节点既有左子树又有右子树，则有下面的三种处理方法：
4.3.1：找到按照中序遍历该删除节点的直接前驱节点，将该节点转移到删除节点，然后删除这个前驱节点；
4.3.2：找到按照中序遍历该删除节点的直接后续节点，将该节点转移到删除节点，然后删除这个后序节点；
4.3.3：找到按照中序遍历该删除节点的直接前驱节点，将删除节点的左子树接到父节点上，将删除节点的右子树接到该前序节点的右子树上，然后删除节点。

5. 二叉树的前序遍历
  由于二叉树是递归定义的，所以二叉树的遍历一般也是采用递归的形式。前序遍历即采用先访问根节点，再访问左子树，最后访问右子树的顺序。前序遍历也是按照类似的方式递归遍历，具体操作如下：
① 如果当前节点值为空，返回；
②如果当前节点值不为空，打印当前节点值；递归遍历左子树；递归遍历右子树。

6. 二叉树的中序遍历
①如果当前节点值为空，返回；
②递归遍历左子树；打印当前节点的值；递归遍历右子树。

7. 二叉树的后序遍历
①如果当前节点值为空，返回；
②递归遍历左子树；递归遍历右子树；打印当前节点的值。

8. 二叉树的层次遍历
  二叉树的层次遍历，即从根节点开始，逐层按照从左到右的顺序遍历。层次遍历比前中后序遍历要麻烦一点，它需要借助一个额外的链表来保存节点进行遍历。具体做法如下：
①初始化一个用来保存二叉树节点的空链表；
②如果这是一棵空二叉树，直接返回；否则将根节点添加到链表；
③while(当链表不为空时)
  弹出链表第一个二叉树节点，打印该二叉树节点的值；
  如果该二叉树节点的【回答】
您好有代码吗【提问】
右子树不为空，则将该右子树添加到链表；

  以上就是关于二叉树的基本操作，下面是C语言具体实现的代码，谨供参考【回答】
您能看到我问题的具体内容吗【提问】
没有【回答】
由先序序列和中序序列以及由中序序列和后序
序列构造一棵二叉树的功能(二叉树中的每个结点值为单个字符),要求以括号表示和凹入
表示法输出该二叉树,并用先序遍历序列“ABDEHJKLMNCFGI”和中序遍历序列
“DBJHLKMNEAFCGI”以及由中序遍历序列“DBJ HLKMNEAFCGI”和后序遍历序列
DJLNMKHEBFIGCA”进行验证
【提问】
你好，这方面我本来不太懂，因为点快点着单了，所以是尽可能的找些对你有用的资料。【回答】
好吧【提问】

3. C语言 数据结构 二叉树实现的疑问

首先敬仰一下楼主的勤奋！

我主要针对第二个算法说，我觉得上面这段话也是在讲第二个算法。其实两个算法差不太多。
1. 栈顶记录中的指针其实就是指栈顶，每次push()进去或者pop()出来的那个p。他代表的是正在访问的节点得下一个节点。比如，访问一个树t的左子树t->lchild时，栈顶就是t；访问t->lchild->lchild时，栈顶就是t->lchild。访问t->rchild时，栈顶为NULL；访问t->lchild->rchild时，栈顶为t；访问t->rchild->lchild时，栈顶也是t；访问t->rchild->rcchild时，栈顶仍为NULL。他的意义就是，在访问完了当前的子树之后，就会去访问栈顶记录的指针对应的节点的数据。
2. 关于“工作记录”那个词，我觉得还是别深究了。那段话意思是要仿照编译器把递归编译成迭代的思路来自己写迭代算法，可是实际上后面给出的算法里根本没有严格执行上述思路，写出来的算法并不是严格意义上的可以一般性替换递归的迭代算法。所以追究那个词也没意义，明白迭代遍历的算法怎么用就够了。等以后对递归有了更深刻的认识，自然就明白了。其实就是函数递归调用自身之前像中断那样保存自己的工作环境和进度。
3. （2）句并不矛盾。他说“指针为空时”和“指针指向的xxx”中间不是有句“退回上一层”么，那就表示pop()，于是原来那个在栈顶的空指针弹出去了，原来在第二位的指针现在到了栈顶。于是后面那句指的是对这个指针进行操作。
另外,虚机团上产品团购,超级便宜

4. 数据结构-二叉树的创建？

　　如果要在内存中建立一个如下左图这样的树，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.\n");            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.\n");            return ERROR;        }         (*t)->data = ch;        CreateTree2(&((*t)->lchild));        CreateTree2(&((*t)->rchild));    }    return OK;}　　其实建立二叉树，也是利用了递归的原理。只不过在原来应该打印结点的地方，改成生成结点、给结点赋值的操作而已。因此，完全可以用中序或后序遍历的方式实现二叉树的建立，只不过代码里生成结点和构造左右子树的代码顺序交互一下即可。

5. 二叉树（C语言）

这个问题，可以看成完全二叉树，有性质有节点i的父节点为： i/2.
而题目要求的意思也就是找到两个节点的公共父节点。（含可能为其中一个节点）
因此，思路如下：
输入两个值 x,y
找到较大的那个，（循环的，因不断改变，所以需不断比较）
做x=x/2；（假设此时x较大,x为int 型）
然后再比较，，如此反复。
当x==y时，结束，即为输出值。

（因马上断电，不给代码了，思路就是这样。。。）

6. 数据结构的二叉树

2、这个是平衡二叉树的定义，不是普通二叉树的要求
8、正确
2、设根结点的深度为1
深度为6的满二叉树只有最下一层是叶子，也就是有2^5=32个叶子，相应地，分支都是度为2的结点，有2^5-1 = 31 个

7. 还原二叉树（数据结构c语言版）

由先序知道A为根，由中序知道BC为左子树，EDGHFI为右子树，如图1所示；
以此类推，最终结果如4所示。

8. 数据结构~构建二叉树的简单题~~~求助

该二叉树为：
                   A
             /             \
           B                  E
         /                        \
       C                            F
     /                                 \
  D                                      G