Creation and traversal of binary tree

The definition of a tree

： What is a tree ？

Suppose we give the results of preorder traversal and inorder traversal of a binary tree , How can we create a tree from these two traversal results ？

Through the result of preorder traversal, we can find the root node of the binary tree , Now that you have the root node of the binary tree , We are looking at sequence traversal , Find the root node of the binary tree in the middle order traversal , All nodes before the root node are the left subtree of the binary tree , All nodes after the root node are the right subtree of the binary tree . Thus, the traversal results can be segmented .

Now that you have got the left subtree and the right subtree, it's easy to do , We know that the left and right subtrees of a binary tree can also be regarded as a binary tree , At this time, the scale of binary tree becomes smaller , But it still conforms to the results of preorder traversal and inorder traversal , Therefore, the left and right subtrees can be created separately .

Pseudo code means ：

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)
{
    
    // First, we need to buy a node , Let it be the root node , So you need a purchase node function 
    BtNode* root = BuyNode();// Buy nodes 
    root->value = pre[0];
    // To build a binary tree , We also need to find the location of the root node in the middle order traversal , So as to determine the left and right subtrees , So you also need a lookup function , The return value is the location of the root node pos
    int pos = FindPos(in,n,pre[0]);// Find... In the middle order traversal pre[0] The location of , If not found , It shows that the two traversal results are not a binary tree , immediate withdrawal 
    if(pos == -1) exit(0);
    // At this time, we have new left subtree and right subtree , Create... Separately 
    CreateBinaryTree( The result of preorder traversal of left subtree , Middle order traversal results of left subtree , The size of the left subtree );// Create the left subtree 
    CreateBinaryTree( The result of preorder traversal of the right subtree , The middle order traversal result of the right subtree , The size of the right subtree );// Create the right subtree 
}


//pre  Indicates that the pre order traversal array ,in Indicates that the array is traversed in middle order ,n Represents the number of nodes 
BinaryTree CreateBtree(char* Pre,char* in)
{
    
    int n = sizeof(pre)/sizeof(pre[0]);
    if(pre==nullptr||in==nullptr||n<=0)
    {
    
        return nullptr;// If the above conditions are not met, the binary tree does not exist , Returns a null pointer directly 
    }
    CreateBinaryTree(pre,in,n);// Start to create 
}

The complete code for building a binary tree and traversing before, during and after recursion is as follows ：

#include<iostream>
#include<stack>
#include<queue>
#include<memory>

/* * There are two ways to store binary trees , One is to store in a linked list , One is to store in an array  *  When storing in an array , Pay attention to the relationship between nodes , Suppose the location of the root node is POS Then the position of the left subtree is  * 2*POS+1, The position of the right subtree is 2*POS+2. Because of this relationship , When the binary tree is not full , Use arrays for storage  *  It's a waste of space , Low utilization of space . *  When storing a binary tree in a linked list , Each binary tree node contains a left child pointer and a right child pointer , Two pointers, respectively  *  Point to the corresponding node , Save a space , And it's easier to use . */
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;
}


// Create a binary tree through the first and middle order array 
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];// The last data of post order traversal is the root node 
		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;
}

// Establish a binary tree through the post ordered array 
BinaryTree CreateLITree(ElemType* Li, ElemType* In)
{
    
	int n = strlen(Li);
	if (Li == nullptr || In == nullptr)
	{
    
		return nullptr;
	}
	else
		return CreateLI(Li, In, n);
}

// Preorder traversal of two tree （ recursively ） The root node - The left subtree - Right subtree 
void PreOrder(BtNode* root)
{
    
	if (root != nullptr)
	{
    
		cout << root->value << " ";
		PreOrder(root->leftchild);
		PreOrder(root->rightchild);
	}
}

// Middle order traversal of binary trees （ recursively ） The left subtree - The root node - Right subtree 
void InOrder(BtNode* root)
{
    
	if (root != nullptr)
	{
    
		InOrder(root->leftchild);
		cout << root->value << " ";
		InOrder(root->rightchild);
	}
}

// Postorder traversal of binary trees （ recursively ） The left subtree - Right subtree - The root node 
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;
}

Implementation of non recursive middle order traversal ：

Here we need a stack to realize , Take advantage of stack features , Last in, first out , When we reach the end node , Print end node . In the order of the middle , Both left, middle and right print binary tree . How do you do that ？

Apply for a station to store nodes , When the root node is not empty , Or when the stack is not empty, judge whether the left child of the node in the stack is empty , If the left child is not empty, continue to put the left child in the stack , If the left child is empty , Just print this node , Then visit the right child , Continue the previous judgment .

The point is that when we visit each node , It should be judged as the root node , Think of it as a small binary tree , Complete the middle order traversal , Then the overall implementation is the middle order traversal of the whole binary tree .

Code implementation :

void NiceInOrder(BtNode* root)
{
    
	// If the root node is empty , Return directly without sorting 
	if(root == nullptr) return;
    std::stack<BtNode*> st;
    while(root!=nullptr || !st.empty())
    {
    
        // Keep putting the left subtree on the stack , When the left subtree is empty , It indicates that the end node is reached 
        while(root!=nullptr)
        {
    
            st.push(root);
            root = root->leftchild;
        }
        root = st.top(); st.pop();
        cout<< root->value;
        root = root->rightchild;
        }
    }
}

