二叉树的根节点同时有左右孩子怎么转化成森林

森林和二叉树转换的c或c++代码~

你好，尊敬的百度知道用户楼主，很愿意为你问题作答

1、转换：将森林中的每棵树转换成二叉树； 2、连线：第一颗树不动，从第二棵树开始，依次把后一棵树的根节点座位前一棵树的根节点的右孩子，知道所有的二叉树都连在一起，即完成了森林向二叉树的转换。 3、旋转：以根节点为轴心，将整棵树顺时针旋转一定角度，得到层次分明的二叉树。

将一棵二叉树转化成森林，可按如下步骤进行：
①抹线：将二叉树根结点与其右孩子之间的连线，以及沿着此右孩子的右链连续不继搜索到的右孩子间的连线抹掉。这样就得到了若干棵根结点没有右子树的二叉树。
②将得到的这些二叉树用前述方法分别转化成一般树。

首先你要对一些基本概念掌握清楚。祝你好运！！

树转化为二叉树时结点左子树是原来的孩子结点，右子树是原来的兄弟结点。即取根节点左孩子向右连接他的兄弟结点（在同一层次的节点，原来互不相连）并把它的子树，而把除左孩子外，原来与根节点相连的线擦除。这样根节点没有右孩子，因为由树转化来的二叉树某个节点A的左子树是原来作为树时A的孩子，其右子树是他的兄弟。
希望你能看懂~~

[二叉树]
        A
     /     \
    B       C
   / \     / \
  D   E   F   G
     / \   \   \
    H   I   J   K
     \   \       \
      L   M       N

(1) [二叉树]的根节点是A,而A的右分支是C G K N, 先将右分支分离,得到5棵二叉树:

    [第1棵二叉树]
        A
       / 
      B
     / \ 
    D   E
       / \
      H   I
       \   \
        L   M


    [第2棵二叉树]
         C
        /
       F
        \
         J


    [第3棵二叉树],[第4棵二叉树],[第5棵二叉树]都只有一个根节点,分别是G,K,N :
     G    K    N


(2) 将这5棵二叉树分别转化为对应的[树]:

    [第1棵二叉树]的根节点是A,其左分支是B,而B的右分支是E,I,M,将B,E,I,M转化为兄弟节点,
    它们的父节点是A,而节点E有左分支H,而H有右分支L,将H和L转化为兄弟节点,它们的父节点是E,
    而节点B仍然是D的父节点, 得到[森林]的[第1棵树]:

           A
     /    / \  \
    B    E   I  M
    |   / \
    D  H   L


    [第2棵二叉树]的根节点是C,其左分支是F,而F的右分支是J,将F和J转化为兄弟节点,
    它们的父节点是C, 得到[森林]的[第2棵树]:

       C
      / \
     F   J


    [第3棵二叉树]只有一个根节点,转化为[森林]的[第3棵树]:
     G

    [第4棵二叉树]只有一个根节点,转化为[森林]的[第4棵树]:
     K

    [第5棵二叉树]只有一个根节点,转化为[森林]的[第5棵树]:
     N

题目所示的[二叉树],转化成的[森林]就是由上述5棵树组成:

           A            C      G    K    N
     /    / \  \       / \
    B    E   I  M     F   J
    |   / \
    D  H   L

---

黑河市17062289538： 求一个二叉树转化成树的算法,包括根节点有右孩子的,怎么转化成树.注意不是转化成森林..只是转成树 - ？
庾栏津止： 首先要知道 树(森林)转换成二叉树的方法.一般是把树(森林)当前结点的的孩子当成左子树(或右子树),层层转换而得到一个新的二叉树.根据树(森林)转换二叉树的方法,逆向回去,就可以得到二叉树转换树的算法.【以下资料的算法】:是把当前结点的孩子当成左子树,兄弟结点当成右子树.

黑河市17062289538： 数据结构与算法 二叉树交换左右子树算法 - ？
庾栏津止： 传入树的根结点即可: exchangeLR(&root); //root为树的根节点void exchangeLR(TreeNode *root) {TreeNode *tmp;if (root == NULL)return;// 左子树交换exChangeLR(root->left);// 右子树交换exChangeLR(root->right);// 交换当前结点的左右子树tmp = root->left;root->left = root->right;root->right = tmp; }

黑河市17062289538： 数据结构,如何将二叉树中所有结点的左、右子女互换? - ？
庾栏津止： void swapNode(node *root) { if(root==NULL) return;swapNode(root->left); swapNode(root->right);node* temp = root->left; root->left = root->right; root->right = temp;}典型的遍历树的问题,你得补课了.

黑河市17062289538： 根结点有右孩子的二叉树能否转换为树而不是指森林 - ？
庾栏津止： 可以,一个二叉树可以分成很多个树

黑河市17062289538： 二叉树中如何交换左右子树? - ？
庾栏津止： 使用遍历,每遍历到一个结点,就交换其左右子树 void Swap(bnode *root) {// 使用后序遍历 bnode *temp; if (root != NULL) { Swap(root->lchild): Swap(root->rchild); temp = root->lchild;root->lchild = root->rchild; root->rchild = temp; }}

黑河市17062289538： 编写一个算法,将二叉树中每个结点的左右孩子交换. - ？
庾栏津止： 从根节点开始,对每个节点,左右孩子互换,对他们递归该过程

黑河市17062289538： 如何删除二叉树的节点(该节点有左右孩子,且左右孩子也有左右孩子) - ？
庾栏津止： // S_dt_ecpxs.cpp : 定义控制台应用程序的入口点.//动态查找表 二叉排序树的插入和删除#include ＂stdafx.h＂#include＂stdio.h＂#include＂string.h＂#include＂malloc.h＂ typedef int ElemType; //定义 typedef struct BiTNode{ int data; struct ...

黑河市17062289538： 数据结构的树和二叉树之间怎么转换?？
庾栏津止： 由根结点往下,如果有多个孩子那么这一层的孩子都作为本层第一个结点的右孩子的右孩子的右孩子……而本层第一个结点则作为它们双亲结点的左孩子,比如一个只有两层四个结点的树,变换完了以后就变成:根结点-》往左有一个孩子-》往右一个孩子-》继续往右一个孩子 这样的折线型

黑河市17062289538： 数据结构的树和二叉树之间怎么转换? - ？
庾栏津止： 将树转换成二叉树:① 加线:在兄弟之间加一连线 ② 抹线:对每个结点,除了其左孩子外,去除其与其余孩子之间的关系 ③ 旋转:以树的根结点为轴心,将整树顺时针转45° 将二叉树转换成树:① 加线:若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子……沿分支找到的所有右孩子,都与p的双亲用线连起来 ② 抹线:抹掉原二叉树中双亲与右孩子之间的连线 ③ 调整:将结点按层次排列,形成树结构

黑河市17062289538： 树怎么转化为二叉树 - ？
庾栏津止： 1、去除所有父结点也孩子结点连线; 2、把父结点与最左边的孩子相连,作为父结点的左孩子; 3、把同层结点的兄弟结点相连作为左边兄弟的右孩子; 以此类推所有结点即得到二叉树.