二叉树:每个节点最多两个孩子节点。
二叉树的结构: struct TreeNode
{
DataType _value; //节点值
TreeNode* _left; //左孩子
TreeNode* _ridht; //右孩子
};
二叉树的基础: 构造、拷贝构造、析构、赋值运算符的重载
二叉树的知识点: 高度、节点的个数、子节点的个数
二叉树的遍历: 前序、中序、后序遍历(递归及非递归)
遍历顺序: 前序——根左右 中序——左根右 后序——左右根
注意: 递归遍历时,应该注意不要出现栈溢出现象。
因为++index返回对象,index++返回临时变量,所以传引用做参数时有++index。
#pragma once #include<queue> #include<stack> //二叉树的结构 template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T _data; //构造函数 BinaryTreeNode(const T& x) :_left(NULL) , _right(NULL) , _data(x) {} }; template<class T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: //构造 BinaryTree() :_root(NULL) {} // a--树的节点前序遍历的数组 size--数组中元素个数 invaild--无效值即节点为空 BinaryTree(const T* a,size_t size,const T& invalid) { size_t index = 0; _root = _CreateTree(a, size,invalid,index); } //析构 ~BinaryTree() { _Destory(_root); _root = NULL; } //拷贝 BinaryTree(const BinaryTree<T>& t) { _root = _Copy(t._root); } //赋值重载(传统) //BinaryTree<T>& operator=(const BinaryTree<T>& t) //{ // if (this != &t) // { // Node* tmp = _Copy(t._root); // _Destory(_root); // _root = tmp; // } // return *this; //} //赋值重载(现代) BinaryTree<T>& operator=(BinaryTree<T> t) { swap(_root, t._root); return *this; } T& operator->() { return _root; } public: void PrevOrder()//前序 { _PrevOrder(_root); cout << endl; } void InOrder()//中序 { _InOrder(_root); cout << endl; } void PostOrder()//后序 { _PostOrder(_root); cout << endl; } size_t Size() //节点个数 { return _Size(_root); } size_t Depth() //树的深度 { return _Depth(_root); } size_t LeafSize() //叶子节点个数 { return _LeafSize(_root); } //层次遍历 void LevelOrder() { queue<Node*> q; if (_root) { q.push(_root); } while (!q.empty()) { Node* front = q.front(); cout << front->_data << " "; q.pop(); if (front->_left) { q.push(front->_left); } if (front->_right) { q.push(front->_right); } } cout << endl; } public: //非递归的前中后序遍历(栈) void PrevOrder_NonR() { stack<Node*> s; if (_root) s.push(_root); while (!s.empty()) { Node* top = s.top(); cout << top->_data << " "; s.pop(); //栈后进先出 ,所以 右先进,左先出 if (top->_right) s.push(top->_right); if (top->_left) s.push(top->_left); } cout << endl; } void InOrder_NonR() { //压左树 //取出一个节点即它的左路走完了,在访问右树(看作子问题) stack<Node*> s; Node* cur = _root; while (cur || !s.empty()) { //压树的左路节点直至最左段节点 while (cur) { s.push(cur); cur = cur->_left; } if (!s.empty()) { Node* top = s.top(); s.pop(); cout << top->_data << " "; cur=top->_right; } } cout << endl; } void PostOrder_NonR() { Node* prev = NULL; Node* cur = _root; stack<Node*> s; while (cur || !s.empty()) { //压树的左路节点直至最左段节点 while (cur) { s.push(cur); cur = cur->_left; } Node* top = s.top(); if (top->_right == NULL || top->_right == prev) { cout << top->_data << " "; s.pop(); prev = top; } else { cur = top->_right; } } cout << endl; } protected: //注意 此处index要用引用传参 Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index) { Node* root = NULL; if ((index < size) && (a[index] != invalid)) { root = new Node(a[index]); //注意下面只能用++index。此处传的是引用 //因为++index返回对象,index++返回临时变量。 root->_left = _CreateTree(a, size, invalid, ++index); root->_right = _CreateTree(a, size, invalid, ++index); } return root; } void _Destory(Node* root) { if (root == NULL) return; _Destroy(root->_left); _Destroy(root->_right); delete root; } Node* _Copy(Node* root) { if (root == NULL) return NULL; NOde* newRoot = new Node(root->_data); newRoot->_left = _Copy(root->_left); newRoot->_right = _Copy(root->_right); return newRoot; } ////////////// void _PrevOrder(Node* root) { if (root == NULL) return; cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } void _InOrder(Node* root) { if (root == NULL) return; _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); } void _PostOrder(Node* root) { if (root == NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } size_t _Size(Node* root) { if (root == NULL) return 0; return (_Size(root->_left) + _Size(root->_right) + 1); } size_t _Depth(Node* root) { if (root == NULL) return 0; size_t LeftDepth = _Depth(root->_left); size_t RightDepth = _Depth(root->_right); return (LeftDepth > RightDepth) ? (LeftDepth + 1) : (RightDepth + 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)); } private: Node *_root; };
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。