• 森林转化为二叉树
千次阅读
2016-08-06 14:30:19

森林结构及转化后的二叉树结构如图所示：

代码如下：

#ifndef _TREE_H
#define _TREE_H

#include <iostream>
using namespace std;

template <typename T>
class Tree;

template <typename T>
class TreeNode{
friend class Tree<T>;
public:
TreeNode() :m_data(T()), firstChild(NULL), nextSibling(NULL)
{}
TreeNode(T data) :m_data(data), firstChild(NULL), nextSibling(NULL)
{}
private:
T m_data;
TreeNode<T> *firstChild;
TreeNode<T> *nextSibling;
};

template <typename T>
class Tree{
typedef TreeNode<T> node_type;
public:
Tree() = default;
Tree(T ref) :refval(ref), root(NULL)
{}
public:
void init_tree(const char* str);
void preorder_traverse()const;

int Size()const;
int Height()const;
node_type* Root()const;
node_type* Find(const T&)const;
node_type* Parent(node_type *)const;
bool is_empty()const;
protected:
void init_tree(node_type *&, const char *&);
void preorder_traverse(node_type *)const;

int Size(node_type *)const;
int Height(node_type *)const;
node_type* Find(node_type *, const T&)const;
node_type* Parent(node_type *, node_type *)const;
private:
node_type *root;
T refval;
};

//public interface

template <typename T>
void Tree<T>::init_tree(const char* str)
{
init_tree(root, str);
}

template <typename T>
void Tree<T>::preorder_traverse()const
{
preorder_traverse(root);
}

template <typename T>
int Tree<T>::Size()const
{
return Size(root);
}

template <typename T>
int Tree<T>::Height()const
{
return Height(root);
}

template <typename T>
TreeNode<T>* Tree<T>::Root()const
{
return root;
}

template <typename T>
TreeNode<T>* Tree<T>::Find(const T& val)const
{
return Find(root, val);
}

template <typename T>
TreeNode<T>* Tree<T>::Parent(node_type *cur)const
{
return Parent(root, cur);
}

template <typename T>
bool Tree<T>::is_empty()const
{
return root == NULL;
}

//protected interface

template <typename T>
void Tree<T>::init_tree(node_type *&t, const char *&str)
{
if(*str == refval){
t = NULL;
return ;
}
else{
t = new node_type(*str);
init_tree(t->firstChild, ++str);
init_tree(t->nextSibling, ++str);
}
}

template <typename T>
void Tree<T>::preorder_traverse(node_type *t)const
{
if(t == NULL)
return ;

cout << t->m_data << " ";
preorder_traverse(t->firstChild);
preorder_traverse(t->nextSibling);
}

template <typename T>
int Tree<T>::Size(node_type *t)const
{
if(t == NULL)
return 0;
else
return 1 + Size(t->firstChild) + Size(t->nextSibling);
}

template <typename T>
int Tree<T>::Height(node_type *t)const
{
if(t == NULL)
return 0;
if(t->firstChild == NULL)
return 1;

int m_current;
int max = 0;

auto tmp = t->firstChild;
while(tmp != NULL){
m_current = Height(tmp);
if(m_current > max)
max = m_current;

tmp = tmp->nextSibling;
}

return max + 1;
}

template <typename T>
TreeNode<T>* Tree<T>::Find(node_type *t, const T& val)const
{
if(t == NULL)
return NULL;
if(t->m_data == val)
return t;

auto tmp = Find(t->firstChild, val);
if(tmp == NULL)
tmp = Find(t->nextSibling, val);

return tmp;
}

template <typename T>
TreeNode<T>* Tree<T>::Parent(node_type *t, node_type *cur)const
{
if(t == NULL || cur == NULL || t == cur)
return NULL;
if(t->firstChild == cur)
return t;

auto p = t->firstChild;
while(p != NULL && p != cur){
auto tmp = Parent(p, cur);
if(tmp != NULL)
return tmp;

p = p->nextSibling;
}

if(p != NULL && p == cur)
return t;
else
return NULL;
}

#endif


更多相关内容
• ⑴)加线——树中所有相邻兄弟之间加一条连线。 (2)去线——对树中的每个结点，只保留它...(3)层次调整——以根结点轴心，将树顺时针转动一定的角度，使之层次分明。 第三点可以直接记“左是孩子，右是兄弟” ...

一、树转化为二叉树：

