二叉树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含7527字,纯文字阅读大概需要11分钟。
内容图文
![二叉树](/upload/InfoBanner/zyjiaocheng/1276/8dfceb6058a64c1481087431d2720ff5.jpg)
介绍二叉树之前呢,我们先来说说树?
树呢,顾名思义,长得像一棵树,不过通常我们画成一颗倒过来的树,根在上,叶在下。还是看图吧。
既然说到树了,那就说说树的一些基本概念吧。用图说明。
树的存储结构:
下面呢,就来介绍树的特殊例子---二叉树
所谓二叉树呢,就是父节点最多有两个孩子。
二叉树的存储结构:
(1)数组存储
数组存储即用一块连续内存来存储二叉树。
若二叉树为满二叉树或者完全二叉树时,用数组存储非常有效,但是对于一般的二叉树来说,效果并不是很好。若要在二叉树中进行增删的话,可能要挪动大量的元素。而使用链表可以克服此困难。
(2)链表存储
template <class T> class BinaryTreeNode//节点 { public: BinaryTreeNode(const T& data) :_data(data) ,_left(NULL) ,_right(NULL) {} T _data;//值 BinaryTreeNode* _left;//左子树 BinaryTreeNode* _right;//右子树 };
以下述二叉树为例,实现代码:
此二叉树的数组表示:int a[10] = {1,2,3,‘#‘,‘#‘,4,‘#‘,‘#‘,5,6}
由图可知:
先根遍历:1,2,3,4,5,6
中根遍历:3,2,4,1,6,5
后根遍历:3,4,2,6,5,1
层次遍历:1,2,5,3,4,6
template <class T> class BinaryTree { public: BinaryTree()//无参构造函数 :_root(NULL) {} BinaryTree(const T* a,size_t size,const T& invalue)//构造函数 { size_t index = 0; _root = _CreatTree(a,size,index,invalue); } BinaryTree(const BinaryTree<T>& t)//拷贝构造 { _root = _Copy(t._root); } BinaryTree<T>& operator=(const BinaryTree<T>& t)//赋值函数 { if(this != &t) { BinaryTreeNode<T>* tmp = _Copy(t._root); _Destory(_root); _root = tmp; } return *this; } ~BinaryTree()//析构 { _Destory(_root); _root = NULL; } public: void PrevOrder()//先根遍历 { cout<<"先根遍历:"; _PrevOrder(_root); cout<<endl; } void InOrder()//中根遍历 { cout<<"中根遍历:"; _InOrder(_root); cout<<endl; } void PostOrder()//后根遍历 { cout<<"后根遍历:"; _PostOrder(_root); cout<<endl; } void LevelOrder()//层次遍历 { cout<<"层次遍历:"; _LevelOrder(_root); } size_t size() { size_t size = 0; _Size(_root,size); return size; } size_t size()//节点个数 { return _Size(_root); } size_t Depth()//树的深度 { return _Depth(_root); } size_t LeafSize()//叶子节点个数 { return _LeafSize(_root); } public: public: BinaryTreeNode<T>* _CreatTree(const T* a,size_t size,size_t &index,const T& invalue)//创建树 { BinaryTreeNode<T>* root = NULL; if(index < size && a[index] != invalue) { root = new BinaryTreeNode<T>(a[index]); root->_left = _CreatTree(a,size,++index,invalue); root->_right = _CreatTree(a,size,++index,invalue); } return root; } void _PrevOrder(BinaryTreeNode<T>* root)//先根遍历 { if(root == NULL) return; else { cout<<root->_data<<" "; _PrevOrder(root->_left); _PrevOrder(root->_right); } } void _InOrder(BinaryTreeNode<T>* root)//中根遍历 { if(root == NULL)//递归终止条件 return; else { _InOrder(root->_left); cout<<root->_data<<" "; _InOrder(root->_right); } } void _PostOrder(BinaryTreeNode<T>* root)//后根遍历 { if(root == NULL) return; else { _PostOrder(root->_left); _PostOrder(root->_right); cout<<root->_data<<" "; } } void _Destory(BinaryTreeNode<T>* root)//析构---相当于后序删除 { if(root == NULL) return; else { _Destory(root->_left); _Destory(root->_right); delete root; } } size_t _Size(BinaryTreeNode<T>* root)//节点的个数 { size_t count = 0; if(root == NULL) return 0; count = _Size(root->_left) + _Size(root->_right); return count+1; } size_t _Depth(BinaryTreeNode<T>* root)//树的深度 { size_t left = 0; size_t right = 0; size_t max = 0; if(root == 0) return 0; else { left = _Depth(root->_left); right = _Depth(root->_right); max = left>right?left:right; return max+1; } } size_t _LeafSize(BinaryTreeNode<T>* root)//叶子节点的个数 { size_t count = 0; if(root == NULL) return 0; if(root && root->_left == NULL && root->_right == NULL) return 1; count = _LeafSize(root->_left)+_LeafSize(root->_right); return count; } //size_t _LeafSize(BinaryTreeNode<T>* root)//遍历整个树来确定叶子节点的个数 //{ // static size_t count = 0; // if(root == NULL) // return 0; // if(root->_left == NULL && root->_right == NULL) // { // ++count; // } // _LeafSize(root->_left); // _LeafSize(root->_right); // return count; //} BinaryTreeNode<T>* _Copy(BinaryTreeNode<T>* root) { BinaryTreeNode<T>* newroot = NULL; if(root != NULL) { newroot = new BinaryTreeNode<T>(root->_data); newroot->_left = _Copy(root->_left); newroot->_right = _Copy(root->_right); } return newroot; } void _LevelOrder(BinaryTreeNode<T>* root)//层次遍历 { queue<BinaryTreeNode<T>*> q; if(root == NULL) return; if(root != NULL) { q.push(root); } while(!q.empty()) { BinaryTreeNode<T>* node = q.front(); cout<<node->_data<<" "; if(node->_left != NULL) { q.push(node->_left); } if(node->_right != NULL) { q.push(node->_right); } q.pop(); } cout<<endl; } void PrevOrder_NonR()//非递归的先根遍历 { cout<<"非递归的先根遍历:"; BinaryTreeNode<T>* cur = _root; stack<BinaryTreeNode<T>*> s; if(cur != NULL) { s.push(cur); cout<<s.top()->_data<<" "; s.pop(); } while(!s.empty() || cur) { if(cur->_right != NULL) { s.push(cur->_right); } if(cur->_left != NULL) { s.push(cur->_left); } if(!s.empty()) { cout<<s.top()->_data<<" "; cur = s.top(); s.pop(); } else { cur = NULL; } } cout<<endl; } void INOrder_NonR()//非递归的中根遍历 { cout<<"非递归的中根遍历:"; if(_root == NULL) return; BinaryTreeNode<T>* cur = _root; stack<BinaryTreeNode<T>*> s; while(cur || !s.empty()) { while(cur) { s.push(cur); cur = cur->_left; } BinaryTreeNode<T>* top = s.top(); cout<<top->_data<<" "; s.pop(); cur = top->_right; } cout<<endl; } void PostOrder_NonR()//非递归的后根遍历 { cout<<"非递归的后根遍历:"; BinaryTreeNode<T>* cur = _root; BinaryTreeNode<T>* prev = NULL; stack<BinaryTreeNode<T>*> s; BinaryTreeNode<T>* top = NULL; if(_root == NULL) return; while(cur || !s.empty()) { while(cur) { while(cur) { s.push(cur); cur = cur->_left; } top = s.top(); cur = top->_right; } if(s.top()->_right == NULL) { cout<<s.top()->_data<<" "; prev = s.top(); s.pop(); } if(!s.empty()) { if(s.top()->_right == prev) { cout<<s.top()->_data<<" "; prev = s.top(); s.pop(); } if(!s.empty()) { cur = s.top()->_right; } else { cur = NULL; } } } cout<<endl; } protected: BinaryTreeNode<T>* _root;//根节点 };
测试函数:
void Test() { int a[10] = {1,2,3,‘#‘,‘#‘,4,‘#‘,‘#‘,5,6}; BinaryTree<int> b(a,10,‘#‘); b.PrevOrder(); b.InOrder(); b.PostOrder(); //b.~BinaryTree(); int ret1 = b.size();//节点个数 int ret2 = b.LeafSize();//叶子节点 int ret3 = b.Depth();//深度 cout<<ret1<<endl; cout<<ret2<<endl; cout<<ret3<<endl; BinaryTree<int> b1(b);//拷贝构造 b1.PrevOrder(); BinaryTree<int> b2; b2 = b1;//赋值 b2.PrevOrder(); b2.LevelOrder(); b2.PrevOrder_NonR(); b2.INOrder_NonR(); b2.PostOrder_NonR(); }
测试结果:
测试结果和由图得出的结果相同。
原文:http://10810429.blog.51cto.com/10800429/1767038
内容总结
以上是互联网集市为您收集整理的二叉树全部内容,希望文章能够帮你解决二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。