二叉树的遍历操作

一时失言乱红尘 2022-06-14 23:09 204阅读 0赞

#include<iostream> #include<queue> #include<stack> using namespace std; //定义二叉树的节点数据类型 struct BTNode{ char data; BTNode *left_child; BTNode *right_child; }; class BinaryTree { private: BTNode *BT; public: BinaryTree(){BT = NULL;}//构造函数，将根节点置空 ~BinaryTree();//销毁二叉树 void CreateBTree(){ cout<<"输入数据，以‘#'代表空指针："<<endl;Create(BT);} void Create(BTNode* &ptNode);//递归创建二叉树 void DisplayLevelBTree();//层次遍历二叉树 void PreTraBTree(){cout<<"递归先序遍历：";PreTraBTree(BT);cout<<endl;} void InTraBTree(){cout<<"递归中序遍历：";InTraBTree(BT);cout<<endl;} void PostTraBTree(){cout<<"递归后序遍历：";PostTraBTree(BT);cout<<endl;} void PreTraBTree(BTNode* ptNode);//递归算法：先序遍历 void InTraBTree(BTNode* ptNode);//递归算法：中序遍历 void PostTraBTree(BTNode* ptNode);//递归算法：后序遍历 void PreTraBTree_N();//非递归算法：先序遍历 void InTraBTree_N();//非递归算法：中序遍历 void PostTraBTree_N();//非递归算法：后序遍历 }; //递归创建二叉树 void BinaryTree::Create(BTNode* &ptNode) { char data; cin>>data; if(data == '#') ptNode = NULL; else { ptNode = new BTNode; if(ptNode == NULL) cout<<"申请内存失败！"<<endl; ptNode->data = data; Create(ptNode->left_child); Create(ptNode->right_child); } } //层次遍历二叉树 /* ** 算法概述 层次遍历二叉树，关键要用到队列， 父结点一出，就要判断子结点是否为空，非空则马上进入队列 */ void BinaryTree::DisplayLevelBTree() { cout<<"层次遍历二叉树："<<endl; queue<BTNode *> que; if(BT!=NULL) que.push(BT); else cout<<"树为空！"<<endl; BTNode *pnode; while(!que.empty()) { pnode = que.front(); cout<<pnode->data<<' '; que.pop(); if(pnode->left_child) que.push(pnode->left_child); if(pnode->right_child) que.push(pnode->right_child); } cout<<endl; } //递归算法：先序遍历 void BinaryTree::PreTraBTree(BTNode* ptNode) { if(ptNode) { cout<<ptNode->data<<' '; PreTraBTree(ptNode->left_child); PreTraBTree(ptNode->right_child); } } //递归算法：中序遍历 void BinaryTree::InTraBTree(BTNode* ptNode) { if(ptNode) { InTraBTree(ptNode->left_child); cout<<ptNode->data<<' '; InTraBTree(ptNode->right_child); } } //递归算法：后序遍历 void BinaryTree::PostTraBTree(BTNode* ptNode) { if(ptNode) { PostTraBTree(ptNode->left_child); PostTraBTree(ptNode->right_child); cout<<ptNode->data<<' '; } } //非递归算法：先序遍历 /* ** 算法概述 对于任一节点P， 1）输出节点P，然后将其入栈，再看P的左孩子是否为空； 2）若P的左孩子不为空，则置P的左孩子为当前节点，重复1）的操作； 3）若P的左孩子为空，则将栈顶节点出栈，但不输出， 并将出栈节点的右孩子置为当前节点，看其是否为空； 4）若不为空，则循环至1）操作； 5）如果为空，则继续出栈，但不输出， 同时将出栈节点的右孩子置为当前节点， 看其是否为空，重复4）和5）操作； 6）直到当前节点P为NULL并且栈空，遍历结束。 */ void BinaryTree::PreTraBTree_N() { cout<<"非递归先序遍历："; stack<BTNode *> bt_stack;//利用栈来实现 BTNode* p_cur = BT;//当前节点，开始的时候指向根节点 while( p_cur || !bt_stack.empty())//当前节点P为NULL并且栈空，遍历结束 { cout<<p_cur->data<<' ';//首先输出当前数据 bt_stack.push(p_cur);//当前节点入栈 p_cur = p_cur->left_child;//入栈的时候操作左孩子 while(!p_cur && !bt_stack.empty())//当前节点为空 { p_cur = bt_stack.top(); bt_stack.pop(); p_cur = p_cur->right_child;//出栈的时候操作右孩子 } } cout<<endl; } //非递归算法：中序遍历 /* ** 算法概述 对于任一节点P， 1）若P的左孩子不为空，则将P入栈并将P的左孩子置为当前节点， 然后再对当前节点进行相同的处理； 2）若P的左孩子为空，则输出P节点，而后将P的右孩子置为当前节点， 看其是否为空； 3）若不为空，则重复1）和2）的操作； 4）若为空，则执行出栈操作，输出栈顶节点， 并将出栈的节点的右孩子置为当前节点，看其是否为空， 重复3）和4）的操作； 5）直到当前节点P为NULL并且栈为空，则遍历结束。 */ void BinaryTree::InTraBTree_N() { cout<<"非递归中序遍历："; stack<BTNode *> bt_stack; BTNode* p_cur = BT; while(p_cur || !bt_stack.empty()) { if(p_cur->left_child) { bt_stack.push(p_cur); p_cur = p_cur->left_child; } else { cout<<p_cur->data<<' '; p_cur = p_cur->right_child; while(!p_cur && !bt_stack.empty()) { p_cur = bt_stack.top(); cout<<p_cur->data<<' '; bt_stack.pop(); p_cur = p_cur->right_child; } } } cout<<endl; } //非递归算法：后序遍历 void BinaryTree::PostTraBTree_N() { } int main() { BinaryTree *b_tree = new BinaryTree(); b_tree->CreateBTree(); b_tree->DisplayLevelBTree(); b_tree->PreTraBTree(); b_tree->InTraBTree(); b_tree->PostTraBTree(); b_tree->PreTraBTree_N(); b_tree->InTraBTree_N(); return 0; }

显然，对一个含有n个节点的二叉树进行遍历，其时间复杂度为O(n)，所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况为n，因此其空间复杂的也为O(n)。

参考博文：http://blog.csdn.net/pi9nc/article/details/13008511