(黑马课程)
(千夫影子)
(一叶知秋)
第三方登录：多叉树转换为二叉树算法
方法：将多叉树的第一个儿子结点作为二叉树的左结点，将其兄弟结点作为二叉树的右结点。
举例，如下图：
树的结构为：
typedef struct BinaryTreeNode{
struct BinaryTreeNode* leftC
struct BinaryTreeNode* rightC
typedef struct TreeNode{
struct TreeNode* child[];
int child_
BinaryTreeNode* ToBinaryTree(TreeNode* root){
if(root == null)
BinaryTreeNode* binaryRoot = new BinaryTreeNode();
binaryRoot-&leftChild =
binaryRoot-&rightChild = NULL;//注意初始化
binaryRoot-&value =
binaryRoot-&leftChild =
ToBinaryTree(root-&child[0]);
BinaryTreeNode* brother =
binaryRoot-&leftC
for(int i = 1; i &
root-&child_i++){
brother-&rightChild =
ToBinaryTree(root-&child[i]);
brother = brother-&rightC
return binaryR
看是什么二叉树了。
先遍历多叉树，将所有节点得到，然后根据相应的二叉树的规则构造二叉树就行了。
树采用的存储结构见表一，转化为二叉树见表二，之后再将表转化为二叉链表的存储方式，程序及相应测试见代码：
rightchild
1（原值为0 ）
#include &string&
#include&iostream&
struct Node { //以表的形式存储的树结点
struct TreeNode { //以二叉链表存储的树的结点
int creattable( Node table[]){ //创建树的表并转化为二叉树
int n,k,i,j;
cout&&"输入结点个数:(&20)";
if ( n&0 ){
cout&&"输入结点信息和双亲编号(第一个请输入根结点信息如
a -1 ):"&&
&& for( i = 0; i &
cin&&table[i].data&&table[i].
table[i].lchild = table[i].rchild = 0;
&& for( i = 0; i &
&&& for( j = 1;j
if( table[j].parent == i )
if( table[i].lchild == 0 ){
table[i].lchild =
table[k].rchild =
&& for( i = 0; i &
cout&&table[i].data&&table[i].parent&&table
[i].lchild&&table[i].rchild&&
void Build ( TreeNode*&
current,Node node[], int pos ,int n ){ //将表
转化为二叉链表
{if ( current == 0 ){
&& current = new TreeN
&& current-&l =
current-&r = 0;
current-&data = node[pos].
if (node[pos].lchild )
current-&l, node, node[pos].lchild, n);
if (node[pos].rchild
urrent-&r ,node, node[pos].rchild, n);
void Visit ( TreeNode* current ){ //访问结点
cout&&current-&data&&"
void Preorder( TreeNode* root ){ //按先序遍历
&& TreeNode* current =
&& if( current != 0
&&& Visit(
current );
&&& Preorder(
current-&l );
&&& Preorder(
current-&r
int main(){
Node node [20];
int n = creattable( node );
TreeNode* root = 0;
Build ( root, node, 0 , n);
if (root){
cout&&"先序遍历：";
&& Preorder ( root );
cout&&"空树！"&&
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
《数据结构课程设计之-树与二叉树的转换》.doc 21页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：250 &&
你可能关注的文档：
··········
··········
衡阳师范学院
《数据结构》课程设计
树与二叉树的转换
计算机科学系
计算机科学与设计
1302学生姓名：
1指导老师：
完成日期：
一．需求分析.…………………………………………………………………3
二．概要设析………………………………………………………………….3
三．详细设计………………………………………………………………….5
的建立………………………………………………………………..5
2.一般树转化成二叉树…………………………………………………..6序遍历树的递归算法………………………………………………..7
4.后序遍历树的递归………………………………………………..75.先序遍历树的非递归算法……………………………………………..7序遍历树的非递归算法……………………………………………..8
7.序非递归的算法…………………………………………………..设计与调试分析………………………………………………………….0
五．用户………………………………………………………………….10
六．测试结果………………………………………………………………….11附录程序）………………………………………………………….14总结……………………………………………………………………….20一.需求分析
本程序的功能是对任意树进行递归前序遍历和后序遍历，以及实现的用到的建立与二叉树的转换算法后序二叉树的递归递归算法序遍历算法
2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 BiNode creat()，BiNode stree_creat(char *a,int k)。
2一般树转化成二叉树void exchange()，class Tree
3先序遍历树的递归算法
1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。void PreOrder(BiNode root)。
4后序遍历树的递归算法
1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；void PostOrder(BiNode root)。5先序遍历树的非递归算法
1）先将根节点进栈，在栈不为空时循环2)出栈p，访问*p若右孩子节点不空将右孩子节点进栈若左不空时其左孩子节点进栈。的非递归算法
一个栈保存需要返回的指针，先扫描根节点所有的左孩子节点并一一进栈，出栈一个节点*b作为当前节点，然后扫描节点的右子树。当节点的左右孩子节点均访问后再访问节点，如此重复操作，直到栈空为止。序的遍历
LevelOrder(BiNode root)。
1树的建立PTree CreatTree(PTree T)
for(i=1;ch!=-1;i++)
printf(&输入第%d结点:\n&,i);
scanf(&%d,%d&,&fa,&ch);
printf(&\n&);
T.count++;T.node[T.count].data = p.T.node[T.count].parent = p.
printf(&\n&);
printf(&创建的树具体情况如下:\n&);
print_ptree(T);
2一般树转换成二叉树BTNode *change(PTree T)
int i,j=0;
BTNode p[MAX_TREE_SIZE];
BTNode *ip,*is,*ir,*T
ip=(BTNode *)malloc(sizeof(BTNode));
is=(BTNode *)malloc(sizeof(BTNode));
ir=(BTNode *)malloc(sizeof(BTNode));
Tree=(BTNode *)malloc(sizeof(BTNode));
for(i=0;i&T.i++)
p[i]=GetTreeNode(T.node[i].data);
for(i=1;i&T.i++)
while(T.node[i].parent!=is-&data)
正在加载中，请稍后...数据结构课程设计说明书 树的应用 树和二叉树的转换_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构课程设计说明书 树的应用 树和二叉树的转换
&&数据结构课程设计说明书 树的应用 树和二叉树的转换
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩24页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢要求：输入一棵二叉排序树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建新的结点，只能调整树中结点的指针的指向。如下图：
方法一：我们借助一个容器来顺序存储结点的指针，然后改变指针的指向。
1 //////////////////////二叉搜索树与双向链表（方法一）//////////////////////////////////////////
3 void Convertfirst(BinaryTreeNode* pRoot , vector&BinaryTreeNode*&& Vec)
if (pRoot)
Convertfirst(pRoot-&m_pLeft , Vec);
Vec.push_back(pRoot);
Convertfirst(pRoot-&m_pRight , Vec);
12 BinaryTreeNode* Convert1(BinaryTreeNode* pRoot)
if (!pRoot)
return NULL;
vector&BinaryTreeNode*& V
Convertfirst(pRoot ,Vec);
BinaryTreeNode* pHead = Vec[0];
vector&BinaryTreeNode*&::iterator it = Vec.begin();
for ( ; it != Vec.end()-1;it++)
(*it)-&m_pRight = (*(it+1)) ;
(*(it+1))-&m_pLeft = (*it) ;
方法二：我们边遍历边改变指针的指向。
1 //////////////////////二叉搜索树与双向链表（方法二）//////////////////
2 void ConvertNode(BinaryTreeNode* pNode , BinaryTreeNode** pLastNodeList)
if (pNode)
ConvertNode(pNode-&m_pLeft , pLastNodeList);
pNode-&m_pLeft = *pLastNodeL
if (*pLastNodeList != NULL)
(*pLastNodeList)-&m_pRight = pN
*pLastNodeList = pN
ConvertNode(pNode-&m_pRight , pLastNodeList);
17 BinaryTreeNode* Convert2(BinaryTreeNode* pRoot)
if (!pRoot)
return NULL;
BinaryTreeNode* pLastNodeList = NULL ;
ConvertNode(pRoot ,&pLastNodeList);
while (pLastNodeList && pLastNodeList-&m_pLeft)
pLastNodeList = pLastNodeList-&m_pL
return pLastNodeL
阅读(...) 评论()