加线——树中所有相邻兄弟之间加一条连线。·

(2)去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。

(3)层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。

第三点可以直接记为“左是孩子，右是兄弟”

例：

二、森林转化为二叉树：

(1)将森林中的每一棵树转化为二叉树；

(2)第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根节点的右孩子。

例：

三、二叉树转化为树和森林：

(1)加线——若某结点x是其双亲y左孩子，则把结点x的右孩子右孩子的右孩子……，都与结点y用线连起来；

(2)去线——删去原二叉树中所有的双亲结点右孩子结点的连线；

(3) 层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。

例：

四、树的遍历

先根(次序)遍历:

若树不空，则先访问根结点，然后依次先根遍历各棵子树。

后根(次序)遍历:

若树不空，则先依次后根遍历各棵子树，然后访问根结点。

五、森林的遍历

1、森林中第一棵树的根结点；

2、森林中第一棵树的子树森林；

3、森林中其它树构成的森林。

1.先序遍历：

若森林不空，则：

访问森林中第一棵树的根结点;

先序遍历森林中第一棵树的子树森林;

先序遍历森林中(除第一棵树之外)其余树构成的森林。

即：依次从左至右对森林中的每一棵进行先根遍历

2.中序遍历：

若森林不空，则

中序遍历森林中第一棵树的子树森林;

访问森林中第一棵树的根结点;

中序遍历森林中(除第一棵树之外)其     余树构成的森林。

即：依次从左至右对森林中的每一棵进行后根遍历

展开全文
• 先实现二叉树，再实现森林，希望给出更好的方法

孩子兄弟表示法的理解与代码实现|树转化为二叉树
森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是：
（1）先把每棵树转换为二叉树；
（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

# 森林转化为二叉树的实现

网上这个例子代码没找到几个
自己想了想方法有这几个
1.把多个树变为森林，当你将树转化为二叉树的时候，紧接着可以在根结点的右孩子那输入新的树，这样就完成了森林的构造。

2.依次将树转化为二叉树，然后判断第一个树（二叉树形式）的右孩子是否存在，（应该是不存在）然后将第二个树的根结点作为第一个树的右孩子这样就连接了。

根据树的数量重复上面操作。

Status CreatForst(Node &T1, Node &T2)
{

if (T1->next_sib != NULL)
{
CreatForst(T1->next_sib,T2);

}
else
{
T1->next_sib = T2;
//return 0;
}
return 0;
}


加上上面这个部分就行
孩子兄弟表示法的理解与代码实现|树转化为二叉树

展开全文
• 一、将树转换为二叉树： 树中每个结点最多只有一个最左边的孩子...二、将一个森林转换为二叉树： 具体方法是：1.将森林中的每棵树变为二叉树； 2.因为转换所得的二叉树的根结点的右子树均空，故可将各二叉树的根结...

一、将树转换为二叉树：
树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：
1.在所有兄弟结点之间加一连线
2.对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。
如下图所示：

二、将一个森林转换为二叉树：
具体方法是：1.将森林中的每棵树变为二叉树；
2.因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
如下图所示：

三、二叉树转换为树：
是树转换为二叉树的逆过程。
1.加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。
2.去线。删除原二叉树中所有结点与其右孩子结点的连线。
如下图所示：

四、二叉树转换为森林：
假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。
1.从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。
2.将每棵分离后的二叉树转换为树。
如下图所示：

展开全文
• 数据结构14————树,森林转化为二叉树(孩子兄弟表示法) 1.树转换二叉树 2.森林转换为二叉树 3.二叉树转森林和树 4.森林和树的遍历 5.二叉森林树的应用
• 具体方法是： 1.将森林中的每棵树变为二叉树； 2.因为转换所得的二叉树的根结点的右子树均空，故可将各二叉树的根结点视兄弟从左至右连在一起，就形成了一棵二叉树。 如下图所示： ...
• 一般树转化为二叉树方法 设法保证任意一个节点的左指针域指向它的第一个孩子，右指针...森林是由树组成，所以只需要将森林里面的树转化为二叉树存储即可，树与树的根节点当作兄弟节点处理 转为为二叉树 ...
• ## 树、森林转化为二叉树

