二叉树的所有编程算法

#include <iostream> #include <string> #include <vector> #include <list> #include <cassert> using namespace std; // struct define struct Node { char c; Node* left; Node* right; bool leftVisite; bool rightVisite; Node() { c = 0; left = 0; right = 0; leftVisite = false; rightVisite = false; } }; // 按先序扩展序列建立二叉树 Node* createTree(const string& allNodes); void displayTree(Node* tree); // 先序、中序、后序遍历的递归算法 void firstTravel(Node* tree); void midTravel(Node* tree); void lastTravel(Node* tree); // 先序遍历的非递归算法, 基于堆栈 void _firstTravel(Node* tree); // 中序遍历的非递归算法, 基于堆栈 void _midTravel(Node* tree); // 后序遍历的非递归算法, 基于堆栈 void _lastTravel(Node* tree); // 释放资源 void releaseTravel(Node* tree); // 层次的非递归算法, 基于队列 void levelTravel(Node* tree); // 统计二叉树中叶子结点的个数 int countLeaf(Node* tree); // 统计二叉树中结点的总数 int countNode(Node* tree); // 求二叉树的深度(后序遍历) int treeDepth(Node* tree); // 求二叉树的宽度（具有结点数最多的层上的结点数） unsigned int treeWidth(Node* tree); // 已知二叉树中序遍历和后序遍历序列，求二叉树的二叉链表结构 Node* midLastToTree(const string& midIn, const string& lastIn); // 已知二叉树中序遍历和先序遍历序列，求二叉树的二叉链表结构 Node* firstMidToTree(const string& midIn, const string firstIn); void main() { cout<<"输入先序扩展序列\n"; string inData; getline(cin, inData); Node* tree = createTree(inData); cout<<"树的2叉表示:\n"; displayTree(tree); cout<<"先序遍历:"; firstTravel(tree); cout<<'\n'; cout<<"中序遍历:"; midTravel(tree); cout<<'\n'; cout<<"后序遍历:"; lastTravel(tree); cout<<'\n'; cout<<"非递归先序遍历:"; _firstTravel(tree); cout<<'\n'; cout<<"非递归中序遍历:"; _midTravel(tree); cout<<'\n'; cout<<"非递归后序遍历:"; _lastTravel(tree); cout<<'\n'; cout<<"层次遍历:"; levelTravel(tree); cout<<'\n'; cout<<"叶子节点数目:"<<countLeaf(tree)<<'\n'; cout<<"总节点数目:"<<countNode(tree)<<'\n'; cout<<"树深度:"<<treeDepth(tree)<<'\n'; cout<<"树宽度:"<<treeWidth(tree)<<'\n'; // 中序遍历和后序遍历序列求二叉树 { releaseTravel(tree); cout<<"输入中序和后序遍历序列\n"; string midIn, lastIn; getline(cin, midIn); getline(cin, lastIn); tree = midLastToTree(midIn, lastIn); displayTree(tree); } // 中序遍历和先序遍历序列求二叉树 { releaseTravel(tree); cout<<"输入先序遍历和中序遍历序列\n"; string midIn, firstIn; getline(cin, firstIn); getline(cin, midIn); tree = firstMidToTree(midIn, firstIn); displayTree(tree); } cout<<"press any key to continue\n"; cin>>inData; releaseTravel(tree); } void createChild(Node* &node, string::const_iterator& iter, string::const_iterator& endIter) { if (iter != endIter) { char c = *iter++;//建立字符串 if (' ' == c) { node = 0; } else { node = new Node; node->c = c;//构造根结点 createChild(node->left, iter, endIter);//构造左子树 createChild(node->right, iter, endIter);//构造右子树 } } else { node = 0; } } Node* createTree(const string& allNodes)// 按先序扩展序列建立二叉树 { string::const_iterator curIter = allNodes.begin(); string::const_iterator endIter = allNodes.end(); Node* tree = 0; createChild(tree, curIter, endIter); return tree; } void firstTravel(Node* tree)//先序遍历的递归算法 { if (tree) { cout<<tree->c;//根 firstTravel(tree->left);//左 firstTravel(tree->right);//右 } } void releaseTravel(Node* tree)// 释放资源 { if (tree) { releaseTravel(tree->left); releaseTravel(tree->right); delete tree; tree = 0; } } void midTravel(Node* tree)//中序遍历的递归算法 { if (tree) { midTravel(tree->left); cout<<tree->c; midTravel(tree->right); } } void lastTravel(Node* tree)//后序遍历的递归算法 { if (tree) { lastTravel(tree->left); lastTravel(tree->right); cout<<tree->c; } } void resetTree(Node* tree)//重置二叉树 { if (tree) { tree->leftVisite = false; tree->rightVisite = false; resetTree(tree->left); resetTree(tree->right); } } void _firstTravel(Node* tree)//先序遍历非递归算法 { //assert(tree); resetTree(tree); typedef vector<Node*> NodeStack; NodeStack stack; stack.push_back(tree); // 初始化栈 while (stack.size()) { Node* topNode = stack.back(); if (!topNode->leftVisite && !topNode->rightVisite) { cout<<topNode->c; } if (topNode->left && !topNode->leftVisite) { stack.push_back(topNode->left); topNode->leftVisite = true; }else if (topNode->right && !topNode->rightVisite) { stack.push_back(topNode->right); topNode->rightVisite = true; } else { stack.pop_back(); } } } void _midTravel(Node* tree)//中序遍历的非递归算法 { //assert(tree); resetTree(tree); typedef vector<Node*> NodeStack; NodeStack stack; stack.push_back(tree); // 初始化 while (stack.size()) { Node* topNode = stack.back(); if (topNode->leftVisite && !topNode->rightVisite) { cout<<topNode->c; } if (topNode->left && !topNode->leftVisite) { stack.push_back(topNode->left); topNode->leftVisite = true; }else if (topNode->right && !topNode->rightVisite) { if (!topNode->left && topNode->right) {cout<<topNode->c; }// 单边只有右子节点 stack.push_back(topNode->right); topNode->rightVisite = true; } else { if (!topNode->left && !topNode->right) { cout<<topNode->c; } stack.pop_back(); } } } void _lastTravel(Node* tree)//后序遍历的非递归算法 { //assert(tree); resetTree(tree); typedef vector<Node*> NodeStack; NodeStack stack; stack.push_back(tree); // 初始化 while (stack.size()) { Node* topNode = stack.back(); if (topNode->leftVisite && topNode->rightVisite) { cout<<topNode->c; } if (topNode->left && !topNode->leftVisite) { stack.push_back(topNode->left); topNode->leftVisite = true; }else if (topNode->right && !topNode->rightVisite) { stack.push_back(topNode->right); topNode->rightVisite = true; } else { // 针对叶子节点或者单边子节点的情况 if (!topNode->left || !topNode->right) { cout<<topNode->c; } stack.pop_back(); } } } void levelTravel(Node* tree)// 层次的非递归算法, 基于队列 { //assert(tree); typedef list<Node*> Queue; Queue nodeQueue; nodeQueue.push_back(tree); while (nodeQueue.size())//由上至下，由左至右 { Node* node = nodeQueue.front(); cout<<node->c; if (node->left) { nodeQueue.push_back(node->left); } if (node->right) { nodeQueue.push_back(node->right); } nodeQueue.pop_front(); } } int countLeaf(Node* tree)// 统计二叉树中叶子结点的个数 { if (!tree) { return 0; } if (!tree->left && !tree->right)//孤立点 { return 1; } //递归计算 int sum = 0; sum += countLeaf(tree->left); sum += countLeaf(tree->right); return sum; } int countNode(Node* tree)// 统计二叉树中结点的总数 { int sum = 0; if (tree) { sum = 1; sum += countNode(tree->left); sum += countNode(tree->right); } return sum; } int treeDepth(Node* tree)// 求二叉树的深度(后序遍历) { int leftDepth = 0; int rightDepth = 0; if (tree) { leftDepth = 1; leftDepth += treeDepth(tree->left); rightDepth = 1; rightDepth += treeDepth(tree->right); } return max(leftDepth, rightDepth); } unsigned int treeWidth(Node* tree)// 求二叉树的宽度（具有结点数最多的层上的结点数） { if (!tree) { return 0; } typedef list<Node*> Queue; Queue nodeQueue; unsigned int width = 0; nodeQueue.push_back(tree); while (nodeQueue.size()) { unsigned int size = nodeQueue.size(); // 上一层的节点全部出列,并压入下一层节点 for (unsigned int i=0; i<size; ++i) { Node* node = nodeQueue.front(); if (node->left) { nodeQ