c++二叉树


 1 #pragma once
 2 template<class T>struct binaryNode {
 3     binaryNode() = default;
 4     binaryNode(T data, binaryNode<T>* father = NULL, binaryNode<T>* lson = NULL, binaryNode<T>* rson = NULL) :
 5         father(father), lson(lson), rson(rson), data(data) {}
 6     binaryNode<T>* father;
 7     binaryNode<T>* lson;
 8     binaryNode<T>* rson;
 9     T data;
10     size_t height() {
11         size_t height = 1;
12         if (lson == NULL && rson == NULL);
13         else
14             height++;
15         return height;
16     }
17     size_t size() {
18         size_t sz = 1;
19         lson == NULL ? sz : sz++;
20         rson == NULL ? sz : sz++;
21         return sz;
22     };
23     auto insertls(T data) {
24         return lson = new binaryNode<T>(data, this);
25     }
26     auto insertrs(T data) {
27         return rson = new binaryNode<T>(data, this);
28     }
29     auto remove() {
30         delete rson;
31         delete lson;
32         delete this;
33     }
34     bool operator<(const binaryNode<T>* node) { return node->data < data ? true : false; }
35     bool operator>(const binaryNode<T>* node) { return !(node < this); }
36     bool operator==(const binaryNode<T>* node) { return data == node->data; }
37 
38 };

  1 #include <iostream>
  2 #include<string>
  3 #include<binaryTree.hpp>
  4 #include<vector>
  5 #include<cassert>
  6 using namespace std;
  7 
  8 template<class T>binaryNode<T>* getNode(T num)
  9 {
 10     return new binaryNode<T>(num);
 11 
 12 };
 13 
 14 vector<size_t> getvec(size_t num) {
 15     vector<size_t>s;
 16     while (num > 1) {
 17         s.push_back(num % 2);
 18         num /= 2;
 19     }
 20     return s;
 21 }
 22 
 23 template<class T>class binaryTree {
 24 public:
 25 
 26     binaryNode<T>* top = nullptr, * curr;
 27 
 28     binaryTree() = default;
 29 
 30     binaryTree(T data, binaryNode<T>* node = new binaryNode<T>()) :top(node)
 31         //binaryTree()
 32     {
 33         sz = 0;
 34         curr = top;
 35         sz++;
 36         top->data = data;
 37     }
 38 
 39     binaryNode<T>* operator[](size_t num) {
 40         if (num == 1)return top;
 41         vector<size_t>s = getvec(num);
 42         binaryNode<T>* cp = curr;
 43         for (int i = static_cast<int>(s.size() - 1); i >= 0; --i) {
 44             if (s[i] && cp->rson)
 45                 cp = cp->rson;
 46             else if (!s[i] && cp->lson)
 47                 cp = cp->lson;
 48             else return nullptr;
 49         }
 50         return cp;
 51     }
 52 
 53     size_t size() const { return sz; }
 54 
 55     size_t height()const {
 56         return hi;
 57     }
 58 
 59     void insertls(int num, T data) { insertls(num, new binaryNode<T>(data)); }
 60 
 61     void insertrs(int num, T data) { insertrs(num, new binaryNode<T>(data)); }
 62 
 63     void insertls(int num, binaryNode<T>* node) {
 64         binaryNode<T>* get = this->operator[](num);
 65         assert(get != nullptr);
 66         if (get->rson == NULL)hi++;
 67         sz += node->size();
 68         get->lson = node;
 69     }
 70 
 71     void insertrs(int num, binaryNode<T>*node) {
 72         binaryNode<T>* get = this->operator[](num);
 73         assert(get != nullptr);
 74         if (get->lson == NULL)hi++;
 75         sz += node->size();
 76         get->rson = node;
 77     }
 78 
 79 
 80     void insertaslstree(int num, const binaryTree<T>& tree) {
 81         sz += tree.size() - tree.top->size();
 82         insertls(num, tree.top);
 83         hi--;
 84         hi += tree.height();
 85     }
 86 
 87     void insertasrstree(int num, const binaryTree<T>& tree) {
 88         sz += tree.size() - tree.top->size();
 89 
 90         insertrs(num, tree.top);
 91         hi--;
 92         hi += tree.height();
 93     }
 94     auto root() { return top; }
 95 
 96     void preorder_traverse(binaryNode<T>*node) {
 97         if (!node)return;
 98         cout << node->data<<" ";
 99         preorder_traverse(node->lson);
100         preorder_traverse(node->rson);
101     }
102 
103     void inorder_traverse(binaryNode<T>* node) {
104         if (!node)return;
105         inorder_traverse(node->lson);
106         cout << node->data << " ";
107         inorder_traverse(node->rson);
108     }
109 
110     void postorder_traverse(binaryNode<T>* node) {
111         if (!node)return;
112         postorder_traverse(node->lson);
113         postorder_traverse(node->rson);
114         cout << node->data << " ";
115     }
116 
117     void remove(int num) {
118         binaryNode<T>* get = this->operator[](num);
119         binaryNode<T>* father = this->operator[](num / 2);
120         if (get->lson || get->rson)
121         {
122             cout << "不允许remove" << endl;
123         }
124         else {
125             if (father->lson && father->rson);
126             else hi--;
127             sz--;
128             get->remove();
129         }
130     }
131 
132     bool empty() { return top == nullptr ? true : false; }
133 
134 
135 
136 private:
137     size_t sz;
138     size_t hi = top->height();
139 };
140 int main() {
141     binaryTree<char>s('i');
142     s.insertls(1, getNode('d'));
143     s.insertrs(1, getNode('l'));
144     s.insertls(2, getNode('c'));
145     s.insertrs(2, getNode('h'));
146     s.insertls(4, getNode('a'));
147     s.insertrs(8, getNode('b'));
148     s.insertls(5, getNode('f'));
149     s.insertls(10, getNode('e'));
150     s.insertrs(10, getNode('g'));
151     s.insertls(3, getNode('k'));
152     s.insertls(6, getNode('j'));
153     s.insertrs(3, getNode('n'));
154     s.insertrs(7, getNode('p'));
155     s.insertls(7, getNode('m'));
156     s.insertls(15, getNode('o'));
157     //cout << s.size();
158     //cout << s[18]->data;
159     //cout << "size:" << s.size();
160     s.inorder_traverse(s.top);
161 }