千次阅读 多人点赞 2016-12-29 12:12:34
森林转换为二叉树的画法树转换为二叉树的画法1.在兄弟节点之间加一连线；2.对每一个节点，只保留它与第一个子节点的连线，与其他自己节点的连线全部抹掉；3.以树根轴心，顺时针旋转45度。森林转换为二叉树的画法1....
• 文章目录借助孩子兄弟表示法把树，森林转换为二叉树把普通树转换为二叉树森林转换为二叉树 借助孩子兄弟表示法把树，森林转换为二叉树 树的孩子兄弟表示法可以把任何树存储一个二叉链表，即每个结点只有两个指针域...
• 算法主要还是使用递归，首先将森林问题拆解成树的问题（具体原理这里不过多赘述，重点在于动手实践），然后树转二叉树的过程需要递归往左走，再处理兄弟，难点在于三种数据结构的转换。 #include<iostream>
• 2 森林转换成二叉树 3 思路：u的孩子节点v1, v2, v3....（v1,v2,....互为兄弟节点） 4 那么将u的一个孩子节点（v1）连在u的左子树上，那么其他的孩子节点都连在v1的右子树上！ 5 */ 6 #include<...
• package main import ( "unsafe" "fmt" ) type TreeNode struct { x int childs []*TreeNode } type Tree TreeNode type BTreeNode struct { x int ...type BTree ...
• 先说结论：树变二叉根相连。（每一棵树都先变成二叉树，然后把根节点连起来即可。） 前言：那树怎么变二叉树呢？结论：兄弟相连，留长子，绕根节点旋转45° ...将下面3棵树组成的森林转换为二叉树 ...
• 1、树转换为二叉树 （1）加线。在所有兄弟结点之间加一条线。 （2）去线。对树中每个结点，只保留它与第一个孩子结点的连线，...2、森林转换为二叉树 （1）把每棵树转换为二叉树。 （2）第一棵二叉树不动，从第二棵二
• 文章目录树转换为二叉树 树转换为二叉树二叉树和树都可以用二叉链表作为存储结构，因此二叉链表可以导出树与二叉树的一个对应关系，即给定一棵树，可以找到唯一的一棵二叉树与之对应。其中树的二叉链表存储详情可...
• 1、树转换为二叉树 由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。 将树转换成二叉树的步骤是： （1）加线。就是在所有兄弟结点之间加一条连线； ...
• 森林二叉树的过程是这样的： （1）把每棵树转换为二叉树。 （2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线连接起来。 所以转换后的二叉树的...
• C语言森林转换成二叉树二叉树转换成森林等的递归算法。 假定普通树采用定长结点结构，而二叉树采用二叉链表结构 (1) 树转换成二叉树的算法： (i) 将原树的根结点转换为二叉树的根结点; (ii) 将原树根结点的所有...
• 森林二叉树转换树转换成二叉树森林转换成二叉树二叉树转换二叉树还原为森林树与森林的遍历树的遍历树的前序遍历定义：树的后序遍历定义：森林遍历前序遍历后序遍历 线索二叉树 定义 n个结点的二叉链表中含有n+...
• 树、森林二叉树的转换 ...2.森林转换为二叉树 森林是由若干棵树组成，可以理解森林中的每一棵树都是兄弟，可以按照兄弟的处理方法来操作。将森林转换成二叉树的步骤如下： 把每棵树转换成二叉树。 第一棵
• 孩子兄弟表示法使每个结点包括三个内容：结点值、指向结点第一个孩子的结点的指针，及指向结点下一个兄弟结点的指针（沿此区域可以找到结点的所有兄弟结点） 将下面一个有三棵树组成的森林转换为二叉树 转换规则，左...
• 给定一组森林，编写程序生成对应的二叉树，输出这颗二叉树叶结点对应的二进制编码.规定二叉树的左边由0表示，二叉树的右边由1表示。 输入 输入： N B 表示N个树，每结点最多B个分支 第2行至第N+1行，每个树的...
• ③以第一棵树根结点为二叉树的根，再以根结点轴心，顺时针旋转，构成二叉树型结构 森林二叉树口诀 :树变二叉根相连。 eg 二叉树转换成森林 ①抹线:将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有...
• 数据结构，树、森林二叉树的转换详解，树和森林的遍历详解。
• 二叉树结点的数目： void Count(BiNode *root){ if (root) { Count(root->lchild); number+ +; //number数据成员 Count(root->rchild); } } 树中结点的数目等于左子树结点的数目加上右子树结点的数目加1...

...