二叉树:二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream> #include<assert.h> #include<stack> #include<queue>
using namespace std; //节点结构 template<class T> class BinaryTreeNode//节点 { public: BinaryTreeNode(const T& data) :_data(data) ,_left(NULL) ,_right(NULL) {} T _data;//值 BinaryTreeNode* _left;//左子树 BinaryTreeNode* _right;//右子树 }; template<class T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: BinaryTree()//无参构造函数 :_root(NULL) {} BinaryTree(const T* a, size_t size, const T& invalid)//构造函数 { assert(a); size_t index = 0; _root = _CreateTree(a, size, invalid, index); } 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); _Destroy(_root); _root = temp; } return *this; } ~BinaryTree()//析构 { _Destroy(_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); cout << endl; } size_t Size()//求二叉树的节点的个数 { return _Size(_root); } size_t Depth()//求二叉树的深度 { return _Depth(_root); } size_t LeafSize()//叶子节点个数 { return _LeafSize(_root); } protected: Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index) //index要传引用,需要更改index的值 { Node* root = NULL; //判断数组是否越界和输入的值是否合法 if (index < size&&a[index] != invalid) { root = new Node(a[index]);//创建根节点 root->_left = _CreateTree(a, size, invalid, ++index);//递归创建左子树 root->_right = _CreateTree(a, size, invalid, ++index);//递归创建右子树 } return root;//返回根节点 } //void _PrevOrder(Node* root) //{ ////如果节点为空则直接返回 //if (root == NULL) //{ //return; //} //cout << root->_data << " ";//访问根节点 //_PrevOrder(root->_left);//递归访问左子树 //_PrevOrder(root->_right);//递归访问右子树 //} void _PrevOrder(Node* root) { stack<Node*> s; if (root==NULL) { return; } s.push(root); while (!s.empty()) { root = s.top(); cout << root->_data << " "; s.pop(); if (root->_right) { s.push(root->_right); } if (root->_left) { s.push(root->_left); } } } //void _InOrder(Node* root) //{ ////如果节点为空则直接返回 //if (root == NULL) //{ //return; //} //_InOrder(root->_left);//递归访问左子树 //cout << root->_data << " ";//递归访问根节点 //_InOrder(root->_right);//递归访问右子树 //} void _InOrder(Node* root) { if (root == NULL) { return; } stack<Node*> s; Node* cur = root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } cur = s.top();//将栈顶元素保存,以便后面判断它是否有有孩子 cout << s.top()->_data << " "; s.pop(); if (cur->_right == NULL) { cur = NULL; } else { cur = cur->_right; } } } //void _PostOrder(Node* root) //{ //if(root == NULL) //{ //return; //} //_PostOrder(root->_left);//递归访问左子树 //_PostOrder(root->_right);//递归访问右子树 //cout << root->_data << " ";//递归访问根节点 //} void _PostOrder(Node* root) { if (root == NULL) { return; } Node* cur = root; Node* prev = NULL; stack<Node*> s; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } cur = s.top(); if (cur->_right == NULL || cur->_right == prev) { cout << cur->_data << " "; s.pop(); prev = cur; cur = NULL; } else { cur = cur->_right; } } } void _Destory(Node* root)//析构---相当于后序删除 { if (root == NULL) { return; } //删除叶结点 if (root->_left== NULL&&root->_right == NULL) { delete root; root = NULL; return; } _Destory(root->_left);//递归删除左子树 _Destory(root->_right);//递归删除右子树 delete root; } size_t _Size(Node* root)//节点的个数 { size_t count = 0; if (root == NULL) { return count;//树为空 } count = _Size(root->_left) + _Size(root->_right); return count + 1; } size_t _Depth(Node* 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(Node* root)//叶子节点的个数 { if (root == NULL) { return 0; } if (root->_left == NULL && root->_right == NULL) { return 1; } return _LeafSize(root->_left) + _LeafSize(root->_right); } Node* _Copy(Node* root) { if (roo == NULL) { return; } Node* newroot = new Node(root->_data); newroot->_left = Copy(root->_left); newroot->_right = Copy(root->_right); return newroot; } void _LevelOrder(Node* root)//层次遍历 { queue<Node*> q; if (root == NULL) { return; } q.push(root);//根节点入队 while (!q.empty())//当队列不为空 { if (q.front()->_left) { q.push(q.front()->_left); } if (q.front()->_right) { q.push(q.front()->_right); } cout << q.front()->_data << " "; q.pop(); } cout << endl; } private: Node* _root;//根节点 }; void Test() { int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; BinaryTree<int> b(a, 10, '#'); b.PrevOrder(); b.InOrder(); b.PostOrder(); b.LevelOrder(); cout << "size:" << b.Size() << endl; cout << "depth:" << b.Depth() << endl; cout << "leafSize:" << b.LeafSize() << endl; } int main() { Test(); getchar(); return 0; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。