森林转化为二叉树c源码（森林如何转化成二叉树）
本文目录一览：
- 1、在C++中如何将森林转换为二叉树呢?
- 2、数据结构中,怎么样把森林转化成二叉树
- 3、怎么将一个森林转化为二叉树 谁能给我一个例子
- 4、用c语言来完成”森林到二叉树“的转换。。。
- 5、《森林与二叉树的转换》C语言代码
- 6、森林与二叉树的转换
在C++中如何将森林转换为二叉树呢?
1、转换：将森林中的每棵树转换成二叉树； 2、连线：第一颗树不动，从第二棵树开始，依次把后一棵树的根节点座位前一棵树的根节点的右孩子，知道所有的二叉树都连在一起，即完成了森林向二叉树的转换。 3、旋转：以根节点为轴心，将整棵树顺时针旋转一定角度，得到层次分明的二叉树。 首先你要对一些基本概念掌握清楚。祝你好运！！
数据结构中,怎么样把森林转化成二叉树
步骤1：先将各树按照左孩子右兄弟的原则转化成二叉树
步骤2：然后将各二叉树通过根的右指针相连（即：按森林图形中树的先后次序，依次将后边一棵二叉树的根作为前边一棵二叉树根结点的右子树）
下面给你举个例子：
怎么将一个森林转化为二叉树 谁能给我一个例子
将森林中每棵树的根节点作为二叉树的根节点森林转化为二叉树c源码，每个节点中的从左数第一个孩子是二叉树中的左孩子森林转化为二叉树c源码，该孩子的所有兄弟都依次为该节点的有孩子
，如此例推。
用c语言来完成”森林到二叉树“的转换。。。
这是C++森林转化为二叉树c源码的
typedef struct BinaryTreeNode{
struct BinaryTreeNode* leftChild;
struct BinaryTreeNode* rightChild;
int value;
};
typedef struct TreeNode{
struct TreeNode* child[];
int child_count;
int value;
};
BinaryTreeNode* ToBinaryTree(TreeNode* root){
if(root == null)
return null;
BinaryTreeNode* binaryRoot = new BinaryTreeNode();
binaryRoot-value = root-value;
binaryRoot-leftChild = ToBinaryTree(root-child[0]);
BinaryTreeNode* brother = binaryRoot-leftChild;
for(int i = 1; i root-child_count;i++){
brother-rightChild = ToBinaryTree(root-child[i]);
brother = brother-rightChild;
}
return binaryRoot;
}
《森林与二叉树的转换》C语言代码
#includestdio.h
#includemalloc.h
#define DEGREE 5 //树的高度
#define NULL 0
#define QUEUESIZE 10
#define MAX_NODE_NUM 100
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@树和二叉树的结构体@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
typedef struct st1//树节点的类型
{
char data;//数据域，采用char星
struct st1 *children[DEGREE];//指向孩子节点的指针域
}CTreeNode;
typedef struct st2
{
char data;//数据域
struct st2 *lchild,*rchild;//左右孩子节点的指针
}BTreeNode;
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@查找树的节点@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
CTreeNode *SearchCTree(CTreeNode *root ,char data)
{
int i;
CTreeNode *returnNode;
if(root-data==data)
return root;
else
{
for(i=0;iDEGREE;i++)
{
if(root-children[i]==NULL)
return NULL;
else
{
returnNode=SearchCTree(root-children[i],data);//递归查找
if(returnNode!=NULL)
return returnNode;
}
}
}
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@生成树@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
CTreeNode *CreateSTree()
{
int i,j,k;
char data, parent;;
CTreeNode *root,*parentNode,*node;
printf("请输入树的节点的数量:");
scanf("%d",j);
fflush(stdin);//清除键盘缓存
if(j==0)
return NULL;//空树，结束函数
printf("请输入根节点的数据:");
scanf("%c",data);
fflush(stdin);
root=(CTreeNode *)malloc(sizeof(CTreeNode));
root-data=data;
for(i=0;iDEGREE;i++)
root-children[i]=NULL;
for(i=2;i=j;i++)//依次输入每个节点的信息
{
printf("请输入第%d个节点的数据及其父节点的数据:",i);
scanf("%c%c",data,parent);//切记当以%c号格式输入数据时候，不要输入空格
fflush(stdin);
node=(CTreeNode *)malloc(sizeof(CTreeNode));
node-data=data;
for(k=0;kDEGREE;k++)
node-children[k]=NULL;
//printf("验证parent=%c\n",parent);
parentNode=SearchCTree(root,parent);//查找指定数据的节点
for(k=0;kDEGREE;k++)
{
if(parentNode-children[k]==NULL)
{
parentNode-children[k]=node;
break;
}
}
}
return root;
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@树的遍历@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void preorderTree(CTreeNode *ctroot)//遍历每个节点的操作就是输出该节点的data域
{
CTreeNode *ctchild;
int i;
printf("%c",ctroot-data);//先遍历根节点
for(i=0;iDEGREE;i++)//依次先序遍历孩子节点
{
ctchild=ctroot-children[i];
if(ctchild==NULL)
break;//孩子节点遍历结束，退出
else
preorderTree(ctchild);//递归先序遍历
}
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@结构体类型@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
//树队列结构体类型
typedef struct nodeCTree
{
CTreeNode *CTreeArray[MAX_NODE_NUM];//结构体指针数组，存放节点的地址
//struct nodeCTree *next;
int CTreeFront,CTreeRear;
}QueueCTree;
//二叉树队列结构类型
typedef struct nodeBTree
{
BTreeNode *BTreeArray[MAX_NODE_NUM];//结构体指针数组，存放节点的地址
//struct nodeBTree *next;
int BTreeFront,BTreeRear;
}QueueBTree;
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@初始化队列@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
//初始化树队列
void initQueueCTree(QueueCTree *q)
{
q=(QueueCTree *)malloc(sizeof(QueueCTree));
q-CTreeFront=q-CTreeRear=0;
}
//初始化二叉树队列
void initQueueBTree(QueueBTree *q)
{
q=(QueueBTree *)malloc(sizeof(QueueBTree));
q-BTreeFront=q-BTreeRear=0;
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@入队列@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
//树队列元素入队
int addQueueCTree(QueueCTree *q,CTreeNode *ctroot)//
{
if((q-CTreeRear+1)%MAX_NODE_NUM==q-CTreeFront)//队满
return 0;
q-CTreeRear=(q-CTreeRear+1)%MAX_NODE_NUM;
q-CTreeArray[q-CTreeRear]=ctroot;
return 1;//入队列
}
//二叉树队列元素入队
int addQueueBTree(QueueBTree *q,BTreeNode *btroot)
{
if((q-BTreeRear+1)%MAX_NODE_NUM==q-BTreeFront)//队满
return 0;
q-BTreeRear=(q-BTreeRear+1)%MAX_NODE_NUM;
q-BTreeArray[q-BTreeRear]=btroot;
return 1;//入队列
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@队列判空@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
//树的队列判空
int QueueCTreeEmpty(QueueCTree *q)
{
return(q-CTreeFront==q-CTreeRear);
}
//二叉树队列判空
int QueueBTreeEmpty(QueueBTree *q)
{
return(q-BTreeFront==q-BTreeRear);
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@出队列@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
//树队列元素出队
CTreeNode *delQueueCTree(QueueCTree *q)
{
CTreeNode *ctroot;
if(q-CTreeFront==q-CTreeRear)//队空
return NULL;//返回空指针
q-CTreeFront=(q-CTreeFront+1)%MAX_NODE_NUM;
ctroot=q-CTreeArray[q-CTreeFront];
return ctroot;//返回节点
}
//二叉树队列元素出队
BTreeNode *delQueueBTree(QueueBTree *q)
{
BTreeNode *btroot;
if(q-BTreeFront==q-BTreeRear)//队空
return NULL;//返回空指针
q-BTreeFront=(q-BTreeFront+1)%MAX_NODE_NUM;
btroot=q-BTreeArray[q-BTreeFront];
return btroot;//返回节点
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@树转化为二叉树@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
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=(BTreeNode *)malloc(sizeof(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;iDEGREE;i++)//访问节点所有的孩子节点
{
if(ctnode-children[i]==NULL)//孩子节点访问完毕
break;
p=(BTreeNode *)malloc(sizeof(BTreeNode));//分配二叉树节点
p-data=ctnode-children[i]-data;
p-lchild=p-rchild=NULL;
if(i==0)
btnode-lchild=p;//长子，作为父节点的做孩子
else
LastSibling-rchild=p;//作为上一个兄弟节点的右孩子
LastSibling=p;
addQueueCTree(VisitedCTreeNodes,ctnode-children[i]);//树节点进队列
addQueueBTree(VisitedBTreeNodes,p);//二叉树节点进门队列
}
}
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@二叉树的遍历@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
void Preorder(BTreeNode *T)
{
if(T)
{
printf("%2c",T-data);
Preorder(T-lchild);
Preorder(T-rchild);
}
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@主函数调用@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
int main()
{
CTreeNode *Tree;
BTreeNode *BTree;
printf("创建一棵树\n");
Tree=CreateSTree();
printf("树的先序遍历结果为:");
preorderTree(Tree);
printf("\n");
TreeToBTree(Tree,BTree);
printf("转换后的二叉树，先序遍历的结果为:");
Preorder(BTree);
printf("\n");
return 0;
}
森林与二叉树的转换
1、 树、森林转换成二叉树 将一棵树转换成二叉树森林转化为二叉树c源码的方法森林转化为二叉树c源码： 将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可森林转化为二叉树c源码，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。 特点：一棵树转换成二叉树后，根结点没有右孩子。 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。 2 、二叉树还原成树或森林 这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。 提问者 的感言： 举个例子就最好了，还是要谢谢你。
