上次写了一篇二叉树概念总结的文章，有朋友留言说想看我写关于二叉树遍历和实现的内容。本文就二叉树的遍历方式之先序遍历及利用先序遍历思想创建二叉树进行详细的讲解。
粉丝留言
二叉树的链式存储
二叉树的物理存储可以采用链式存储。如下图所示二叉树：
二叉树
采用链式存储，节点的构成为：
指向左子节点的指针（LeftChild）；节点存储的数据（Data）；指向右子节点的指针（RightChild）；链式存储示意图如下：
二叉树链式存储示意图
二叉树节点以C++类的方式实现为：
class BinaryTree
{
public:
tint Data ;//存储的数据
tBinaryTree* LeftChild;//指向左子节点
tBinaryTree* RightChild ;t
};
先序遍历
想要遍历二叉树的所有节点，这个类似于html标签遍历，但是二叉树有自己的特性，所以二叉树的遍历一般有以下三种：先序遍历、中序遍历、后序遍历和层次遍历；本文就先讲最容易的先序遍历，并且借鉴先序遍历的思想实现一个二叉树。
先序号遍历的核心思想为：按根节点——左子树——右子树的顺序遍历.，以前面的二叉树为例：
访问二叉树的根节点 1；访问节点 1 的左子树，找到节点 2；访问节点 2 的左子树，找到节点 4；由于节点 4 没有左子树，也没有右子树，所以以节点 4 遍历完成，但是节点 2 还未遍历右子树，即节点 5；由于节点 5 无左右子树，此时节点 5 遍历完成，以节点 2 为根的子树也遍历完成。现在回到节点 1 ，并开始遍历该节点的右子树，即访问节点 3；访问节点 3 左子树，找到节点 6；由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；节点 7 无左右子树，以节点 3 为根节点的子树遍历完成，同时回到节点 1。由于节点 1 的左右子树全部遍历完成，此时整个二叉树遍历完成；如下图所示：
先序遍历
先序遍历代码实现：
void PreTraversal(BinaryTree* T){
if (T) {
PreTraversal(T->LeftChild);//访问结点的左孩子
PreTraversal(T->RightChild);//访问结点的右孩子
}
//如果结点为空，返回上一层
return;
}
利用先序遍历思想实现二叉树
借鉴先序遍历的思想，先将左子树全部建立好，再建立右子树的方式来创建二叉树：
BinaryTree* CreatBinaryTree()
{
tstring data = "" ;
tcouttcin>>data ;
tif(data == ".")return nullptr ;
tBinaryTree* root = new BinaryTree();
troot->Data = atoi(data.c_str());
tPreOrderCreat(root) ;
treturn root ;
}
void PreOrderCreat(BinaryTree* T){
tif (T != nullptr ) {tt
ttstring data = "" ;
ttcoutttcin>>data ;
ttif(data != ".")
tt{
tttBinaryTree* node = new BinaryTree();
tttnode->Data = atoi(data.c_str());
tttT->LeftChild = node ;
tt}
PreOrderCreat(T->LeftChild);//访问该结点的左孩子
ttcoutttcin>>data ;
ttif(data != ".")
tt{
tttBinaryTree* node = new BinaryTree();
tttnode->Data = atoi(data.c_str());
tttT->RightChild = node ;
tt}
PreOrderCreat(T->RightChild);//访问该结点的右孩子
}
//如果结点为空，返回上一层
return;
}
本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.sosokankan.com/article/1482088.html