C++二叉树创建
乐十九 人气:0树的定义
什么是树？
假如给我们一棵二叉树的前序遍历和中序遍历结果，我们应该如何通过这两个遍历结果创建一棵树呢？
通过前序遍历的结果我们可以找到二叉树的根节点，那么既然有了二叉树的根节点，我们在看中序遍历，在中序遍历中找到二叉树的根节点，呢么根节点之前的所有节点就是二叉树的左子树了，根节点之后的所有节点就是二叉树的右子树了。由此就可以对遍历结果进行分割了。
既然已经得到了左子树和右子树就好办了，我们知道二叉树的左子树和右子树也可以看作是一棵二叉树，此时二叉树的规模变小的了，但还是符合前序遍历和中序遍历的结果，所以可以对左右子树在分别进行创建。
伪代码表示：
BtNode* BuyNode()
{
BtNode* s = (BtNode*)malloc(sizeof(BtNode));
if(s == nullptr) return nullptr;
memset(s,0,sizeof(BtNode));
return s;
}
int FindPos(char* in,int n,char a)
{
int pos = -1;
for(int i =0;i<n；++i)
{
if(in[i] == a)
{
pos = i;
break;
}
}
return pos;
}
BinaryTree CreateBinaryTree(char* Pre,char* in,int n)
{
//首先我们需要购买一个节点，让其作为根节点，所以就需要一个购买节点函数
BtNode* root = BuyNode();//购买节点
root->value = pre[0];
//要想构建二叉树，我们还需要在中序遍历中找到根节点的位置，从而确定左右子树，所以还需要一个查找函数，返回值是根节点的位置pos
int pos = FindPos(in,n,pre[0]);//在中序遍历中查找pre[0]的位置,如果没有找到，说明两个遍历结果不是一棵二叉树，直接退出
if(pos == -1) exit(0);
//此时我们已经有了新的左子树和右子树，分别来创建
CreateBinaryTree(左子树的前序遍历结果,左子树的中序遍历结果,左子树的大小);//创建左子树
CreateBinaryTree(右子树的前序遍历结果,右子树的中序遍历结果,右子树的大小);//创建右子树
}
//pre 表示前序遍历数组，in表示中序遍历数组，n表示节点的个数
BinaryTree CreateBtree(char* Pre,char* in)
{
int n = sizeof(pre)/sizeof(pre[0]);
if(pre==nullptr||in==nullptr||n<=0)
{
return nullptr;//不满足以上条件说明不存在该二叉树，直接返回空指针
}
CreateBinaryTree(pre,in,n);//开始创建
}构建二叉树以及使用递归方式前中后序遍历完整代码如下：
#include<iostream>
#include<stack>
#include<queue>
#include<memory>
/*
*二叉树的存储方式有两种，一种是以链表的方式进行存储，一种是以数组的方式进行存储
* 当以数组的方式进行存储的时候，要注意节点之间的关系，假设根节点的位置为POS那么左子树的位置就是
* 2*POS+1，右子树的位置就是2*POS+2。正是由于这层关系，当二叉树不是满二叉树的时候，使用数组进行存储
* 是非常的浪费空间的，空间的利用率较低。
* 当以链表的方式存储二叉树的时候，每一个二叉树节点都含有一个左孩子指针和一个右孩子指针，两个指针分别
* 指向相应的节点，节省空间，并且更容易使用。
*/
using namespace std;
typedef char ElemType;
typedef struct BtNode
{
ElemType value;
BtNode* leftchild;
BtNode* rightchild;
}BtNode,*BinaryTree;
BtNode* BuyNode()
{
BtNode* s = (BtNode*)malloc(sizeof(BtNode));
if (s == NULL)return nullptr;
memset(s, 0, sizeof(BtNode));
return s;
}
int FindPos(ElemType* In, int n, ElemType val)
{
int pos = -1;
for (int i = 0; i < n ; ++i)
{
if (In[i] == val)
{
pos = i;
break;
}
}
return pos;
}
BinaryTree CreateBinTree(ElemType* Pr, ElemType* In, int n)
{
BtNode* s = nullptr;
if (n >= 1)
{
s = BuyNode();
s->value = Pr[0];
int pos = FindPos(In, n, Pr[0]);
if (pos == -1) exit(0);
s->leftchild = CreateBinTree(Pr + 1, In, pos);
s->rightchild = CreateBinTree(Pr + pos + 1, In + pos + 1, n - pos - 1);
}
return s;
}
//通过前中序数组创建二叉树
BinaryTree CreateBinaryTree(ElemType* Pr, ElemType* In)
{
int n = strlen(Pr);
if (Pr == nullptr || In == nullptr)
{
return nullptr;
}
else
return CreateBinTree(Pr, In, n);
}
BinaryTree CreateLI(ElemType* Li, ElemType* In, int n)
{
BtNode* s = nullptr;
if (n >= 1)
{
s = BuyNode();
s->value = Li[n - 1];//后序遍历的最后一位数据是根节点
int pos = FindPos(In, n, Li[n - 1]);
if (pos == -1)exit(0);
s->leftchild = CreateLI(Li, In, pos);
s->rightchild = CreateLI(Li + pos, In + pos + 1, n - pos - 1);
}
return s;
}
//通过后中序数组建立二叉树
BinaryTree CreateLITree(ElemType* Li, ElemType* In)
{
int n = strlen(Li);
if (Li == nullptr || In == nullptr)
{
return nullptr;
}
else
return CreateLI(Li, In, n);
}
//二叉树的前序遍历（递归方式）根节点-左子树-右子树
void PreOrder(BtNode* root)
{
if (root != nullptr)
{
cout << root->value << " ";
PreOrder(root->leftchild);
PreOrder(root->rightchild);
}
}
//二叉树的中序遍历（递归方式）左子树-根节点-右子树
void InOrder(BtNode* root)
{
if (root != nullptr)
{
InOrder(root->leftchild);
cout << root->value << " ";
InOrder(root->rightchild);
}
}
//二叉树的后序遍历（递归方式）左子树-右子树-根节点
void PastOrder(BtNode* root)
{
if (root != nullptr)
{
InOrder(root->leftchild);
InOrder(root->rightchild);
cout << root->value << " ";
}
}
int main()
{
char ar[] = { "ABCDEFGH" };
char br[] = { "CBEDFAGH" };
char cr[] = { "CBEDFGHA" };
//BinaryTree root = CreateBinaryTree(ar, br);
BinaryTree root = CreateLITree(cr, br);
PreOrder(root);
cout << endl;
InOrder(root);
cout << endl;
PastOrder(root);
cout << endl;
}非递归的中序遍历的实现
这里我们需要借助一个栈来实现，利用栈的特性，后进先出，当我们到达端节点时，打印端节点。按照中序的顺序，既左中右打印二叉树。具体怎么操作呢？
申请一个站用来存储节点，当根节点不为空，或者栈不为空的时候判断栈中节点的左孩子是否为空，如果左孩子不为空就继续将左孩子入栈，如果左孩子为空，就打印该节点，然后在访问右孩子，继续之前的判断。
要点在于我们访问每一个节点的时候，都要将其当做根节点来判断，将其当做一个小的二叉树，完成中序遍历，那么总的实现下来就是整个二叉树的中序遍历啦。
代码实现:
void NiceInOrder(BtNode* root)
{
//如果根节点为空的话，直接返回就不用排序
if(root == nullptr) return;
std::stack<BtNode*> st;
while(root!=nullptr || !st.empty())
{
//不断将左子树入栈，当左子树为空时，说明到达端节点
while(root!=nullptr)
{
st.push(root);
root = root->leftchild;
}
root = st.top(); st.pop();
cout<< root->value;
root = root->rightchild;
}
}
}二叉树的非递归后序遍历：
后序遍历的顺序是左右中，优先访问左子树当左子树访问完毕之后，在访问右子树，最后访问根节点。那么非递归的后序遍历的难点在于，我们访问到端节点之后如何判断是否打印该节点呢，该节点是否还有右子树没有访问。
假设二叉树只有三个节点，如图所示：
如果根节点不为空就将根节点入栈，因为是后序遍历，所以要再访问根节点的左子树，可以看到左子树也不为空，继续向左子树访问，当左子树为空时返回到根节点继续判断右子树是否为空，当左右子树都为空的时候，才能打印根节点。
代码实现：
void NicePastOrder(BtrNode* root)
{
if(root == nullptr) return;
std::stack<BtNode*> st;
BtNode* tag = nullptr;//标志位，总是指向最近打印的那个节点
while(root != nullptr || !st.empty())
{
while(root!=nullptr)
{
st.push(root);
root = root->left;
}
//当上面的循环执行完毕，说明当前的*root已经指向了nullptr，那么他的双亲节点就是没有左子树的，然后可以进行出战操作了
//当执行完出栈操作之后，我们就已经知道了root节点的左孩子是空的，或者左孩子已经打印过了。
root= st.top(); st.pop();
//因为执行的是后序遍历、出栈之后我们还需要判断，该节点是否有右子树，如果有并且还没有遍历，那么要将右子树遍历完毕才能打印根节点
if(root->rightchild == nullptr || root->rightchild == tag)
{
cout << root->value;
tag = ptr;
ptr =nullptr;
}
else
{
//如果右子树不为空，就要再将右子树入栈，继续判断
st.push(root);
root = root->rightchild；
}
}
}二叉树的非递归的前序遍历的实现
要实现前序遍历就需要先打印根节点，然后打印左子树再打印右子树，还是要使用分治的策略。使用一个栈，先将根节点入栈，只要root不为空或者栈不为空就一直循环，每次循环都出栈顶元素，并判断并将栈顶元素的左右孩子入栈。
代码实现：
void NicePreOrder(BtNode* root)
{
if (root == nullptr) return;
stack<BtNode*> s;
s.push(root);//先将根节点放进去
while (root != nullptr || !s.empty())
{
root = s.top(); s.pop();
cout << root->value;
if (root->rightchild != nullptr)
{
s.push(root->rightchild);
root = root->rightchild;
}
if (root->leftchild != nullptr)
{
s.push(root->leftchild);
root = root->leftchild;
}
}
}二叉树的创建以及前中后序遍历的代码总结
#include<iostream>
#include<stack>
#include<queue>
#include<memory>
/*
*二叉树的存储方式有两种，一种是以链表的方式进行存储，一种是以数组的方式进行存储
* 当以数组的方式进行存储的时候，要注意节点之间的关系，假设根节点的位置为POS那么左子树的位置就是
* 2*POS+1，右子树的位置就是2*POS+2。正是由于这层关系，当二叉树不是满二叉树的时候，使用数组进行存储
* 是非常的浪费空间的，空间的利用率较低。
* 当以链表的方式存储二叉树的时候，每一个二叉树节点都含有一个左孩子指针和一个右孩子指针，两个指针分别
* 指向相应的节点，节省空间，并且更容易使用。
*/
using namespace std;
typedef char ElemType;
typedef struct BtNode
{
ElemType value;
BtNode* leftchild;
BtNode* rightchild;
}BtNode,*BinaryTree;
BtNode* BuyNode()
{
BtNode* s = (BtNode*)malloc(sizeof(BtNode));
if (s == NULL)return nullptr;
memset(s, 0, sizeof(BtNode));
return s;
}
int FindPos(ElemType* In, int n, ElemType val)
{
int pos = -1;
for (int i = 0; i < n ; ++i)
{
if (In[i] == val)
{
pos = i;
break;
}
}
return pos;
}
BinaryTree CreateBinTree(ElemType* Pr, ElemType* In, int n)
{
BtNode* s = nullptr;
if (n >= 1)
{
s = BuyNode();
s->value = Pr[0];
int pos = FindPos(In, n, Pr[0]);
if (pos == -1) exit(0);
s->leftchild = CreateBinTree(Pr + 1, In, pos);
s->rightchild = CreateBinTree(Pr + pos + 1, In + pos + 1, n - pos - 1);
}
return s;
}
//通过前中序数组创建二叉树
BinaryTree CreateBinaryTree(ElemType* Pr, ElemType* In)
{
int n = strlen(Pr);
if (Pr == nullptr || In == nullptr)
{
return nullptr;
}
else
return CreateBinTree(Pr, In, n);
}
BinaryTree CreateLI(ElemType* In, ElemType* Li, int n)
{
BtNode* s = nullptr;
if (n >= 1)
{
s = BuyNode();
s->value = Li[n - 1];//后序遍历的最后一位数据是根节点
int pos = FindPos(In, n, Li[n - 1]);
if (pos == -1)exit(0);
s->leftchild = CreateLI( In,Li, pos);
s->rightchild = CreateLI( In + pos + 1,Li + pos, n - pos - 1);
}
return s;
}
//通过后中序数组建立二叉树
BinaryTree CreateLITree(ElemType* In , ElemType* Li)
{
int n = strlen(In );
if (Li == nullptr || In == nullptr)
{
return nullptr;
}
else
return CreateLI(In,Li , n);
}
//二叉树的前序遍历（递归方式）根节点-左子树-右子树
void PreOrder(BtNode* root)
{
if (root != nullptr)
{
cout << root->value << " ";
PreOrder(root->leftchild);
PreOrder(root->rightchild);
}
}
//二叉树的中序遍历（递归方式）左子树-根节点-右子树
void InOrder(BtNode* root)
{
if (root != nullptr)
{
InOrder(root->leftchild);
cout << root->value << " ";
InOrder(root->rightchild);
}
}
//二叉树的后序遍历（递归方式）左子树-右子树-根节点
void PastOrder(BtNode* root)
{
if (root != nullptr)
{
InOrder(root->leftchild);
InOrder(root->rightchild);
cout << root->value << " ";
}
}
二叉树的中序遍历（非递归方式）
//使用循环的方式一般是面试时考察的重点，原理是使用栈去存储相应的子树，当到达终端节点时，再将栈中的节点一一出栈
void NiceInOrder(BtNode* root)
{
if (root == nullptr) return;
stack<BtNode*> s;
while (root !=nullptr || !s.empty())
{
//将整个左子树入栈
while (root != nullptr)
{
s.push(root);
root = root->leftchild;
}
//到达端节点时开始出栈
root = s.top();
s.pop();
cout << root->value;
root = root->rightchild;
}
cout << endl;
}
//二叉树的前序遍历（非递归方式）
void NicePreOrder(BtNode* root)
{
if (root == nullptr) return;
stack<BtNode*> s;
BtNode* node = nullptr;
s.push(root);
while (!s.empty())
{
node = s.top();
s.pop();
cout << node->value;
if (node->rightchild)
s.push(node->rightchild);
if (node->leftchild)
s.push(node->leftchild);
}
cout << endl;
}
//二叉树的后序遍历（非递归方式）
void NicePastOrder(BtNode* root)
{
if (root == nullptr)return;
stack<BtNode*> st;
BtNode* tag = nullptr;
while (root != nullptr || !st.empty())
{
while (root != nullptr)
{
st.push(root);
root = root->leftchild;
}
root = st.top();
st.pop();
if (root->rightchild == nullptr || root->rightchild == tag)
{
cout << root->value;
tag = root;
root = nullptr;
}
else
{
st.push(root);
root = root->rightchild;
}
}
cout << endl;
}
int main()
{
char ar[] = { "ABCDEFGH" };
char br[] = { "CBEDFAGH" };
char cr[] = { "CEFDBHGA" };
//BinaryTree root = CreateBinaryTree(ar, br);
BinaryTree root = CreateLITree(br,cr );
NiceInOrder(root);
NicePreOrder(root);
PreOrder(root);
/*PreOrder(root);
cout << endl;
InOrder(root);
cout << endl;
PastOrder(root);
cout << endl;*/
}ightchild == tag)
{
cout << root->value;
tag = root;
root = nullptr;
}
else
{
st.push(root);
root = root->rightchild;
}
}
cout << endl;
}
int main()
{
char ar[] = { “ABCDEFGH” };
char br[] = { “CBEDFAGH” };
char cr[] = { “CEFDBHGA” };
//BinaryTree root = CreateBinaryTree(ar, br);
BinaryTree root = CreateLITree(br,cr );
NiceInOrder(root);
NicePreOrder(root);
PreOrder(root);
/PreOrder(root);
cout << endl;
InOrder(root);
cout << endl;
PastOrder(root);
cout << endl;/
}加载全部内容