1.二叉树的性质:
- 第i层最多有2^(i-1)个节点,当然i>=1的。
- 深度为k的二叉树最多有2^k-1个节点。
- 对任何一棵二叉树T,如果其终端的节点为n0,度为2的节点为n2,则n0=n2+1。也就是叶子结点的数量=有两个儿子的非叶子节点+1。总的分支线为(n-1)条。n-1=2*n2 + 1*n1。树T的节点总数为n=n0+n1+n2。可以推导出n0=n2+1。
- 具有n个节点的完全二叉树的深度为floor( log2(n) )+1
- 具有n个节点的完全二叉树,节点按照层的编号(从第一层到第floor(log2(n))+1层,每层从左到右),对于任意的节点i(1<=1<=n):1)如果i=1,则节点i时二叉树的根。2)如果2*i>n则节点没有左孩子;否则其左孩子节点为2*i。3)如果2*i+1>n,则节点没有有儿子,否则其左孩子节点为2*i+1。4)这个性质对于二叉堆的实现特别有用哦。(要注意一下:如果i从0开始,且<n,那么i的父亲为floor((i-1)/2),i的左孩子是2*i+1哦):)
- 树的高度:从节点x向下到某一个叶节点的最大的简单路径的边条数。求任意的节点的深度就可以从左右儿子两边时,向上到达节点,那个最大高度就是他。
- 树的深度:感觉就是所在的层数(待查证)
- 最深叶节点的深度就是树的深度,树根节点的高度就是树的高度。
2.二叉树有哪些?
- 满二叉树:所有的非叶子节点的度为2,且所有的叶子结点都在同一层上,就是满二叉树。
- 完全二叉树:1)叶子只出现在最下两层。2)最下层的叶子一定集中在左部连续的位置。3)倒数二层,若有叶子结点,一定在右部的连续位置。4)如果节点度为1,则节点只有左孩子。5)同样节点的二叉树,完全二叉树的深度最小。如何判断?一颗深度为k二叉树,有n个节点,然后,也对这棵树进行按层从左向右编号,如果所有的编号都和满二叉树对应,那么这棵树是完全二叉树。如果出现编号空挡,就不是完全二叉树。
3.前序遍历、中序遍历和后续遍历:PLR、LPR和LRP,P表示根节点、L左子树或左儿子、R右子树或右儿子。
4.线索化:对于n个节点的二叉树,存在2*n-(n-1)=n+1空闲的个指针域。所以希望利用这些空闲的指针域。对于建立中序遍历的线索树:需要沿着他的遍历方向(所以建立的过程类似于中序遍历),但需要同时修改pre前驱。前驱和后继就是所谓的线索,一般而言空的左子树的指针域为前驱,右子树的为后继。访问呢的时候,和中序一样递归到最左的儿子,然后以此为起点进行遍历,但是需要注意的是,每次访问右子树的时候需要将以右子树为下一个循环的起点。这样可以极大的缩短遍历的时间。
5.二叉树以及三种便利、线索化的实现:
#include <stack> #include <iostream> #include <queue> using namespace std; template<typename T> class BinaryTreeNode { typedef T DataType; typedef BinaryTreeNode<DataType> NodeType; typedef NodeType *Node; public: BinaryTreeNode():leftchild(nullptr),rightchild(nullptr){} BinaryTreeNode(DataType da,Node l=nullptr,Node r=nullptr):leftchild(l),rightchild(r),data(da){} //获取 DataType &getData() { return data; } //设置左儿子 void setLeftchild(Node l) { leftchild = l; } //设置右儿子 void setRightchild(Node r) { rightchild = r; } //获取左儿子 Node getLeftchild() { return leftchild; } //获取右儿子 Node getRightchild() { return rightchild; } //析构函数 Node由管理类释放 ~BinaryTreeNode(){} //获取左儿子的状态 是否是线索(前驱) bool getLeftchildStatus() { return leftThread; } //获取右儿子的状态 是否是线索(后继) bool getRightchildStatus() { return rightThread; } //设置左儿子的状态 是否是线索(前驱) void setLeftchildStatus(bool status) { leftThread = status; } //设置右儿子的状态 是否是线索(后继) void setRightchildStatus(bool status) { rightThread = status; } private: Node leftchild; Node rightchild; DataType data; //这是用来线索化的二叉树标志 bool leftThread=false; bool rightThread=false; }; template<typename T> class BinaryTreeList { public: //类型别名 typedef T DataType; typedef BinaryTreeNode<DataType> NodeType; typedef NodeType *Node; //构造函数 BinaryTreeList(DataType init) :root(new NodeType) { root->getData() = init; } //各种操作 //访问 //获取根节点 Node &getRoot() { return root; } DataType &Retrieve(Node node) { return node->getData(); } //更改 //插入右子节点 void insert_right(Node parent,DataType da) { Node nd = new NodeType(da); nd->setRightchild(parent->getRightchild()); parent->setRightchild(nd); } //插入左子节点 void insert_left(Node parent,DataType da) { Node nd = new NodeType(da); nd->setLeftchild(parent->getLeftchild()); parent->setLeftchild(nd); } //删除节点 //注意要判断删除的是叶子还是非叶子 void erase_left(Node node) { destroy(node->getLeftchild()); node->setLeftchild(nullptr); } void erase_right(Node node) { destroy(node->getRightchild()); node->setRightchild(nullptr); } //释放所有节点 void clear() { destroy(root); root = nullptr; } ~BinaryTreeList() { clear(); } //遍历 //前序遍历 void PreOrder(Node p) { if (p != nullptr) { cout << p->getData() << " "; PreOrder(p->getLeftchild()); PreOrder(p->getRightchild()); } } void PreOrder_Stack(Node p) { std::stack<NodeType*> sta; Node root = p; while (sta.empty() == false || root != nullptr)//只要栈不为空 那么就要 { while (root) { sta.push(root); cout << root->getData() << " "; root = root->getLeftchild(); } root = sta.top();//此时的top是深度最大的左叶子 sta.pop();//把那个将要访问的pop root = root->getRightchild();//将要访问的叶子节点的父节点的值 左儿子已经处理过了 所以这个root要被更新为父节点的右儿子然后在对右儿子进行处理 } cout << endl; } //中序遍历 void InOrderTraverse(Node root) { if (root != nullptr) { InOrderTraverse(root->getLeftchild()); cout << root->getData() << " "; InOrderTraverse(root->getRightchild()); } } void InOrderTraverse_Stack(Node root) { stack<Node> nodes; Node p = root; while (!nodes.empty() || p != nullptr) { while (p) { nodes.push(p); p = p->getLeftchild(); } if (nodes.empty() == false) { p = nodes.top(); cout << p->getData() << " "; nodes.pop(); p = p->getRightchild(); } } cout << endl; } //后续遍历 void PostOrderTraverse(Node p) { if (p != nullptr) { PostOrderTraverse(p->getLeftchild()); PostOrderTraverse(p->getRightchild()); std::cout << p->getData() << " "; } } void PostOrderTraverse_Stack(Node root) { stack<Node> sta; Node p = root; Node prev = nullptr; while (!sta.empty() || p != nullptr) { while (p) { sta.push(p); p = p->getLeftchild(); } p = sta.top(); //分析当前的栈顶元素 此时是没有左儿子的 if (p->getRightchild() ==nullptr /*叶子节点直接访问*/|| p->getRightchild() ==prev/*如果左儿子为null 而且右儿子先前被访问过(说明要访问该节点(LR的父亲))*/) { cout << p->getData() << " "; prev = p; sta.pop();//将这个节点从栈中pop p = nullptr;//将p设置为nullptr是为了不要又开始搜索左儿子 应该访问栈顶了 } else { //sta.pop(); p = p->getRightchild();//不满足条件 那么应该继续搜索右儿子 } } cout << endl; } //层次遍历 void LevelOrderTraverse(Node root) { queue<Node> que; Node p = root; if (p != nullptr) { que.push(p);//首元素入队 while (!que.empty()) //只要队列不为空的话 { p = que.front();//获取对头元素 cout << p->getData() << " "; que.pop();//出对 将对头元素转移到与之同级的右节点上 然后该节点的左右子树分别入队 if (p->getLeftchild()) que.push(p->getLeftchild()); if (p->getRightchild()) que.push(p->getRightchild()); } } cout << endl; } //线索化操作 //建立前序搜索关联 void InOrderThread(Node root) { Node pre = nullptr;//这个指针总是保存之前访问的位置 InOrderThread_Process(root, pre); } //中序线索遍历 void Display_InOrderThread(Node root) { for (Node p = InOrder_FindFirst(root); p != nullptr; p = InOrder_NextNode(p)) cout << p->getData() << " "; cout << endl; } // 前序搜索建立 //建立前序搜索关联 void PreOrderThread(Node root) { Node pre = nullptr;//这个指针总是保存之前访问的位置 PreOrderThread_Process(root, pre); } //前序线索树显示 void Display_PreOrderThread(Node root) { Node d = root; while (d != nullptr) { cout << d->getData() << " "; d = PreOrder_NextNode(d); } cout << endl; } //后续线索化 void PostOrderThread(Node root) { Node pre = nullptr; PostOrderThread_Process(root, pre); } //显示线索化 void Display_PostOrderThread(Node root) { Node p = PostOrderThread_FindFirstNode(root); while (p != nullptr) { cout << p->getData() << " "; p = PostOrderThread_NextNode(p); } cout << endl; } //清除指定根节点以及他的子树的线索信息 void clearAllThreads(Node r) { if (r != nullptr) { clearAllThreads(r->getLeftchild()); clearAllThreads(r->getRightchild()); if (r->getLeftchildStatus() == true) { r->setLeftchildStatus(false); r->setLeftchild(nullptr); } if (r->getLeftchildStatus() == true) { r->setRightchild(nullptr); r->setRightchildStatus(false); } } } private: Node root;//保存根节点 void destroy(Node r) { if (r != nullptr) { if (r->getLeftchildStatus() == false)//如果不是修改后的指针域才会释放他们 避免二次释放 { destroy(r->getLeftchild()); } if (r->getRightchildStatus() == false) { destroy(r->getRightchild()); } delete r; } } //中序线索化 私有函数 void InOrderThread_Process(Node root, Node &pre) { if (root != nullptr) { InOrderThread_Process(root->getLeftchild(), pre);//遍历左子树 if (root->getLeftchild() == nullptr) { //没有左孩子 root->setLeftchildStatus(true); root->setLeftchild(pre);//将左孩子的指正改为前驱 指向树的前驱节点(也就是pre) } if (pre!=nullptr /*这个要判断*/ &&pre->getRightchild() == nullptr) { //前一个节点没有右孩子 pre->setRightchildStatus(true); pre->setRightchild(root); } pre = root;//这个pre是一个引用 所以能够保证指向的是root!=nullptr的前一个节点 InOrderThread_Process(root->getRightchild(), pre);//如果没有右儿子 那么会自动结束当前的递归 从而可以把root定位到原root的父节点 pre已经更新到root } } //寻找中序遍历的起点 最左的左儿子 Node InOrder_FindFirst(Node o) { if (o != nullptr) { Node first = o; while (first->getLeftchildStatus() == false) first = first->getLeftchild(); return first; } else { return nullptr; } } //寻找中序遍历后续的节点 可能是右儿子(因为是中序遍历)或者是指定的后继 Node InOrder_NextNode(Node p) { if (p == nullptr) { return nullptr; } else { if (p->getRightchildStatus() == false) return InOrder_FindFirst(p->getRightchild());//右子树的第一个结点(右子树的最左的儿子) else return p->getRightchild();//或后继 } } //寻找前序线索遍历的下一个节点 Node PreOrder_NextNode(Node p) { if (p == nullptr) { return nullptr; } else { if (p->getLeftchildStatus() == false)//如果左儿子不是空的话 返回的下一个节点就是左儿子 { return p->getLeftchild(); } else { return p->getRightchild();//如果左儿子为空的话(此时节点指的是前驱)那么就返回他的右儿子 } } } //前序线索便利构造 void PreOrderThread_Process(Node root, Node &pre) { if (root != nullptr) { if (root->getLeftchild() == nullptr) { //没有左儿子 那这个左儿子域就用来保存前驱节点的指针 root->setLeftchildStatus(true); root->setLeftchild(pre); } if (pre && pre->getRightchild() == nullptr)//前一个结点没有指针的位置 那么就让他指向下一个节点 { pre->setRightchildStatus(true); pre->setRightchild(root); } pre = root; if (root->getLeftchildStatus() == false)//如果还有左儿子 那么也需要对左儿子建立线索 { PreOrderThread_Process(root->getLeftchild(), pre); } if (root->getRightchildStatus() == false)//如果还有左右儿子 那么也需要对右儿子建立线索 { PreOrderThread_Process(root->getRightchild(), pre); } } } //后续线索遍历 void PostOrderThread_Process(Node root, Node &pre) { if (root != nullptr) { if (root->getLeftchildStatus() == false) PostOrderThread_Process(root->getLeftchild(), pre); if (root->getRightchildStatus() == false) PostOrderThread_Process(root->getRightchild(), pre); if (root->getLeftchild() == nullptr) { root->setLeftchild(pre); root->setLeftchildStatus(true); } if (pre !=nullptr && pre->getRightchildStatus() == false) { pre->setRightchild(root); pre->setRightchildStatus(true); } pre = root; } } Node PostOrderThread_FindFirstNode(Node nd) { if (nd != nullptr) { //用来寻找最深层的节点 while (nd->getLeftchild()) nd = nd->getLeftchild(); return nd; } else { return nullptr; } } //后续线索的下一个节点 Node PostOrderThread_NextNode(Node root) { if (root != nullptr) { if (root->getRightchildStatus() == false) { //存在右儿子 if (root->getLeftchildStatus() == false)//如果存在左儿子的话 也就是到达了第一个有两个儿子的节点 那么我们认为他是不需要遍历的节点 { return nullptr; } else { return PostOrderThread_FindFirstNode(root->getLeftchild());//存在右儿子 左儿子是前驱 那么我们就搜索他的子树 从最低的左儿子开始遍历 } } else { return root->getRightchild();//右儿子是后继 直接返回右儿子 } } else { return nullptr; } } };
6.哈夫曼树:最优二叉树,每次选取频数最小的两个子树或者节点,构建一颗二叉树,然后放入优先队列中。频数最大的节点就会出现在数离根节点最近的地方。所以他的字符映射的长度就会是最小的
#include <algorithm> #include <map> #include <vector> #include <utility> #include <unordered_map> #include <queue> #include <iostream> #include <tchar.h> #include <string> using namespace std; class HuffmanTreeNodeBase { public: //构造函数必须提供频数或频数之和 HuffmanTreeNodeBase(int f) :flag(f) {} //获取flag值 对于叶子节点派生类这个保存的是频数 对于节点保存的是两个flag的频数纸盒之和 int getFlag() const { return flag; } //设置flag void setFlag(int w) { flag = w; } virtual ~HuffmanTreeNodeBase() {} private: int flag;//表示这个节点的值 }; class HuffmanLeafTree :public HuffmanTreeNodeBase { public: //必须提供叶子节点频数和代表的字符 HuffmanLeafTree(int f, char c) :HuffmanTreeNodeBase(f), ch(c) {} //获取叶子节点代表的字符 char getChar() { return ch; } //设置叶子节点代表的字符 void setChar(char c) { ch = c; } ~HuffmanLeafTree() {} private: char ch;//这个表示叶子节点的被编码的符号 }; class HuffmanTreeNode : public HuffmanTreeNodeBase { typedef HuffmanTreeNodeBase *Node; public: //提供频数和频数之和 左儿子节点指针 右儿子节点指针 HuffmanTreeNode(int flag, Node l, Node r) :HuffmanTreeNodeBase(flag), left(l), right(r) {} ~HuffmanTreeNode() { delete left; //析构函数 delete right; } //获取左儿子节点指针 Node getLeftchild() { return left; } //获取右儿子节点指针 Node getRightchild() { return right; } private: Node left; Node right; }; class Huffman { public: typedef std::map<char, int> Charfrenquent;//这个用来保存被编码的字符的出现的频数 typedef std::vector<int> Encoding;//这个用来保存一组哈夫曼编码 typedef std::map<char, Encoding> CharMap;//这个用来保存对应字符的编码表 //构造函数 Huffman() {} //这个用来整理map 频率最小的排在前面 现在已经不使用 void sortMap(std::unordered_map<char, int> &ma) { std::vector<std::pair<char, int>> res; for (auto iter = ma.begin(); iter != ma.end(); ++iter) res.push_back(std::make_pair(iter->first, iter->second)); std::sort(res.begin(), res.end(), [](const std::pair<char, int> &c1, std::pair<char, int> &c2) { return c1.second < c2.second; } ); //重新排序 ma.clear(); for (auto i = res.cbegin(); i != res.cend(); ++i) ma[i->first] = i->second; } //这个函数用来计算字符出现的频率 第三个参数是输出的保存字符对应平频率的映射表 void calcFrenquentofChars(const char *c, int size, Charfrenquent &cf) { if (c != nullptr && size > 0) { for (int i = 0; i < size; ++i) { cf[c[i]]++; } //sortMap(cf); } } //这个用来生成哈夫曼树 需要获取已知的频率映射表 生成的树依据最优二叉树的规则 HuffmanTreeNodeBase *buildHuffmanTree(Charfrenquent &cf) { auto j = [](const HuffmanTreeNodeBase *c1, const HuffmanTreeNodeBase *c2) { return c1->getFlag() > c2->getFlag();/*如果返回的是true表示后面的频数比前面的小 那么就需要吧后面的和前面的交换顺序*/ };//这个用来设置优先队列最先出出对的佘顺序 依据的是频数 频数最小的先出来 std::priority_queue < HuffmanTreeNodeBase*, std::vector<HuffmanTreeNodeBase*>, decltype(j)> trees(j); for (auto i = cf.begin(); i != cf.end(); ++i) trees.push(new HuffmanLeafTree(i->second, i->first)); //优先队列 while (trees.size() > 1) { //从优先队列出来是频数最小的字符 HuffmanTreeNodeBase *le = trees.top(); trees.pop(); HuffmanTreeNodeBase *ri = trees.top(); trees.pop(); HuffmanTreeNode *nd = new HuffmanTreeNode(le->getFlag() + ri->getFlag(), le, ri);//新建的一个Node节点 由于是base的派生类 所以指针是可以插入的 trees.push(nd);//把这个节点插入优先队列 } return trees.top(); } //这个用来生成哈夫曼编码 charmap输出的就是字符对应的编码 用vector保存 第三个参数用来验证是否只存在一个编码的情况 void genrateCode(HuffmanTreeNodeBase *tree, CharMap &cm, Charfrenquent &fren) { Encoding enc;//这个是用于临时保存的vector if (fren.size() == 1) { enc.push_back(0); } else { if (fren.size() <= 0) return; } do_genrateCode(tree, enc, cm); } std::string deCoding(CharMap &cm, std::string &encodedstr) { std::string result; std::map<std::string, char> reverseMap; for (CharMap::const_iterator it = cm.cbegin(); it != cm.cend(); ++it) { std::string k; for (Encoding::const_iterator i = it->second.cbegin(); i != it->second.cend(); ++i) k.push_back(*i + '0');//将vector中的编码序列变成字符串的形式 注意int和char类型的互换 reverseMap.insert(std::make_pair(k, it->first));//将键值对插入map } //反向映射表建立完成 auto beg = encodedstr.cbegin(); auto end = encodedstr.cend(); auto range = ++encodedstr.cbegin();//这个表示范围的有开区间 我们将会从[Beg,range) 中构建查找的字符串 beg!=range 否则为空字符串 int cnt = 0;//cnt计数用于吧beg递增到最近一次匹配位置的尾后 while (beg != end) { char dest; bool changeres = match_str(reverseMap, beg, range, dest);//查找 if (changeres == true) { result.push_back(dest); for (int i = 0; i <= cnt; ++i) { ++beg; } if (range == end)//如果此时的匹配之后range的位置是尾后 那么表示这是最后一次成功的匹配 就结束while break; range = beg + 1;//range>beg cnt = 0;//cntc重新开始计数 } else { ++cnt;//如果匹配失败 那么一旦匹配成功那么bg会递增到beg+cnt+1的位置 ++range;//范围也要递增 } } return result; } ~Huffman() {} private: void do_genrateCode(HuffmanTreeNodeBase *tree, Encoding &precode, CharMap &charmap) { if (tree == nullptr) return; HuffmanLeafTree *leaf = dynamic_cast<HuffmanLeafTree*>(tree); if (leaf) { //表示这个指针是叶子节点 那么就设置该字符的编码 编码保存在int的vector中 charmap[leaf->getChar()] = precode; } else { HuffmanTreeNode *nd = dynamic_cast<HuffmanTreeNode*>(tree); if (nd) { //表示这是节点 所以还是必须把编码压入vector Encoding leftcode = precode;//这里定义一个新的vector他是用来防止不同的vector编码冲突的问题 leftcode.push_back(0);//做儿子的话 路径上的权为0 do_genrateCode(nd->getLeftchild(), leftcode, charmap);//从左儿子开始 递归 Encoding rightcode = precode;//解释同上 rightcode.push_back(1); do_genrateCode(nd->getRightchild(), rightcode, charmap); } } } //这个用来寻找哈夫曼序列对应的字符 第一个参数是映射表 [beg,end) 注意beg !=end 表示要匹配的迭代器范围 bool match_str(std::map<std::string, char> reverseMap, string::const_iterator beg_match, std::string::const_iterator end_match, char &res) { std::string s(beg_match, end_match);//构建一个临时的字符串 auto r = reverseMap.find(s);//根据字符串查找对应的哈夫曼字符映射 if (r == reverseMap.end()) { //如果没有找到的话 返回的是end迭代器 return false; } else { res = r->second;//找到了映射 return true; } } }; int main() { const char *c; int sz; cout << "请输入要编码的序列:"; std::string s; cin >> s; c = s.c_str(); sz = s.size(); Huffman hmf;//哈夫曼对象 Huffman::Charfrenquent hmf_freq;//字符出现的频数 hmf.calcFrenquentofChars(c, sz, hmf_freq); HuffmanTreeNodeBase *tree = hmf.buildHuffmanTree(hmf_freq);//得到地哈夫曼树 Huffman::CharMap hmf_map;//哈夫曼映射表 hmf.genrateCode(tree, hmf_map, hmf_freq); delete tree; int orgsz = 0; int zipsz = 0; //计算应该的长度 int cnt = 0; int weight = 1; int t = hmf_map.size(); while (1) { if (t == 1) { cnt = 1; break; } if (t - weight <= 0) { break; } else { weight *= 2; ++cnt; } } //cnt就应该要编码的二进制的位数 orgsz = sz*cnt; cout << endl << "获得的哈夫曼编码映射为:" << endl; for (auto i = hmf_map.cbegin(); i != hmf_map.cend(); ++i) { cout << "[" << i->first << "]="; for (int j = 0; j < (i->second).size(); ++j) { cout << i->second[j]; } cout << endl; } std::string hfm_encodedstr;//这个表示哈夫曼编码后的二进制 cout << "得到的哈夫曼字符编码为:"; for (int i = 0; i < sz; ++i) { for (int j = 0; j < hmf_map[c[i]].size(); ++j) { cout << hmf_map[c[i]][j]; hfm_encodedstr.push_back(hmf_map[c[i]][j] + '0'); ++zipsz;//压缩后大小计算 } cout << " "; } cout << endl << "原始编码长度:" << orgsz << ",编码后长度:" << zipsz << " 压缩率为:" << (static_cast<float>(zipsz) / orgsz) << endl; cout << "解码后:" << hmf.deCoding(hmf_map, hfm_encodedstr) << endl;//重新解码 return 0; }
为什么需要二叉树呢?因为一个char类型字符可能需要8位来表示。而如果转换成0和1表示,就可以使用floor((log2(N))个0 1 序列表示。假设一共所有的字符可以用宽位4的二进制位表示,那么一个8位就可以用来表示两个字符,积少成多就可以省下很多的空间。有点让我想起了可以用int表示32个真假逻辑值。
7.平衡树:每当插入节点时,可能会使二叉树变成一个链表,这会严重降低二叉树的搜索性能,最坏的时间复杂度会达到O(N)。所以我们仍然需要做出一些调整,使得二叉树能够在floor(log2(N))的时间查找一个节点。所以就需要不断地调整。
- AVL树:比较简单的平衡查找树。平衡因子就是左右子树高度之差的绝对值不超过1,就认为是平衡的。如果定义平衡因子=左子树高度-右子树高度。如果没有子树,对应的高度为-1。插入新元素后,不满足的平衡的四种情况:
参考:
- 树的高度与深度:http://blog.csdn.net/fanpei_moukoy/article/details/23828603
- 《算法之美》
- 《大话数据结构》