C++二叉树的创建及遍历详情

2022-11-13 13:11:53 创建遍历详情

树的定义

什么是树？

假如给我们一棵二叉树的前序遍历和中序遍历结果，我们应该如何通过这两个遍历结果创建一棵树呢？

通过前序遍历的结果我们可以找到二叉树的根节点，那么既然有了二叉树的根节点，我们在看中序遍历，在中序遍历中找到二叉树的根节点，呢么根节点之前的所有节点就是二叉树的左子树了，根节点之后的所有节点就是二叉树的右子树了。由此就可以对遍历结果进行分割了。

既然已经得到了左子树和右子树就好办了，我们知道二叉树的左子树和右子树也可以看作是一棵二叉树，此时二叉树的规模变小的了，但还是符合前序遍历和中序遍历的结果，所以可以对左右子树在分别进行创建。

伪代码表示：

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>

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不为空或者栈不为空就一直循环，每次循环都出栈顶元素，并判断并将栈顶元素的左右孩子入栈。