二叉樹

構建：二叉樹的構建采用的是先序遍歷，->先儲存根節點然后左右節點，用遞歸的思想將所有數據放在樹中。

代碼實現：實現了4種訪問方法，先序，中序，后序，和層序的訪問方法都采用遞歸的方式。

#include<iostream> #include<queue> #include<stack> using?namespace?std;template<class?T>? struct?rootnode {T?_value;rootnode<T>?*_leftnode;rootnode<T>?*_rightnode;rootnode<T>(T?value):?_value(value),_leftnode(NULL),_rightnode(NULL){} };template?<class?T> class?BinaryTree { public:BinaryTree<T>(?T?*str){T?*tmp?=?str;_root?=?_BinaryTree(tmp);}~BinaryTree(){_Clear(_root);}BinaryTree<T>?(BinaryTree?&t){_root=_Copy(t._root);}BinaryTree<T>&?operator=(BinaryTree?t){if?(*this?!=?t){swap(_root,?t._root);}}void?Fastorder(){_Fastorder(_root);}void?Inorder(){_Inorder(_root);}void?Postorder(){_Postorder(_root);}void?Levelorder(){queue<rootnode<T>*>?q;if?(_root?==?NULL){return;}q.push(_root);while?(!q.empty()){rootnode<T>*?root?=?q.front();cout?<<?root->_value;q.pop();if?(root->_leftnode?!=?NULL){q.push(root->_leftnode);}if?(root->_rightnode?!=?NULL){q.push(root->_rightnode);}} }int?leafnum(){int?num?=?0;num=_Leafnum(_root,num);return?num;}int?Size(){int?size?=?0;_Size(_root,size);return?size;}int?Depth(){int?Depth?=?_Depth(_root);return?Depth;}void?NRfastorder(){stack<rootnode<T>*>?s;if?(_root?!=?NULL){s.push(_root);}while?(!s.empty()){rootnode<T>*?front=s.top();cout<<front->_value;s.pop();if?(front->_rightnode?!=?NULL){s.push(front->_rightnode);}if?(front->_leftnode?!=?NULL){s.push(front->_leftnode);}}}void?NRinorder(){stack<rootnode<T>*>s;rootnode<T>*cur?=?_root;rootnode<T>*?top?=?NULL;while?(cur||!s.empty()){while?(cur){s.push(cur);cur?=?cur->_leftnode;} if?(top?!=?s.top()->_rightnode){top?=?s.top();cout?<<?top->_value;s.pop();cur?=?top->_rightnode;}else{top?=?s.top();cout?<<?top->_value;s.pop();}}}void?NRpostorder(){rootnode<T>*cur?=?_root;stack<rootnode<T>*>?s;rootnode<T>*top?=?NULL;while?(cur?||?!s.empty()){while?(cur){s.push(cur);cur?=?cur->_leftnode;}if?(s.top()->_rightnode?!=?NULL&&top?!=?s.top()->_rightnode){top?=?s.top();cur?=?top->_rightnode;}else{top?=?s.top();s.pop();cout?<<?top->_value;}}} protected:rootnode<T>*?_BinaryTree(T?*&str){rootnode<T>?*root?=?NULL;if?(*str?!=?'#'&&*str?!=?'\0'){root?=?new?rootnode<T>(*str);str++;root->_leftnode?=?_BinaryTree(str);str++;root->_rightnode?=?_BinaryTree(str);}return?root;}void?_Fastorder(rootnode<T>?*&root){if?(root?==?NULL){return;}else{cout?<<?root->_value;_Fastorder(root->_leftnode);_Fastorder(root->_rightnode);}}void?_Inorder(rootnode<T>?*root){if?(root?==?NULL){return;}_Inorder(root->_leftnode);cout?<<?root->_value;_Inorder(root->_rightnode);}void?_Postorder(rootnode<T>?*root){if?(root?==?NULL){return;}_Postorder(root->_leftnode);_Postorder(root->_rightnode);cout?<<?root->_value;}void?_Clear(rootnode<T>?*root){if?(root?==?NULL){return;}rootnode<T>?*tmp?=?root->_leftnode;rootnode<T>?*tmp2?=?root->_rightnode;delete?root;_Clear(tmp);_Clear(tmp2);}rootnode<T>*?_Copy(rootnode<T>?*root){rootnode<T>?*newroot?=?NULL;if?(root?==?NULL){return?newroot;}newroot?=?new?rootnode<T>(root->_value);newroot->_leftnode?=?_Copy(root->_leftnode);newroot->_rightnode?=?_Copy(root->_rightnode);return?newroot;}int?_Size(rootnode<T>?*root,int?&size){if?(root?==?NULL){return?0;}size++;_Size(root->_leftnode,size);_Size(root->_rightnode,size);return?size;}int?_Depth(rootnode<T>?*root){if?(root==NULL){return?0;}int?hight?=?1;int?left?=?0;int?right?=?0;left?+=?_Depth(root->_leftnode)?+?hight;right?+=?_Depth(root->_rightnode)?+?hight;if?(left?>?right){return?left;}else{return?right;}}int?_Leafnum(rootnode<T>*?root,int?&num){if?(root?==?NULL){return?0;}if?(root->_leftnode?==?NULL&&root->_rightnode?==?NULL){num++;}_Leafnum(root->_leftnode,?num);_Leafnum(root->_rightnode,?num);return?num;} private:rootnode<T>?*_root; };void?Test1() {char?*str?=?"123##45##6##78###";BinaryTree<char>?b1(str);BinaryTree<char>?b2(b1);BinaryTree<char>?b3?=?b2;b1.Fastorder();cout?<<?endl;b1.Inorder();cout?<<?endl;b1.Postorder();cout?<<?endl;b2.Fastorder();cout?<<?endl;b3.Fastorder();cout?<<?endl;cout?<<?b3.Size()<<endl;cout?<<?b3.Depth()?<<?endl;b3.Levelorder();cout?<<?endl;cout?<<?b3.leafnum()<<endl; } int?main() {????Test1(); }

轉載于:https://blog.51cto.com/wpfbcr/1760648

總結

以上是生活随笔為你收集整理的数据结构--二叉树(1)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。