树是一种重要的非线性数据结构,二叉树是树型结构的一种重要类型。本学年论文介绍了二叉树的定义,二叉树的存储结构,二叉树的相关术语,以此引入二叉树这一概念,为展开二叉树的基本操作做好理论铺垫。二叉树的基本操作主要包含以下几个模块:二叉树的遍历方法,计算二叉树的结点个数,计算二叉树的叶子结点个数,二叉树深度的求解等内容。
前序遍历(递归&非递归)
//前序非递归 void PrevOrder() { stack<Node*> s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { cout << cur->_data << " "; s.push(cur); cur = cur->_left; } //此时当前节点的左子树已遍历完毕 Node *tmp = s.top(); s.pop(); cur = tmp->_right; } cout << endl; } //前序递归 void PrevOrderR() { _PrevOrder(_root); cout << endl; } void _PrevOrder(Node *root) { if (root == NULL) //必须有递归出口!!! return; cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); }
中序遍历(递归&非递归)
//中序非递归 void InOrder() { stack<Node*> s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } //此时当前节点的左子树已遍历完毕 Node *tmp = s.top(); cout << tmp->_data << " "; s.pop(); cur = tmp->_right; } cout << endl; } //中序递归 void InOrderR() { _InOrder(_root); cout << endl; } void _InOrder(Node *root) { if (root == NULL) return; _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); }
后序遍历(递归&非递归)
//后序非递归 //后序遍历可能会出现死循环,所以要记录下前一个访问的节点 void PostOrder() { stack<Node*> s; Node *cur = _root; Node *prev = NULL; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node *tmp = s.top(); if (tmp->_right && tmp->_right != prev) { cur = tmp->_right; } else { cout << tmp->_data << " "; prev = tmp; s.pop(); } } cout << endl; } //后序递归 void PostOrderR() { _PostOrder(_root); cout << endl; } void _PostOrder(Node *root) { if (root == NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; }
层序遍历
从根节点开始,依次访问每层结点。
利用队列先进先出的特性,把每层结点从左至右依次放入队列。
void LevelOrder() //利用队列!!! { queue<Node*> q; Node *front = NULL; //1.push根节点 if (_root) { q.push(_root); } //2.遍历当前节点,push当前节点的左右孩子,pop当前节点 //3.遍历当前节点的左孩子,再遍历右孩子,循环直至队列为空 while (!q.empty()) { front = q.front(); cout << front->_data << " "; if (front->_left) q.push(front->_left); if (front->_right) q.push(front->_right); q.pop(); } cout << endl; }
求二叉树的高度
size_t Depth() { return _Depth(_root); } size_t _Depth(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else { size_t leftDepth = _Depth(root->_left) + 1; size_t rightDepth = _Depth(root->_right) + 1; return leftDepth > rightDepth ? leftDepth : rightDepth; } }
求叶子节点的个数
size_t LeafSize() { return _LeafSize(_root); } size_t _LeafSize(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else return _LeafSize(root->_left) + _LeafSize(root->_right); }
求二叉树第k层的节点个数
size_t GetKLevel(int k) { return _GetKLevel(_root, k); } size_t _GetKLevel(Node *root, int k) { if (root == NULL) return 0; else if (k == 1) return 1; else return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1); }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/482005.html