【数据结构】二叉树的递归实现
发布时间:2020-12-15 05:57:16 所属栏目:安全 来源:网络整理
导读:二叉树的概念,这里就不想多说了,但是你需要知道满二叉树,完全二叉树等等这些基本 概念,下边进入正题。 首先创建一棵二叉树,下边看代码: Node* _Create(T* a,size_t size,size_t index,const T invalid){assert(a);Node* root = NULL;while (index size
二叉树的概念,这里就不想多说了,但是你需要知道满二叉树,完全二叉树等等这些基本 概念,下边进入正题。 首先创建一棵二叉树,下边看代码:
Node* _Create(T* a,size_t size,size_t& index,const T& invalid) { assert(a); Node* root = NULL; while (index < size && a[index] != invalid) { root = new Node(a[index]); root->_left = _Create(a,size,++index,invalid); root->_right = _Create(a,invalid); } return root; } 这里需要注意的就是对数组a的断言。养成好的习惯,该断言就断言。还有就是index这 个必须是引用,因为每个元素只访问一次,也就是外部改的index,内部也需要改。所以 ,就是传引用。 二叉树的销毁:
void _Destroy(Node* root) { if (root == NULL) return; _Destroy(root->_left); _Destroy(root->_right); } 递归代码,看着很简单,但是别忘了销毁,否则内存泄漏。 二叉树的三种遍历----前序,中序,后序
void _PreOrder(Node* root) { Node* cur = root; if (cur != NULL) { cout << cur->_data<<" "; _PreOrder(cur->_left); _PreOrder(cur->_right); } } void _InOrder(Node* root) { Node* cur = root; if (cur != NULL) { _InOrder(cur->_left); cout << cur->_data<<" "; _InOrder(cur->_right); } } void _PostOrder(Node* root) { Node* cur = root; if (cur != NULL) { _PostOrder(cur->_left); _PostOrder(cur->_right); cout << cur->_data<<" "; } } 层序遍历:
void _TiertOrder(Node* root) { queue<Node*> q; Node* cur = root; q.push(cur); while (!q.empty()) { Node* tmp = q.front(); cout << tmp->_data << " "; if (tmp->_left) { q.push(tmp->_left); } if (tmp->_right) { q.push(tmp->_right); } q.pop(); } } 这个过程用到了队列,这里就讲一下思路吧:如果不是空树,根节点入队,如果入队结 点的子树不为空,将子树也入队,入队之后弹出根节点,下边以此类推。比如跟的左孩 子存在,并且已经入队,如果左孩子有左右孩子,将左右孩子也入队,弹出开始入队的 左孩子。 二叉树的深度:
size_t _Depth(Node* root) { if (root == NULL) return 0; size_t left = _Depth(root->_left); size_t right = _Depth(root->_right); return left > right ? left + 1 : right + 1; } 递归过程比较耗时,所以上边的两个变量是很有必要的,永远不要为了代码看着简洁而 不考虑计算机的感受。 二叉树的结点个数:
size_t _Size(Node* root) { if (root == NULL) return 0; return _Size(root->_left) + _Size(root->_right) + 1; } 二叉树中元素的查找
Node* _Find(Node* root,const T& x) { Node* cur = root; if (cur == NULL) return NULL; if (cur->_data == x) return cur; //左子树没有找到才会去遍历 右子树 if (!_Find(cur->_left,x)) _Find(cur->_right,x); } 好了,关于二叉树的递归实现就到这里-- (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- ORA-00704: bootstrap process failure
- 学习笔记5-bootstrap 排版
- angularjs – 角度UI Grid 3.x版本中的操作按钮
- vim – 设置在向前和向后移动单词时跳过标点符号
- 从Angularjs服务调用WebApi中的延迟加载的nHibernate对象时
- linux shell less 命令---转
- angularjs – TypeError:无法使用Angular读取undefined的属
- 在使用无形类型不等式时,如何自定义Scala模糊隐式错误
- 使用XFire开发WebServices服务端
- ruby-on-rails – 为什么:memory_store缓存比memcached的d