C++和Python混合编程进阶-二叉树转换为普通树
视频教程：C++和Python混合编程进阶
Git: https://github.com/JasonLiThirty/C-andPython
本期主要是通过数据结构里的二叉树转化成普通树的例子来应用C++和Python之间的数据交互和脚本调用，同时呢也将使用Python里的第三方可视化图形工具Graphviz将原始的二叉树和转换后产生的树进行可视化。
分为四个步骤，第一步是建立了一个名为TreeStructure的头文件，这个头文件使用C++实现了二叉树及其二叉节点的数据定义，普通树和普通树节点的数据定义，以及二叉树转换为普通树的方法。
第二步是为了让这些C++定义的数据结构和函数能够再Python中使用，我们需要再将它们进行导出，这里就需要用到之前的Python_Wrapper工程。
第三步是接着我们来构建两个Python脚本，一个是PythonTree脚本，完成树相关的操作，另一个是TreeVisual.py来进行数据结构可视化
最后一步是通过Python_Invoker_Module来调用PythonTree脚本来完成我们的功能。
TreeStructure
首先建立了一个名为TreeStructure的头文件，这个头文件使用C++实现了二叉树及其二叉节点的数据定义，普通树和普通树节点的数据定义，以及二叉树转换为普通树的方法。
先来看下二叉节点BinaryNode的结构，我们定义的是一个泛型节点，它包含也给泛型的数据成员data和分别指向左子节点和右子节点的指针。
然后是二叉树BinaryTree的结构，它包含一个根节点的指针以及一个泛型的忽略标志，根节点很好理解，通过这个根节点和前序遍历方法就能够遍历整个树。忽略标志的含义是在用前序遍历列表来构建二叉树时，如果遇到了这个忽略标志，表示不建立该节点。
来看下用前序遍历列表来构建二叉树的方法GenerateByPreorder，可以看到，这是一个递归函数，每次都是从前序遍历的构造列表中取出一个值，如果该值不等于忽略标志，就建立这个节点，然后建立它的左子节点和右子节点，一直递归下去直到所有节点建立完成。
同时，二叉树BinaryTree还包含了前序，中序，后序遍历的方法。
#include<list>
#include<queue>
#include<iostream>
template<typename T>
struct BinaryNode
{
public:
BinaryNode(T info, BinaryNode<T> *left = nullptr, BinaryNode<T> *right = nullptr) :
data(info), leftChild(left), rightChild(right) {}
T data;
BinaryNode<T> *leftChild;
BinaryNode<T> *rightChild;
};
template<typename T>
class BinaryTree
{
public:
BinaryTree(BinaryNode<T> *node) :m_rootNode(node) {}
BinaryTree(T flag) : m_rootNode(nullptr)
{
m_ignoreSign = flag;
}
~BinaryTree() { Free(m_rootNode); }
void GenerateByPreorder(std::list<T> &nodeList)
{
GenerateByPreorder(nodeList, m_rootNode);
}
void Preorder()
{
Preorder(m_rootNode);
}
void Inorder()
{
Inorder(m_rootNode);
}
void Postorder()
{
Postorder(m_rootNode);
}
BinaryNode<T> *Root()
{
return m_rootNode;
}
private:
void Free(BinaryNode<T> *node)
{
if (node != nullptr)
{
Free(node->leftChild);
Free(node->rightChild);
delete node;
node = nullptr;
}
}
void GenerateByPreorder(std::list<T> &nodeList, BinaryNode<T> *&node)
{
if (!nodeList.empty())
{
auto item = nodeList.front();
nodeList.pop_front();
if (item != m_ignoreSign)
{
node = new BinaryNode<T>(item);
GenerateByPreorder(nodeList, node->leftChild);
GenerateByPreorder(nodeList, node->rightChild);
}
else
{
node = nullptr;
}
}
}
void Preorder(BinaryNode<T> *&node)
{
if (node != nullptr)
{
std::cout << node->data << "";
Preorder(node->leftChild);
Preorder(node->rightChild);
}
}
void Inorder(BinaryNode<T> *&node)
{
if (node != nullptr)
{
Inorder(node->leftChild);
std::cout << node->data << "";
Inorder(node->rightChild);
}
}
void Postorder(BinaryNode<T> *&node)
{
if (node != nullptr)
{
Postorder(node->leftChild);
Postorder(node->rightChild);
std::cout << node->data << "";
}
}
private:
BinaryNode<T> *m_rootNode;
T m_ignoreSign;
};
接着看下普通书节点TreeNode的结构，同样它也是一个泛型节点，包含了泛型的数据成员data和包含子节点的列表childList。。
然后是树Tree的结构，它只包含一个根节点的指针，通过广度优先遍历，即层优先遍历就可以遍历整个树。来看下用广度优先遍历方法Levelorder，它使用了两个列表来完成遍历，container作为临时存储器，先将根节点放入container的尾部，如果container不为空，从头部取出某节点放入levelList列表，同时再将这个节点所有的子节点放入container的尾部，一直重复，直到container为空，最终levelList列表里存储的就是通过广度优先遍历得到的节点顺序。
template<typename T>
struct TreeNode
{
public:
TreeNode(T info) : data(info) { childList.clear(); }
T data;
std::list<TreeNode<T>*> childList;
};
template<typename T>
class Tree
{
public:
Tree()
{
m_rootNode = nullptr;
}
Tree(TreeNode<T>* node)
{
m_rootNode = node;
}
~Tree() { Free(m_rootNode); }
TreeNode<T> *Root()
{
return m_rootNode;
}
void Levelorder()
{
Levelorder(m_rootNode);
}
protected:
void Free(TreeNode<T> *node)
{
if (node != nullptr)
{
for (auto child : node->childList)
{
Free(child);
}
delete node;
node = nullptr;
}
}
private:
void Levelorder(TreeNode<T> *&node)
{
std::list<TreeNode<T>*> levelList;
std::list<TreeNode<T>*> container;
if (node == nullptr)
{
return;
}
if (node != nullptr)
{
container.push_back(node);
while (container.size() > 0)
{
TreeNode<T>* tNode = container.front();
levelList.push_back(tNode);
for (auto &child : tNode->childList)
{
container.push_back(child);
}
container.pop_front();
}
}
for (auto &item : levelList)
{
std::cout << item->data << "";
}
}
private:
TreeNode<T> *m_rootNode;
};
最后来看下二叉树转换为普通树的方法ConvertortoTree，二叉树转换成树的思想是，从二叉树的根节点开始，分为加线和删线两个步骤
加线的步骤是：如果结点的左子节点存在，则将左子节点的右子节点、这个右子节点的右子节点，一直沿着这条线上的所有节点都作为该结点的孩子结点，也就是将该结点与这些右子节点连接起来；
删线的步骤是：删除原二叉树中所有结点与其右子节点结点的连接；
这里需要说明的是，在这个示例中，因为我们是根据已有的二叉树来新构建一个普通树，所以只需要加线的步骤 ，另外我们是实现二叉树转换为普通树，而不是转换为森林，所以构建的二叉树的根节点是没有右子节点的。
template<typename T>
Tree<T>* ConverttoTree(BinaryTree<T>* BTree)
{
return new Tree<T>(ConvertortoTree(BTree->Root()));
}
template<typename T>
TreeNode<T>* ConvertortoTree(BinaryNode<T>* BNode)
{
if (BNode == nullptr)
{
return nullptr;
}
TreeNode<T>* node = new TreeNode<T>(BNode->data);
BinaryNode<T> *left = BNode->leftChild;
while (left != nullptr)
{
node->childList.push_back(ConvertortoTree(left));
left = left->rightChild;
}
return node;
}
C++调用测试
在Python_Invoker_Module的include目录设置里加入TreeStructure头文件所在的路径；输出目录也设置为TreeStructure头文件所在的路径。
在Python_Invoker_Module.cpp里我们写了一些调用语句，来测试以上的数据结构和方法是否有效
这里定义了一个前序遍历列表NList，用了构建一个二叉树
然后定义了一个string类型的二叉树bTree，忽略标志为星号，然后使用Nlist来初始化构建这个二叉树
然后调用bTree的Preorder，Inorder，Postorder函数来输出二叉树的前序遍历，中序遍历和后序遍历。
最后调用ConverttoTree函数来将二叉树转换为一个新构建的普通树，并输出这个普通树的广度优先遍历
std::list<std::string> NList{ "A", "B", "C", "*", "*", "D", "E", "*", "G", "H", "*", "*", "I", "*", "*", "F", "J", "*", "*", "*"};
BinaryTree<std::string> bTree("*");
bTree.GenerateByPreorder(NList);
std::cout << "----Preorder----" << std::endl;
bTree.Preorder();
std::cout << " " << std::endl;
std::cout << "----Inorder----" << std::endl;
bTree.Inorder();
std::cout << " " << std::endl;
std::cout << "----Postorder----" << std::endl;
bTree.Postorder();
std::cout << " " << std::endl;
std::cout << "----BTree Convert to Tree----" << std::endl;
std::shared_ptr<Tree<std::string>> tree(ConverttoTree<std::string>(&bTree));
tree->Levelorder();
参看下输出，可以看到，得到了我们想要的结果。
C++数据结构导出
为了让这些C++定义的数据结构和函数能够再Python中使用，我们需要将它们进行导出，这里就需要用到之前的Python_Wrapper工程（输出目录也设置为TreeStructure头文件所在的路径），按照之前的导出步骤，首先我们在
ExportDefinition头文件里，定义了一些需要导出的类和函数，这些类里面封装了TreeStructure里定义的二叉树及其节点，普通树及其节点，以及转换函数。
首先是定义的BNodeWrapper类，封装的是string类型的BinaryNode类，并且提供了接口函数Data()，Left()，Right()来得到BinaryNode里面的数据，左节点和右节点，还有判断是否有左，右节点的函数HaveLeft()和HaveRight()；
BTreeWrapper类封装的是string类型的BinaryTree类，并且提供构建利用前序列表来二叉树的方法Generate，以及前序Preorder()，中序Inorder()和后序Postorder()遍历接口函数。接口函数Tree用来得到真正封装的BinaryTree对象指针。Root函数得到的是BNodeWrapper类型的二叉树的根节点。
接下来是NodeWrapper，它封装的是string类型的TreeNode类，并且提供了接口函数Data()，Child()来得到BinaryNode里面的数据和子节点列表；
TreeWrapper类封装的是string类型的Tree类，并且提供广度优先遍历函数Leverorder()， Root函数得到的是NodeWrapper类型的普通树的根节点。
最后定义了BTreetoTree函数，实际上封装的是TreeStructure里面的ConverttoTree函数，只不过参数和返回值是我们定义的封装类BTreeWrapper和TreeWrapper的对象或指针。
class __declspec(dllexport) BNodeWrapper
{
public:
BNodeWrapper()
{
node.reset(new BinaryNode<std::string>(""));
}
BNodeWrapper(BinaryNode<std::string> *other)
{
node.reset(other);
}
std::string Data()
{
return node->data;
}
BNodeWrapper Left()
{
return BNodeWrapper(node->leftChild);
}
BNodeWrapper Right()
{
return BNodeWrapper(node->rightChild);
}
bool HaveLeft()
{
return (node->leftChild != nullptr);
}
bool HaveRight()
{
return (node->rightChild != nullptr);
}
private:
std::shared_ptr<BinaryNode<std::string>> node;
};
class __declspec(dllexport) BTreeWrapper
{
public:
BTreeWrapper(std::string flag)
{
bTree.reset(new BinaryTree<std::string>(flag));
}
void Generate(boost::python::list data)
{
std::list<std::string> NodeList;
for (int i = 0; i < boost::python::len(data); i++)
{
std::string value = boost::python::extract<std::string>(data[i]);
NodeList.push_back(value);
}
bTree->GenerateByPreorder(NodeList);
}
void Preorder()
{
bTree->Preorder();
}
void Inorder()
{
bTree->Inorder();
}
void Postorder()
{
bTree->Postorder();
}
BinaryTree<std::string>* Tree()
{
return bTree.get();
}
BNodeWrapper Root()
{
return BNodeWrapper(bTree->Root());
}
private:
std::shared_ptr<BinaryTree<std::string>> bTree;
};
class __declspec(dllexport) NodeWrapper
{
public:
NodeWrapper()
{
node.reset(new TreeNode<std::string>(""));
}
NodeWrapper(TreeNode<std::string> *other)
{
node.reset(other);
}
std::string Data()
{
return node->data;
}
boost::python::list Child()
{
boost::python::list childList;
for (auto &child : node->childList)
{
childList.append(NodeWrapper(child));
}
return childList;
}
private:
std::shared_ptr<TreeNode<std::string>> node;
};
class __declspec(dllexport) TreeWrapper
{
public:
TreeWrapper()
{
tree.reset(new Tree<std::string>());
}
TreeWrapper(Tree<std::string>* other)
{
tree.reset(other);
}
void Levelorder()
{
tree->Levelorder();
}
NodeWrapper Root()
{
return NodeWrapper(tree->Root());
}
private:
std::shared_ptr<Tree<std::string>> tree;
};
TreeWrapper* BTreetoTree(BTreeWrapper bTree)
{
return new TreeWrapper(ConverttoTree<std::string>(bTree.Tree()));
}
然后在Python_Wrapper里导出刚才定义的类及其成员函数，以及BTreetoTree函数，因为我们在BTreetoTree函数里new了新的对象，所以需要在导出时将boost::python::return_value_policy设置为boost::python::reference_existing_object，来表明新建了对象。
BOOST_PYTHON_MODULE(Python_Wrapper)
{
boost::python::class_<BNodeWrapper>("BNodeWrapper", boost::python::init<>())
.def("Data", &BNodeWrapper::Data)
.def("HaveLeft", &BNodeWrapper::HaveLeft)
.def("HaveRight", &BNodeWrapper::HaveRight)
.def("Left", &BNodeWrapper::Left)
.def("Right", &BNodeWrapper::Right);
boost::python::class_<BTreeWrapper>("BTreeWrapper", boost::python::init<std::string>())
.def("Generate", &BTreeWrapper::Generate)
.def("Preorder", &BTreeWrapper::Preorder)
.def("Inorder", &BTreeWrapper::Inorder)
.def("Postorder", &BTreeWrapper::Postorder)
.def("Root", &BTreeWrapper::Root);
boost::python::class_<NodeWrapper>("NodeWrapper", boost::python::init<>())
.def("Data", &NodeWrapper::Data)
.def("Child", &NodeWrapper::Child);
boost::python::class_<TreeWrapper>("TreeWrapper", boost::python::init<>())
.def("Levelorder", &TreeWrapper::Levelorder)
.def("Root", &TreeWrapper::Root);
boost::python::def("BTreetoTree", BTreetoTree, boost::python::return_value_policy<boost::python::reference_existing_object>());
}
Python脚本
接着我们来构建两个Python脚本
第一个是TreeVisual.py，这个脚本是用来将二叉树和普通树进行可视化的，脚本调用的graphviz库进行可视化，visualization函数是用来将原始的二叉树和转换后生成的普通树显示出来，关于可视化，这个视频就不做赘述了，以后在分享Python可视化相关知识时，再做详细的介绍。
import Python_Wrapper
from graphviz import Digraph
import datetime
NODE_ID = 0
def get_node_id():
global NODE_ID
NODE_ID += 1
return NODE_ID
def bnode_visual(graph, node, parent_id, is_root = False):
if node is not None:
id = str(get_node_id())
graph.node(id, node.Data())
if not is_root:
graph.edge(parent_id, id, splines='curved', fontsize='10', arrowType='vee')
if node.HaveLeft():
bnode_visual(graph, node.Left(), id)
if node.HaveRight():
bnode_visual(graph, node.Right(), id)
def btree_visual(btree_wrapper):
dot = Digraph('Binary Tree', filename='Binary Tree', engine='dot')
#dot.node_attr.update(style = 'filled', color='lightgrey')
root = btree_wrapper.Root()
bnode_visual(dot, root, 0, True)
#dot.render('visualization/btree_visual.gv', view=True)
return dot
def node_visual(graph, node, parent_id, is_root = False):
if node is not None:
id = str(get_node_id())
graph.node(id, node.Data())
if not is_root:
graph.edge(parent_id, id, splines='curved', fontsize='10', arrowType='vee')
for child in node.Child():
node_visual(graph, child, id)
def tree_visual(tree_wrapper):
dot = Digraph('Tree', filename='Tree', engine='dot')
root = tree_wrapper.Root()
node_visual(dot, root, 0, True)
#dot.render('visualization/tree_visual.gv', view=True)
return dot
def arrow_visual():
dot = Digraph('Arrow', filename='Arrow', engine='dot')
dot.node('arrow', 'Conversion', width = '5' ,fontname = 'bold', fontsize='20', style = 'filled', color = 'lightgrey', shape = 'rarrow')
return dot
def visualization(btree_wrapper, tree_wrapper):
graph = Digraph('Visual', comment='Visual', engine='dot')
graph.subgraph(btree_visual(btree_wrapper))
graph.subgraph(arrow_visual())
graph.subgraph(tree_visual(tree_wrapper))
file = 'visualization/' + datetime.datetime.now().strftime('%H-%M-%S')
graph.render(file, view=True)
另一个是PythonTree.py，这个脚本里建立了一个Python的二叉树类B_Tree，它包含了一个前序遍历的二叉树节点列表和忽略标志这两个类成员变量， generate_pre_order是用来生成前序遍历列表，trans_to_c是用Python的二叉树树类B_Tree里面的前序列表来构建C++里的二叉树BTreeWrapper对象，也就是我们在Python_Wrapper里导出的那个C++二叉树类。
脚本里还有个convert_to_tree函数，内部调用的实际上就是Python_Wrapper里导出的那个BTreetoTree函数，即调用C++所写的转换函数来将二叉树转换为普通树。
然后我们再回到PythonTree.py这个脚本，这个脚本里还有一个btree_to_tree方法，它是提供给C++来进行调用的，这个函数首先利用Python里的B_Tree类构建了一个二叉树root，然后调用这个类的generate_pre_order生成了前序遍历列表。然后再调用trans_to_c函数，利用刚才的前序遍历列表生成了C++的二叉树BTreeWrapper对象c_btree。
生成了c_btree二叉树后，调用了Preorder，Inorder和Postorder输出了这个二叉树的前序，中序和后序的遍历结果。然后调用convert_to_tree函数，利用C++里的转换方法将c_btree二叉树对象转换成了一个新的普通树c_tree对象并输出其广度优先遍历结果。
最后调用TreeVisual.py里的visualization方法，将原始的二叉树和转换后生成的普通树显示出来。
import Python_Wrapper
from TreeVisual import visualization
class B_Tree():
preorder = []
ingore = '*'
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def generate_pre_order(self):
B_Tree.preorder.append(self.data)
if self.left is None:
B_Tree.preorder.append(B_Tree.ingore)
else:
self.left.generate_pre_order()
if self.right is None:
B_Tree.preorder.append(B_Tree.ingore)
else:
self.right.generate_pre_order()
def trans_to_c(self):
btree_wrapper = Python_Wrapper.BTreeWrapper(B_Tree.ingore)
btree_wrapper.Generate(B_Tree.preorder)
return btree_wrapper
def convert_to_tree(btree_wrapper):
return Python_Wrapper.BTreetoTree(btree_wrapper)
#call
def btree_to_tree():
root = B_Tree("A")
b = B_Tree("B")
c = B_Tree("C")
d = B_Tree("D")
e = B_Tree("E")
f = B_Tree("F")
g = B_Tree("G")
h = B_Tree("H")
i = B_Tree("I")
j = B_Tree("J")
#k = B_Tree("K")
#l = B_Tree("L")
#m = B_Tree("M")
#n = B_Tree("N")
root.left = b
b.left = c
b.right = d
d.left = e
d.right = f
e.right = g
g.left = h
g.right = i
f.left = j
#c.left = k
#k.left = l
#l.right = m
#m.right = n
root.generate_pre_order()
print("----Preorder List----")
print(root.preorder)
c_btree = root.trans_to_c()
print("\n")
print("----Preorder----")
c_btree.Preorder()
print("\n")
print("----Inorder----")
c_btree.Inorder()
print("\n")
print("----Postorder----")
c_btree.Postorder()
print("\n")
c_tree = convert_to_tree(c_btree)
print("----Levelorder----")
c_tree.Levelorder()
#btree_visual(c_btree)
#tree_visual(c_tree)
visualization(c_btree, c_tree)
C++调用Python脚本来实现功能
然后我们将Python_Invoker_Module里面的调用改为调用PythonTree.py脚本里面的btree_to_tree方法。
if (!PyInvoker::Initialize())
{
std::cout << "----Python Enviorment Initialized Failed!----" << std::endl;
return -1;
}
PyInvoker::ImportModule(GetCurrentDir());
PyInvoker::RunFunc("PythonTree", "btree_to_tree");
PyInvoker::Finalize();
我们来运行一下。。。可以看到，得到了我们想要的结果，正确输出了二叉树的几种遍历结果，同时还是实现了转换结果的可视化。
