二叉树学习笔记

 1、链表实现二叉树

// 树节点类
class Bitreenode {
    char data;
    Bitreenode* ls, * rs, * fa;  // ls为左儿子节点，rs为右儿子节点，fa为父节点
public:
    Bitreenode() {
        data = '0';
        ls = rs = fa = nullptr;
    }
    void set_ls(Bitreenode *p) {
        ls = p;
    }
    void set_rs(Bitreenode* p) {
        rs = p;
    }
    void set_data(char d) {
        data = d;
    }
    void set_fa(Bitreenode* p) {
        fa = p;
    }
    char get_data() {
        return data;
    }
    Bitreenode* get_ls() {
        return ls;
    }
    Bitreenode*  get_rs() {
        return rs;
    }
    Bitreenode* get_fa() {
        return fa;
    }
};
 
string s;  
int pos;
char son[100];
char fa[100];
 
class Bitree {
    Bitreenode* root;
    int num;
    int cnt;
    int h;
public:
 
    // 建树前初始化工作
    void Creat() {
        pos = 0;
        num = 0;
        cnt = 0;
        h = 0;
        root = creat_tree(nullptr, 0);
    }
    
    // 建树方法采用“先序遍历+空树用0表示”的方法
    Bitreenode* creat_tree(Bitreenode * fa, int height) {
        Bitreenode* cn;
        if (pos >= s.size()) {
            return nullptr;
        }
        char ch = s[pos];
        if (ch == '0') {
            pos++;
            cn = nullptr;
        }
        else {
            height++;
            h = max(h, height);
            cn = new Bitreenode;
            cn->set_data(ch);
            cn->set_fa(fa);
            num++;
            pos++;
            cn->set_ls(creat_tree(cn, height));
            cn->set_rs(creat_tree(cn, height));
        }
        return cn;
    }
 
    // 前序遍历
    void preOrder(Bitreenode *p) {
        if (p != nullptr) {
            cout << p->get_data();
            preOrder(p->get_ls());
            preOrder(p->get_rs());
        }
    }
 
    // 中序遍历
    void inOrder(Bitreenode* p) {
        if (p != nullptr) {
            inOrder(p->get_ls());
            cout << p->get_data();
            inOrder(p->get_rs());
        }
    }
 
    // 后序遍历
    void posOrder(Bitreenode* p) {
        if (p != nullptr) {
            posOrder(p->get_ls());
            posOrder(p->get_rs());
            cout << p->get_data();
        }
    }
 
    // 计算叶节点数
    int get_sonnode(Bitreenode *p) {
        if (p != nullptr) {
            if (p->get_ls() == nullptr && p->get_rs() == nullptr) {
                son[cnt] = p->get_data();
                fa[cnt] = p->get_fa()->get_data();
                cnt++;
            }
            else {
                get_sonnode(p->get_ls());
                get_sonnode(p->get_rs());
            }
        }
        return cnt;
    }
 
    // 层序遍历
    void levelOrder(Bitreenode* p) {
        queue q;
        if (p == nullptr) {
            return;
        }
        q.push(p);
        while (q.empty() != 1) {
            p = q.front();
            q.pop();
            cout << p->get_data();
            if (p->get_ls() != nullptr) {
                q.push(p->get_ls());
            }
            if (p->get_rs() != nullptr) {
                q.push(p->get_rs());
            }
            
        }
    }
    
    // 返回根节点
    Bitreenode* get_root() {
        return root;
    }
 
    // 返回树的深度
    int get_h() {
        return h;
    }
};

2、数组实现二叉树

#include 
#include 
#include 
#include 
#include
using namespace std;
 
struct Bitree {
	int data;
	int ls;
	int rs;
};
 
void preOrder(Bitree * p, int n, int pos) {
	if(p[pos].data != 0) {
		cout << p[pos].data << " ";
		if(p[pos].ls != -1)preOrder(p, n, p[pos].ls);
		if(p[pos].rs != -1)preOrder(p, n, p[pos].rs);
	}
}
 
