c++二叉树demo

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

 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 };