Digging into the various operations of traversing binary trees (non recursive traversal)
- 2020-04-02 00:48:35
- OfStack
First use, first order method to establish a binary tree, and then respectively using the method of recursive and non-recursive implementation before the order, in sequence, after the order traversing binary tree, and use the two methods for traversing binary tree, one way is to use the queue in the STL, another method is to define the queue, an array, respectively, using the front and rear two array subscript to represent the team with the team, there are two operation is the depth of the binary tree, the junction points...
The operation effect diagram is as follows:
Input two nodes in the binary tree, output the two nodes in the lowest number of the common parent node.
Idea: walk the binary tree, find a path from the root node to the destination node, and then look for the common parent node on both paths.
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
//Description of binary tree nodes
typedef struct BiTNode
{
char data;
struct BiTNode *lchild, *rchild; //About the child
}BiTNode,*BiTree;
//Create a binary tree by walking through it in order
//BiTree *CreateBiTree() // Returns the node pointer type
//void CreateBiTree(BiTree &root) // Parameter of the reference type
void CreateBiTree(BiTNode **root) //The secondary pointer is used as the function parameter
{
char ch; //The data to be inserted
scanf("n%c", &ch);
//cin>>ch;
if(ch=='#')
*root = NULL;
else
{
*root = (BiTNode *)malloc(sizeof(BiTNode));
(*root)->data = ch;
printf(" Please enter the %c Left child: ",ch);
CreateBiTree(&((*root)->lchild));
printf(" Please enter the %c Right children: ",ch);
CreateBiTree(&((*root)->rchild));
}
}
//Preorder traversal of the algorithm program
void PreOrder(BiTNode *root)
{
if(root==NULL)
return ;
printf("%c ", root->data); //The output data
PreOrder(root->lchild); //Recursively, the preorder traverses the left subtree
PreOrder(root->rchild); //Recursively, the preorder traverses the right subtree
}
//In order traversal of the algorithm program
void InOrder(BiTNode *root)
{
if(root==NULL)
return ;
InOrder(root->lchild); //Recursively, the preorder traverses the left subtree
printf("%c ", root->data); //The output data
InOrder(root->rchild); //Recursively, the preorder traverses the right subtree
}
//An algorithmic program for sequential traversal
void PostOrder(BiTNode *root)
{
if(root==NULL)
return ;
PostOrder(root->lchild); //Recursively, the preorder traverses the left subtree
PostOrder(root->rchild); //Recursively, the preorder traverses the right subtree
printf("%c ", root->data); //The output data
}
void PreOrder_Nonrecursive2(BiTree T) //Non - recursive & NBSP of first order traversal;
{
if(!T)
return ;
stack<BiTree> s;
s.push(T);
while(!s.empty())
{
BiTree temp = s.top();
cout<<temp->data<<" ";
s.pop();
if(temp->rchild)
s.push(temp->rchild);
if(temp->lchild)
s.push(temp->lchild);
}
}
void PreOrder_Nonrecursive(BiTree T) //Nonrecursive order traversal first
{
if(!T)
return ;
stack<BiTree> s;
while(T) //The nodes in the left subtree are all pushed into the stack
{
s.push(T);
cout<<T->data<<" ";
T = T->lchild;
}
while(!s.empty())
{
BiTree temp = s.top()->rchild; //The right subtree of the top element on the stack
s.pop(); //Pops the top of the stack element
while(temp) //If there is a right subtree at the top of the stack, the right subtree is also traversed to the bottom
{
cout<<temp->data<<" ";
s.push(temp);
temp = temp->lchild;
}
}
}
void InOrderTraverse(BiTree T) //The non - recursive traversal of the middle order
{
if(!T)
return ;
stack<BiTree> S;
BiTree curr = T->lchild; //Points to the current node to check
S.push(T);
while(curr != NULL || !S.empty())
{
while(curr != NULL) //Go all the way to the left
{
S.push(curr);
curr = curr->lchild;
}
curr = S.top();
S.pop();
cout<<curr->data<<" ";
curr = curr->rchild;
}
}
void PostOrder_Nonrecursive(BiTree T) //Non - recursive & NBSP of post - order traversal;
{
stack<BiTree> S;
BiTree curr = T ; //Points to the current node to check
BiTree previsited = NULL; //Points to the previous node being accessed
while(curr != NULL || !S.empty()) //End of stack empty time & noon;
{
while(curr != NULL) //Go all the way to the left Until it is empty
{
S.push(curr);
curr = curr->lchild;
}
curr = S.top();
//The right child of the current node accesses the current node if it is empty or already accessed
if(curr->rchild == NULL || curr->rchild == previsited)
{
cout<<curr->data<<" ";
previsited = curr;
S.pop();
curr = NULL;
}
else
curr = curr->rchild; //Otherwise visit the right child
}
}
void PostOrder_Nonrecursive(BiTree T) //Non - recursive & NBSP of post - order traversal; & have spent & have spent & have spent Double stack method
{
stack<BiTree> s1 , s2;
BiTree curr ; //Points to the current node to check
s1.push(T);
while(!s1.empty()) //End of stack empty time & noon;
{
curr = s1.top();
s1.pop();
s2.push(curr);
if(curr->lchild)
s1.push(curr->lchild);
if(curr->rchild)
s1.push(curr->rchild);
}
while(!s2.empty())
{
printf("%c ", s2.top()->data);
s2.pop();
}
}
int visit(BiTree T)
{
if(T)
{
printf("%c ",T->data);
return 1;
}
else
return 0;
}
void LeverTraverse(BiTree T) //Method 1. Traversing the binary tree at non-recursive levels
{
queue <BiTree> Q;
BiTree p;
p = T;
if(visit(p)==1)
Q.push(p);
while(!Q.empty())
{
p = Q.front();
Q.pop();
if(visit(p->lchild) == 1)
Q.push(p->lchild);
if(visit(p->rchild) == 1)
Q.push(p->rchild);
}
}
void LevelOrder(BiTree BT) //Method 2. Traversing the binary tree at non-recursive levels
{
BiTNode *queue[10];//The definition queue has ten Spaces
if (BT==NULL)
return;
int front,rear;
front=rear=0;
queue[rear++]=BT;
while(front!=rear)//If the tail pointer is not equal to the head pointer
{
cout<<queue[front]->data<<" "; //Output traversal results
if(queue[front]->lchild!=NULL) //Enqueue the left child pointer at the head of the queue
{
queue[rear]=queue[front]->lchild;
rear++; //The tail pointer moves back one place
}
if(queue[front]->rchild!=NULL)
{
queue[rear]=queue[front]->rchild; //Enqueue the right child of the first node in the queue
rear++; //The tail pointer moves back one place
}
front++; //Move the counter pointer one place back
}
}
int depth(BiTNode *T) //The depth of the tree
{
if(!T)
return 0;
int d1,d2;
d1=depth(T->lchild);
d2=depth(T->rchild);
return (d1>d2?d1:d2)+1;
//return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;
}
int CountNode(BiTNode *T)
{
if(T == NULL)
return 0;
return 1+CountNode(T->lchild)+CountNode(T->rchild);
}
int main(void)
{
BiTNode *root=NULL; //Define a root node
int flag=1,k;
printf(" This procedure to achieve the basic operation of binary tree. n");
printf(" Can be set up binary tree, recursive first order, in order, after the order traversal, non-recursive first order, in order traversal and non-recursive sequence traversal operations. n");
while(flag)
{
printf("n");
printf("|--------------------------------------------------------------|n");
printf("| The basic operations of a binary tree are as follows : |n");
printf("| 0. Create a binary tree |n");
printf("| 1. Recursively order traversal first |n");
printf("| 2. Order traversal in recursion |n");
printf("| 3. Recursive sequential traversal |n");
printf("| 4. Non-recursive first order traversal |n");
printf("| 5. Nonrecursive order traversal |n");
printf("| 6. Nonrecursive sequential traversal |n");
printf("| 7. Nonrecursive hierarchical traversal |n");
printf("| 8. binary The depth of the tree |n");
printf("| 9. The number of nodes in the binary tree |n");
printf("| 10. Exit the program |n");
printf("|--------------------------------------------------------------|n");
printf(" Please select functions: ");
scanf("%d",&k);
switch(k)
{
case 0:
printf(" Please establish a binary tree and enter the root node of the binary tree: ");
CreateBiTree(&root);
break;
case 1:
if(root)
{
printf(" The result of recursive first order traversal binary tree is: ");
PreOrder(root);
printf("n");
}
else
printf(" Binary tree is empty! n");
break;
case 2:
if(root)
{
printf(" The result of order traversal binary tree in recursion is: ");
InOrder(root);
printf("n");
}
else
printf(" Binary tree is empty! n");
break;
case 3:
if(root)
{
printf(" The result of traversing the binary tree after recursion is: ");
PostOrder(root);
printf("n");
}
else
printf(" Binary tree is empty! n");
break;
case 4:
if(root)
{
printf(" Non-recursive first order traversal binary tree: ");
PreOrder_Nonrecursive(root);
printf("n");
}
else
printf(" Binary tree is empty! n");
break;
case 5:
if(root)
{
printf(" Non-recursive order traversal binary tree: ");
InOrderTraverse(root);
printf("n");
}
else
printf(" Binary tree is empty! n");
break;
case 6:
if(root)
{
printf(" Non-recursive traversal binary tree: ");
PostOrder_Nonrecursive(root);
printf("n");
}
else
printf(" Binary tree is empty! n");
break;
case 7:
if(root)
{
printf(" Non-recursive order traversal binary tree: ");
//LeverTraverse(root);
LevelOrder(root);
printf("n");
}
else
printf(" Binary tree is empty! n");
break;
case 8:
if(root)
printf(" The binary tree The depth of the tree To: %dn",depth(root));
else
printf(" Binary tree is empty! n");
break;
case 9:
if(root)
printf(" The number of nodes of this binary tree is: %dn",CountNode(root));
else
printf(" Binary tree is empty! n");
break;
default:
flag=0;
printf(" The program is finished, press any key to exit! n");
}
}
system("pause");
return 0;
}
The operation effect diagram is as follows:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/2013052417405321.gif ">
Input:
1
2
4
#
#
5
#
#
3
6
#
#
7
#
#
You u can construct a binary tree as shown in the following figure.
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/2013052417405322.gif ">
Another way to write postorder traversal non-recursion:
void Postorder(BiTree T)
{
if(T == NULL)
return ;
stack<BiTree> s;
BiTree prev = NULL , curr = NULL;
s.push(T);
while(!s.empty())
{
curr = s.top();
if(prev == NULL || prev->lchild == curr || prev->rchild == curr)
{
if(curr->lchild != NULL)
s.push(curr->lchild);
else if(curr->rchild != NULL)
s.push(curr->rchild);
}
else if(curr->lchild == prev)
{
if(curr->rchild != NULL)
s.push(curr->rchild);
}
else
{
cout<<curr->data;
s.pop();
}
prev = curr;
}
}
Input two nodes in the binary tree, output the two nodes in the lowest number of the common parent node.
Idea: walk the binary tree, find a path from the root node to the destination node, and then look for the common parent node on both paths.
//Gets a path from the root node to the destination node & NBSP;
bool GetNodePath(TreeNode *pRoot , TreeNode *pNode , vector<TreeNode *> &path)
{
if(pRoot == NULL)
return false;
if(pRoot == pNode)
return true;
else if(GetNodePath(pRoot->lchild , pNode , path) )
{
path.push_back(pRoot->lchild);
return true;
}
else if(GetNodePath(pRoot->rchild , pNode , path) )
{
path.push_back(pRoot->rchild);
return true;
}
return false;
}
TreeNode *GetLastCommonNode(const vector<TreeNode *> &path1 , const vector<TreeNode *> &path2)
{
vector<TreeNode *>::const_iterator iter1 = path1.begin();
vector<TreeNode *>::const_iterator iter2 = path2.begin();
TreeNode *pLast;
while(iter1 != path1.end() && iter2 != path2.end() )
{
if(*iter1 == *iter2)
pLast = *iter1;
else
break;
iter1++;
iter2++;
}
return pLast;
}
TreeNode *GetLastCommonParent(TreeNode *pRoot , TreeNode *pNode1 , TreeNode *pNode2)
{
if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
vector<TreeNode *> path1;
GetNodePath(pRoot , pNode1 , path1);
vector<TreeNode *> path2;
GetNodePath(pRoot , pNode2 , path2);
return GetLastCommonNode(path1 , path2);
}