Non recursive postorder traversal of binary trees ：

The order of post order traversal is left, right, middle , Access the left subtree first when the left subtree is accessed , When accessing the right subtree , Finally, the root node is accessed . Then the difficulty of non recursive post order traversal is , After accessing the end node, how can we determine whether to print the node , Whether there is any right subtree of this node that has not been accessed .

Suppose the binary tree has only three nodes , As shown in the figure ：

If the root node is not empty, put the root node on the stack , Because it is post order traversal , So you need to visit the left subtree of the root node , You can see that the left subtree is not empty , Continue to visit the left subtree , When the left subtree is empty, return to the root node and continue to judge whether the right subtree is empty , When the left and right subtrees are empty , To print the root node .

Code implementation ：

void NicePastOrder(BtrNode* root)
{
    
    if(root == nullptr) return;
    std::stack<BtNode*> st;
    BtNode* tag = nullptr;// Sign a , Always point to the most recently printed node 
    while(root != nullptr || !st.empty())
    {
    
        while(root!=nullptr)
        {
    
            st.push(root);
            root = root->left;
        }
        // When the above loop is completed , State the current *root It has pointed to nullptr, Then his parent node has no left subtree , Then you can go to war 
        // After performing the stack out operation , We already know root The left child of the node is empty , Or the left child has already printed it .
        root= st.top(); st.pop();
        // Because it performs post order traversal 、 After coming out of the stack, we still need to judge , Whether the node has a right subtree , If there is and has not been traversed , Then the root node can be printed after traversing the right subtree 
        if(root->rightchild == nullptr || root->rightchild == tag)
        {
    
            cout << root->value;
            tag = ptr;
            ptr =nullptr;
        }
        else
        {
    
            // If the right subtree is not empty , You need to put the right subtree on the stack again , Continue to judge 
            st.push(root);
            root = root->rightchild;
        }
    }
}

Implementation of non recursive preorder traversal of binary tree ：

To implement the preorder traversal, you need to print the root node first , Then print the left subtree and then the right subtree , Still use the divide and conquer strategy . Using a stack , First put the root node on the stack , as long as root If it is not empty or the stack is not empty, it will always loop , Every cycle produces the top element , And judge and put the left and right children of the elements on the top of the stack .

Code implementation ：

void NicePreOrder(BtNode* root)
{
    
	if (root == nullptr) return;
	stack<BtNode*> s;
	s.push(root);// First put the root node 
	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;
		}
	}
}

The creation of binary tree and the code summary of traversal before, during and after ：

#include<iostream>
#include<stack>
#include<queue>
#include<memory>

/*
* There are two ways to store binary trees , One is to store in a linked list , One is to store in an array 
*  When storing in an array , Pay attention to the relationship between nodes , Suppose the location of the root node is POS Then the position of the left subtree is 
* 2*POS+1, The position of the right subtree is 2*POS+2. Because of this relationship , When the binary tree is not full , Use arrays for storage 
*  It's a waste of space , Low utilization of space .
*  When storing a binary tree in a linked list , Each binary tree node contains a left child pointer and a right child pointer , Two pointers, respectively 
*  Point to the corresponding node , Save a space , And it's easier to use .
*/
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;
}


// Create a binary tree through the first and middle order array 
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];// The last data of post order traversal is the root node 
		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;
}

// Establish a binary tree through the post ordered array 
BinaryTree CreateLITree(ElemType* In , ElemType* Li)
{
	int n = strlen(In );
	if (Li == nullptr || In == nullptr)
	{
		return nullptr;
	}
	else
		return CreateLI(In,Li , n);
}

// Preorder traversal of two tree （ recursively ） The root node - The left subtree - Right subtree 
void PreOrder(BtNode* root)
{
	if (root != nullptr)
	{
		cout << root->value << " ";
		PreOrder(root->leftchild);
		PreOrder(root->rightchild);
	}
}

// Middle order traversal of binary trees （ recursively ） The left subtree - The root node - Right subtree 
void InOrder(BtNode* root)
{
	if (root != nullptr)
	{
		InOrder(root->leftchild);
		cout << root->value << " ";
		InOrder(root->rightchild);
	}
}

// Postorder traversal of binary trees （ recursively ） The left subtree - Right subtree - The root node 
void PastOrder(BtNode* root)
{
	if (root != nullptr)
	{
		InOrder(root->leftchild);
		InOrder(root->rightchild);
		cout << root->value << " ";
	}
}
 Middle order traversal of binary trees （ Non recursive ）
// The use of circulation is generally the focus of the interview , The principle is to use the stack to store the corresponding subtree , When reaching the terminal node , Then take the nodes in the stack out of the stack one by one 
void NiceInOrder(BtNode* root)
{
	if (root == nullptr) return;
	stack<BtNode*> s;
	while (root !=nullptr || !s.empty())
	{
		// Stack the entire left subtree 
		while (root != nullptr)
		{
			s.push(root);
			root = root->leftchild;
		}
		// Start to stack when reaching the end node 
		root = s.top();
		s.pop();
		cout << root->value;
		root = root->rightchild;
	}
	cout << endl;
}


// Preorder traversal of two tree （ Non recursive ）
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;
}

// Postorder traversal of binary trees （ Non recursive ）
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;/
}