二叉树的构造与一些常见操作(C++描述)

二叉树的构造与一些常见操作(C++描述)

2020-10-04 二叉树的构建与销毁&遍历&具体操作

这是《王道数据结构》中要求读者必须掌握的一些操作，我花了一上午实现了一下，其中大部分操作都是用的递归方法。为了测试，我额外写了诸如构建树和销毁树等函数。

过程中我仅用了几个用例来测试函数，可能有没考虑到的边界情况，如果存在问题，请各位大佬务必在评论区指正。

先直接上代码，等以后有时间再把这些操作整理、完善和扩充。

2020-10-04 二叉树的构建与销毁&遍历&具体操作

#include<iostream> #include<vector> using namespace std; //此例子中以char为节点类型，作改动时部分函数也需要更改，'#'代表空结点 typedef char elem; //二叉树的二叉链表存储 typedef struct BNode{ elem val; BNode* left, *right; BNode(elem v):left(NULL),right(NULL){ val = v; } }BTree; //循环队列---专用于BNode* typedef struct Queue{ static const int MaxSize = 50; //根据输入规模可以调整 BNode* queue[MaxSize]; int front, rear; Queue():front(0),rear(0){} void EnQueue(BNode* node){ if((rear+1)%MaxSize != front){ queue[rear] = node; rear = (rear+1) % MaxSize; } } void DeQueue(BNode*& e){ if(front != rear){ e = queue[front]; front = (front+1)%MaxSize; } } bool isEmpty(){ return front == rear; } }Queue; /********************典型&一般操作的函数原型**********************/ //最基本操作 void createBTree(BTree*& root, const vector<elem>& v); //创建树 void destroyBTree(BTree*& root); //销毁树 //bfs void bfs(BTree* root, vector<BNode*>& nodes); //层序遍历 //dfs void preorder(BTree* root, vector<BNode*>& nodes); //先序遍历模板 void inorder(BTree* root, vector<BNode*>& nodes); //中序遍历模板 void postorder(BTree* root, vector<BNode*>& nodes); //后序遍历模板 void bfsPrint(BTree* root); //按层序遍历顺序打印树的元素(不能体现树形) void preOrderPrint(BTree* root, int level=1); //先序打印结点值以及所在层次 //一些具体的操作 int calcDegreeNodeCount(BTree* root, int degree); //计算特定度的节点数 int getBTreeHeight(BTree* root); //获得该树的高度 int getBTreeWidth(BTree* root); //获得树的宽度 void delBTreeLeaves(BTree*& root); //删除树中所有叶子结点 int getNodeLayer(BTree* root, BNode* p, int level=1); //获取结点所在层次 elem getBTreeMaxVal(BTree* root); //获得元素最大值 void swapNodes(BNode* root); //交换结点的子女 void revertBTree(BTree* root); //翻转整棵二叉树 /**************************函数定义****************************/ //创建BTree void createBTree(BTree*& root, const vector<elem>& v){ int n = v.size(); if(!n || v[0] == '#') return; root = NULL; Queue que; root = new BNode(v[0]); que.EnQueue(root); int i=1; while (i<n){ BNode* p = NULL; if(!que.isEmpty()) que.DeQueue(p); else{ cout<<"error input"<<endl; break; } if(v[i] == '#'){ ++i; que.EnQueue(NULL); //占位空结点 } else{ p->left = new BNode(v[i++]); que.EnQueue(p->left); } if(i<n){ if(v[i] == '#'){ ++i; que.EnQueue(NULL); //占位空结点 } else{ p->right = new BNode(v[i++]); que.EnQueue(p->right); } } } } //销毁树 void destroyBTree(BTree*& root){ if(!root) return; destroyBTree(root->left); destroyBTree(root->right); delete root; root = NULL; } //按层序遍历序列打印结点值 void bfsPrint(BTree* root){ if(!root) return; Queue que; que.EnQueue(root); while (!que.isEmpty()){ BNode* e = NULL; que.DeQueue(e); cout<<e->val<<" "; if(e->left) que.EnQueue(e->left); if(e->right) que.EnQueue(e->right); } cout<<"\n"; } //获取BTree中结点度为degree的个数 int calcDegreeNodeCount(BTree* root, int degree){ if(!root) return 0; int left = calcDegreeNodeCount(root->left, degree); int right = calcDegreeNodeCount(root->right, degree); int deg = 0; if(root->left) ++deg; if(root->right) ++deg; if(deg == degree){//度为degree的结点 return 1 + left + right; } return left + right; } //获取BTree的高度 int getBTreeHeight(BTree* root){ if(!root) return 0; int left = getBTreeHeight(root->left); int right = getBTreeHeight(root->right); return 1 + (left > right ? left: right); } //获取BTree的宽度 int getBTreeWidth(BTree* root){ if(!root) return 0; BNode* lastNode = root; BNode* newLastNode = NULL; Queue que; que.EnQueue(root); int curWidth = 0, maxWidth = 0; while (!que.isEmpty()){ BNode* p = NULL; que.DeQueue(p); curWidth++; if(p->left){ que.EnQueue(p->left); newLastNode = p->left; } if(p->right){ que.EnQueue(p->right); newLastNode = p->right; } if(p == lastNode){ maxWidth = maxWidth>=curWidth?maxWidth:curWidth; lastNode = newLastNode; curWidth=0; } } return maxWidth; } //删除BTree中所有叶子节点 void delBTreeLeaves(BTree*& root){ if(!root) return; if(!root->left && !root->right){ delete root; root = NULL; return; } delBTreeLeaves(root->left); delBTreeLeaves(root->right); } //获得指定结点p所在的层级 int getNodeLayer(BTree* root, BNode* p, int level){ if(!root){ return 0; //cannot find } else if(root == p){ return level; } else{ int left = getNodeLayer(root->left, p, level+1); if(!left){ return getNodeLayer(root->right, p, level+1); } else return left; } } //层序遍历得到的序列保存在nodes容器中 void bfs(BTree* root, vector<BNode*>& nodes){ nodes.clear(); if(!root) return; Queue que; que.EnQueue(root); while (!que.isEmpty()){ BNode* p = NULL; que.DeQueue(p); nodes.push_back(p); if(p->left){ que.EnQueue(p->left); } if(p->right){ que.EnQueue(p->right); } } } //获得BTree中元素最大值 elem getBTreeMaxVal(BTree* root){ if(!root){ return 0; } int left=-1, right=-1; if(root->left) left = getBTreeMaxVal(root->left); if(root->right) right = getBTreeMaxVal(root->right); if(root->val >= left && root->val >= right) return root->val; else if(left >= root->val && left >= right){ return left; } else{ return right; } } //先序遍历得到的序列保存在nodes容器中 void preorder(BTree* root, vector<BNode*>& nodes){ if(!root) return; nodes.push_back(root); preorder(root->left, nodes); preorder(root->right, nodes); } //中序遍历得到的序列保存在nodes容器中 void inorder(BTree* root, vector<BNode*>& nodes){ if(!root) return; inorder(root->left, nodes); nodes.push_back(root); inorder(root->right, nodes); } //后序遍历得到的序列保存在nodes容器中 void postorder(BTree* root, vector<BNode*>& nodes){ if(!root) return; postorder(root->left, nodes); postorder(root->right, nodes); nodes.push_back(root); } //交换root的子女节点 (翻转) void swapNodes(BNode* root){ if(!root->left && !root->right) return; BNode* temp = root->left; root->left = root->right; root->right = temp; } //翻转整棵树，包括其子树 void revertBTree(BTree* root){ //先后序都行，但中序不可以，因为可能"负负得正 " if(!root){ return; } swapNodes(root); revertBTree(root->left); revertBTree(root->right); } //先序打印结点元素值以及所在层级 void preOrderPrint(BTree* root, int level){ if(!root) return; cout<<root->val<<" -> "<<level<<endl; preOrderPrint(root->left, level+1); preOrderPrint(root->right, level+1); } //操作测试 int main(){ BTree* root = NULL; int N = 15; vector<elem> v= vector<elem>(N); for (int i=0; i<N; ++i){ v[i] = 'a' + i; } v[9] = v[10] = v[11] = v[12] = v[5] = '#'; cout<<"树的形状: "; for (int i=0; i<N; ++i) cout<<v[i]<<" "; cout<<endl; cout<<"createTree"<<endl; createBTree(root, v); cout<<"\nTest bfsPrint(): "<<endl; bfsPrint(root); cout<<"\nTest calcDegreeNodeCount(): "<<endl; cout<<"度为1的结点："<<calcDegreeNodeCount(root, 1)<<endl; cout<<"度为2的结点："<<calcDegreeNodeCount(root, 2)<<endl; cout<<"度为0的结点："<<calcDegreeNodeCount(root, 0)<<endl; cout<<"\nTest getBTreeHeight(): "<<endl; cout<<"树的高度为："<<getBTreeHeight(root)<<endl; cout<<"\nTest getBTreeWidth(): "<<endl; cout<<"树的宽度为："<<getBTreeWidth(root)<<endl; /* cout<<"\nTest delBTreeLeaves(): "<<endl; cout<<"Before delete: "<<endl; bfsPrint(root); cout<<"After delete: "<<endl; delBTreeLeaves(root); bfsPrint(root); */ cout<<"\nTest getNodeLayer(): "<<endl; vector<BNode*> ret; bfs(root, ret); cout<<"node "<<ret[5]->val<<" is at layer " <<getNodeLayer(root, ret[5])<<endl; cout<<"\nTest getBTreeMaxVal(): "<<endl; cout<<"树中最大元素："<<getBTreeMaxVal(root)<<endl; cout<<"\nTest revertBTree(): "<<endl; revertBTree(root); cout<<"树翻转后："<<endl; bfsPrint(root); cout<<"\nTest preOrderPrint(): "<<endl; cout<<"格式：结点值 -> 层次"<<endl; preOrderPrint(root); destroyBTree(root); return 0; }

【运行结果】