下载文档原格式
数据结构有序树转⼆叉树（树的遍历）Description计算输⼊有序树的深度和有序树转化为⼆叉树之后树的深度。
Input输⼊包含多组数据。
每组数据第⼀⾏为⼀个整数n（2<=n<=30000）代表节点的数量，接下来n-1⾏，两个整数a、b代表a是b的⽗亲结点。
Output输出当前树的深度和转化成⼆叉树之后的深度。
Sample Input51 51 35 21 4Sample Output3 4HINTAppend Code析：这个题很好说，只要遍历⼀次就能得到答案，由于要先有序树转成⼆叉树，我也没听过，我百度了⼀下怎么转，看到百度百科中有，我总结⼀下就是，左⼉⼦，右兄弟，和那个字典树有的⼀拼，也就是左结点是⼉⼦结点，⽽右结点是兄弟结点，那么我们可以⽤两个参数来记录深度，⼆叉树既然是右兄弟，那么同⼀深度的就会多⼀层，加1，这样最⼤的就是答案。
代码如下：#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cstdio>#include <string>#include <cstdlib>#include <cmath>#include <iostream>#include <cstring>#include <set>#include <queue>#include <algorithm>#include <vector>#include <map>#include <cctype>#include <cmath>#include <stack>#define debug puts("+++++")//#include <tr1/unordered_map>#define freopenr freopen("in.txt", "r", stdin)#define freopenw freopen("out.txt", "w", stdout)using namespace std;//using namespace std :: tr1;typedef long long LL;typedef pair<int, int> P;const int INF = 0x3f3f3f3f;const double inf = 0x3f3f3f3f3f3f;const LL LNF = 0x3f3f3f3f3f3f;const double PI = acos(-1.0);const double eps = 1e-8;const int maxn = 3e4 + 5;const LL mod = 1e3 + 7;const int N = 1e6 + 5;const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1};const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1};const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; inline LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a%b); }inline int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }inline int lcm(int a, int b){ return a * b / gcd(a, b); }int n, m;const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};inline int Min(int a, int b){ return a < b ? a : b; }inline int Max(int a, int b){ return a > b ? a : b; }inline LL Min(LL a, LL b){ return a < b ? a : b; }inline LL Max(LL a, LL b){ return a > b ? a : b; }inline bool is_in(int r, int c){return r >= 0 && r < n && c >= 0 && c < m;}vector<int> G[maxn];bool in[maxn];int ans1, ans2;void dfs(int u, int cnt1, int cnt2){ans1 = Max(ans1, cnt1);ans2 = Max(ans2, cnt2);for(int i = 0; i < G[u].size(); ++i)dfs(G[u][i], cnt1+1, cnt2+i+1);}int main(){while(scanf("%d", &n) == 1){for(int i = 0; i <= n; ++i) G[i].clear(), in[i] = 0;int u, v;for(int i = 1; i < n; ++i){scanf("%d %d", &u, &v);G[u].push_back(v);in[v] = true;}ans1 = ans2 = 0;for(int i = 1; i <= n; ++i) if(!in[i]){dfs(i, 1, 1); break;}printf("%d %d\n", ans1, ans2);}return 0;}。
树转化为二叉树的方法如下：
1、去除所有父结点也孩子结点连线。
2、把父结点与最左边的孩子相连，作为父结点的左孩子。
3、把同层结点的兄弟结点相连作为左边兄弟的右孩子，以此类推所有结点即得到二叉树。
二叉树
二叉树（Binary tree）是指计算机科学中每个结点最多有两个子树的树结构，其子树被称作“左子树”（left subtree）和“右子树”（right subtree），常被用于实现二叉查找树和二叉堆。
在二叉树中，一个元素也称作一个结点。
当集合为空时，称该二叉树为空二叉树。
二叉树的遍历，遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。
由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD（称为后根次序遍历）。
二叉树转换为树的规则摘要：一、二叉树与树的定义1.二叉树的定义2.树的定义二、二叉树转换为树的规则1.树的根节点2.树的层次结构3.树的节点关系三、转换方法与步骤1.遍历二叉树2.构建树结构3.确定节点关系四、转换过程中的注意事项1.避免重复遍历2.确保节点唯一性3.考虑节点顺序正文：二叉树与树是计算机科学中常用的数据结构，它们在数据存储与处理方面具有重要作用。
二叉树是一种特殊的树结构，每个节点最多只有两个子节点，分别称为左子节点和右子节点。
在实际应用中，有时需要将二叉树转换为树结构。
本文将详细介绍二叉树转换为树的规则及方法。
首先，我们需要了解二叉树与树的定义。
二叉树是一种特殊的树结构，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。
树是一种非线性的数据结构，由若干个节点组成，这些节点通过边相互连接，具有唯一的根节点。
二叉树转换为树的规则主要包括以下几点：1.树的根节点：二叉树的根节点将成为树的根节点。
2.树的层次结构：二叉树的层次结构将转换为树的层次结构。
具体来说，二叉树的同一层节点将转换为树的同一行节点。
3.树的节点关系：二叉树中相邻的兄弟节点在树中将成为兄弟节点或子节点。
对于二叉树的每个节点，它的左子节点将成为树的子节点，右子节点将成为兄弟节点。
需要注意的是，在转换过程中要确保节点关系的正确性。
接下来，我们介绍二叉树转换为树的步骤：1.遍历二叉树：首先需要遍历二叉树，获取每个节点的信息，如节点值、左右子节点等。
2.构建树结构：根据遍历得到的节点信息，构建树的层次结构。
树的根节点即为二叉树的根节点，树的层次结构应与二叉树的层次结构保持一致。
3.确定节点关系：根据二叉树中节点之间的关系，确定树中节点之间的关系。
具体来说，二叉树的左子节点将成为树的子节点，右子节点将成为兄弟节点。
在二叉树转换为树的过程中，需要注意以下几点：1.避免重复遍历：在遍历二叉树时，应尽量避免重复遍历同一节点，以提高转换效率。
数据结构详细教案——树与二叉树一、教学目标1.了解树和二叉树的基本概念和特点；2.掌握树和二叉树的基本操作；3.能够通过递归遍历树和二叉树。
二、教学重难点1.树和二叉树的基本概念和特点；2.递归遍历树和二叉树。
三、教学内容1.树的概念和特点1.1树的定义树是n（n>=0）个节点的有限集。
当n=0时，称为空树；如果不为空树，则1. 树有且仅有一个特殊节点被称为根（Root）；2.其余节点可分为m（m>0）个互不相交的有限集T1，T2，...，Tm，其中每个集合又是一棵树。
1.2节点间的关系- 父节点（parent）是当前节点的直接上级节点；- 子节点（child）是当前节点的直接下级节点；- 兄弟节点（sibling）是具有同一父节点的节点；- 祖先节点（ancestor）是通过从当前节点到根的任意路径可以到达的节点；- 子孙节点（descendant）是通过从该节点到子树的任意节点可以到达的节点。
1.3树的特点-树是一个有层次的结构，可以看作是一个鱼骨图；-树中的每个节点都可以有多个子节点，但只有一个父节点；-树中的节点之间是唯一的，不存在重复节点；-树中的任意两个节点之间都有且仅有一条路径连接。
2.二叉树的概念和特点2.1二叉树的定义二叉树是一种特殊的树结构，它的每个节点最多只能有两个子节点，分别称为左子节点和右子节点。
2.2二叉树的特点-二叉树的度最大为2，即每个节点最多有两个子节点；-二叉树的第i层最多有2^(i-1)个节点；-对于任意一颗二叉树，如果其叶子节点数为n0，度为2的节点数为n2，则有n0=n2+1；-完全二叉树是一种特殊的二叉树，除了最后一层的叶子节点外，每一层的节点都是满的。
四、教学过程1.讲解树和二叉树的基本概念和特点，引导学生理解树和二叉树的定义和节点间的关系。
2.分析树和二叉树的基本操作，并通过实例演示操作过程，让学生掌握操作的步骤和方法。
3.运用递归算法遍历树和二叉树的过程，详细讲解前序遍历、中序遍历和后序遍历的定义和实现方法。
《数据结构》课程设计报告设计题目：_树与二叉树的转换___姓名：_______李锦_____________学号：________211214011_______专业：_______物联网工程_______院系：_______计算机科学与技术_______班级：__________1205___________指导教师：_________高秀梅______2014年 2 月14 日目录一、问题描述 (2)二、基本要求 (2)三、概要设计 (2)四、数据结构设计 (2)五、算法设计 (3)1、算法分析 (3)2、算法实现 (3)六、程序测试与实现 (6)1、函数之间的调用关系 (6)2、主程序 (6)3、测试数据 (8)4、测试结果 (8)七、调试分析 (10)八、遇到的问题及解决办法 (10)九、心得体会 (10)一、问题描述完成树与二叉树的转换二、基本要求1、树采用双亲表示法2、能够将树转换为二叉树3、对转换的二叉树进行算法设计统计人一结点的孩子数4、利用转换的二叉树计算树的高度三、概要设计操作集合：(1) CTreeNode *SearchCTree(CTreeNode *root ,char data) 查找树结点(2) CTreeNode *CreateSTree() 生成树(3) void preorderTree(CTreeNode *ctroot) 树的遍历(4) void PrintTree(CTreeNode *troot,int depth) 树的输出(5 void initQueueCTree(QueueCTree *&q) 初始化树队列(6) void initQueueBTree(QueueBTree *&q) 初始化二叉树队列（7）void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot) //树转化为二叉树ctroot 指向树的根节点，btroot,指向二叉树的根四、数据结构设计struct CTreeNode//树节点的类型{char data;//数据域，采用char星struct CTreeNode *children[DEGREE];//指向孩子节点的指针域};struct BTreeNode{char data;//数据域BTreeNode *lchild,*rchild;//左右孩子节点的指针};//树队列结构体类型struct QueueCTree{CTreeNode *CTreeArray[MAX_NODE_NUM];//结构体指针数组，存放节点的地址//struct nodeCTree *next;int CTreeFront,CTreeRear;};//二叉树队列结构类型struct QueueBTree{BTreeNode *BTreeArray[MAX_NODE_NUM];//结构体指针数组，存放节点的地址//struct nodeBTree *next;int BTreeFront,BTreeRear;};五、算法设计1、算法分析将树转换成二叉树的步骤是：（1）加线。
就是在所有兄弟结点之间加一条连线；（2）抹线。
就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；（3）旋转。
就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。
2、算法实现void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)//树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的跟{QueueCTree *VisitedCTreeNodes;QueueBTree *VisitedBTreeNodes;//辅助队列initQueueCTree(VisitedCTreeNodes);initQueueBTree(VisitedBTreeNodes);//初始化队列CTreeNode *ctnode;BTreeNode *btnode,*p,*LastSibling;int i;btroot=new BTreeNode;//添加开辟内存空间语句btroot->data=ctroot->data;//树的根节点作为二叉树的根节点btroot->lchild=btroot->rchild=NULL;addQueueCTree(VisitedCTreeNodes,ctroot);//树的跟节点入队addQueueBTree(VisitedBTreeNodes,btroot);//二叉树的跟节点入队while(!QueueCTreeEmpty(VisitedCTreeNodes)){ctnode=delQueueCTree(VisitedCTreeNodes);//树节点出队btnode=delQueueBTree(VisitedBTreeNodes);//二叉树节点出队for(i=0;i<DEGREE;i++)//访问节点所有的孩子节点{if(ctnode->children[i]==NULL)//孩子节点访问完毕break;p=new BTreeNode;//分配二叉树节点p->data=ctnode->children[i]->data;p->lchild=p->rchild=NULL;if(i==0)btnode->lchild=p;//长子，作为父节点的做孩子elseLastSibling->rchild=p;//作为上一个兄弟节点的右孩子LastSibling=p;addQueueCTree(VisitedCTreeNodes,ctnode->children[i]);//树节点进队列addQueueBTree(VisitedBTreeNodes,p);//二叉树节点进门队列}3、算法流程图六、程序测试与实现1、函数之间的调用关系2、主程序int main(){CTreeNode *Tree;BTreeNode *BTree;int x=0;char n,i,j,k;while(1){p:n=menu();if(n=='1'){while(1){i=Treemenu();switch(i){case '1':Tree=CreateSTree();break;case '2':PrintTree(Tree,10);cout<<"\n\t\t按任意键返回...\n";getch();break;case '3':preorderTree(Tree);cout<<"\n\t\t按任意键返回...\n";getch();break;case '4':goto p;break;}}}if(n=='2'){TreeToBTree(Tree,BTree);while(1){j=Btreemenu();switch(j){case '1':PrintIn(BTree,5);cout<<"\n\t\t按任意键返回...\n";getch();break;case '2':Preorder(BTree);cout<<"\n\t\t按任意键返回...\n";getch();break;case '3':cout<<FindDepth(BTree);cout<<"\n\t\t按任意键返回...\n";getch();break;case '4':count(BTree);cout<<"\n\t\t按任意键返回...\n";getch();break;case '5':goto p;break;}}}if(n=='3'){break;}}return 0;}3、测试数据a b c d e4、测试结果数据结构课程设计七、调试分析首先根据指令，输入信息，生成一个树后，再将生成的树转化成二叉树，然后输出二叉树的结构图,二叉树的前序遍历结果以及二叉树的深度和节点孩子数八、遇到的问题及解决办法调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题。
九、心得体会通过本次课程设计，我发现，有关一个课题的所有知识不仅仅是在课本上，多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力。
本次课程设计还让我认识到自己的缺点。
本次选的课题是二叉树的遍历，因为本学期所学的就是二叉树等数据结构，所以认为比较适合。
刚开始认为会很简单，但到后来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。
经过慢慢的调试，最终测试成功。
这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我的知识面，使我更加熟练的掌握各种方法。
总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构更加了解。
10。