int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		Bitree* p = new Bitree[n + 1];
		for (int i = 1; i <= n; i++) {
			cin >> p[i].data;
			if (2 * i <= n) {
				p[i].ls = 2 * i;
			}
			else p[i].ls = -1;
 
			if (2 * i + 1 <= n) {
				p[i].rs = 2 * i + 1;
			}
			else p[i].rs = -1;
		}
		preOrder(p, n, 1);
		cout << endl;
	}
	return 0;
}

3、赫夫曼编码树

#include
#include
using namespace std;
 
// 节点
struct huffmannode {
    int weight;
    int fa, ls, rs;
    string code;
    char mean;
};
 
class huffmantree {
    huffmannode** tree;
    int n;
public:
    huffmantree() {}
    
    // 建树
    void build_tree() {
        cin >> n;
        tree = new  huffmannode*[2*n];
        for (int i = 1; i <= n; i++) {
            tree[i] = new huffmannode;
            cin >> tree[i]->weight;
            tree[i]->fa = tree[i]->ls = tree[i]->rs = 0;
            tree[i]->code = "";
        }
        for (int i = 1; i <= n; i++) {
            cin >> tree[i]->mean;
        }
        for (int i = n + 1; i <= 2 * n - 1; i++) {
            tree[i] = new huffmannode;
            tree[i]->weight = 0;
            tree[i]->fa = tree[i]->ls = tree[i]->rs = 0;
            tree[i]->code = "";
            tree[i]->mean = '%';
        }
        for (int i = n + 1; i <= 2 * n - 1; i++) {
            int s1, s2;
            search(i, s1, s2);
            tree[i]->ls = s1, tree[i]->rs = s2;
            tree[i]->weight = tree[s1]->weight + tree[s2]->weight;
        }
    }
 
    // 寻找weight最小的两个节点
    void search(int idx, int& s1, int& s2) {
        int minn = 99999999;
        for (int i = 1; i < idx; i++) {
            if (minn > tree[i]->weight && tree[i]->fa == 0) {
                minn = tree[i]->weight;
                s1 = i;
            }
        }
        tree[s1]->fa = idx;
        minn = 99999999;
        for (int i = 1; i < idx; i++) {
            if (minn > tree[i]->weight && tree[i]->fa == 0) {
                minn = tree[i]->weight;
                s2 = i;
            }
        }
        tree[s2]->fa = idx;
    }
 
 
    // 编码
    void build_code() {
        for (int i = 1; i <= n; i++) {
            int fa = tree[i]->fa;
            int son = i;
            while (fa != 0) {
                if (tree[fa]->ls == son) {
                    tree[i]->code = "0" + tree[i]->code;
                }
                else if (tree[fa]->rs == son) {
                    tree[i]->code = "1" + tree[i]->code;
                }
                son = fa;
                fa = tree[fa]->fa;
            }
        }
    }
 
    // 展示编码
    void show_code() {
        for (int i = 1; i <= n; i++) {
            cout << tree[i]->weight << "-" << tree[i]->code << endl;
        }
    }
 
    // 解码
    int Decode(const string codestr, string &txtstr) {
        int p = 2 * n - 1;
        for (int i = 0; i < codestr.size(); i++) {
            char ch = codestr[i];
            if (ch == '0') p = tree[p]->ls;
            else if (ch == '1') p = tree[p]->rs;
            else return -1;
 
            if (tree[p]->ls == 0) {
                txtstr += tree[p]->mean;
                p = 2 * n - 1;
            }
            else if(tree[p]->ls != 0 && i == codestr.size() - 1) {
                return -1;
            }
        }
        return 1;
    }
};
 
int main() {
    huffmantree tree;
    tree.build_tree();
    int t;
    cin >> t;
    while (t--) {
        string codestr = "", txtstr = "";
        cin >> codestr;
        if (tree.Decode(codestr, txtstr) == 1) {
            cout << txtstr << endl;
        }
        else {
            cout << "error" << endl;
        }
    }
    return 0;
}