二叉树作为非线性数据结构,是以分支关系定义层次结构,以下重点为二叉树的存储结构及基本 *** 作,以及树与二叉树之间的转化,最后介绍特殊的树结构——哈夫曼树。
目录
二叉树的定义及基本 *** 作
树与二叉树之间的转化
哈夫曼树
满二叉树:深度为k且含有(2^k)-1个结点的二叉树
完全二叉树:深度为k,有n个结点的二叉树,利用层次遍历,二叉树每一个结点与编号一一对应,如下图(b):
存储方式:顺序存储(适合完全二叉树)和链式存储(又叫二叉链表)
二叉树的定义及基本 *** 作
#pragma once #include树与二叉树之间的转化using namespace std; const int ERROR = 0; const int OK = 1; typedef char ElemType; class BiTNode { public: ElemType data; BiTNode* lchild; BiTNode* rchild; }; class BiTree { public: BiTree(); BiTNode* CreateBiTree();//先序创建二叉树 BiTNode* GetRoot();//获得根结点 int GetBiTNum();//获得结点个数 void PreOrderTraverse(BiTNode* node);//先序遍历 void InOrderTraverse(BiTNode *node);//中序遍历 void PosOrderTraverse(BiTNode* node);//后序遍历 BiTNode* Copy(BiTNode* node);//二叉树复制 int Depth(BiTNode* node);//计算二叉树的深度 int NodeCount(BiTNode* node);//计算结点个数 int LeadCount(BiTNode* node); //计算叶子节点个数 bool IsSymmetric();//判断一棵二叉树是否是对称二叉树 bool IsSymmetrical(BiTNode* node1, BiTNode* node2);//两步走 void DestoryBiTree(BiTNode* node);//销毁二叉树 private: BiTNode* root; //二叉树的根节点 int m_size; //二叉树的大小 //二叉树的深度 }; BiTree::BiTree() { this->root = nullptr; this->m_size = 0; } BiTNode* BiTree::CreateBiTree() { BiTNode* T; T = new BiTNode; if (this->root == nullptr) cout << "请输入根节点(#代表空树):"; else cout << "请输入节点(#代表空树):"; ElemType ch; cin >> ch; if (ch == '#') T = nullptr; else { T->data = ch; this->m_size++; if (this->root == nullptr) root = T; T->lchild = this->CreateBiTree(); T->rchild = this->CreateBiTree(); } return T; } int BiTree::GetBiTNum() { return this->m_size; } BiTNode* BiTree::GetRoot() { return this->root; } void BiTree::PreOrderTraverse(BiTNode* node) { if (node) { cout << node->data << "t"; this->PreOrderTraverse(node->lchild); this->PreOrderTraverse(node->rchild); } } void BiTree::InOrderTraverse(BiTNode* node) { if (node) { this->InOrderTraverse(node->lchild); cout << node->data << "t"; this->InOrderTraverse(node->rchild); } } void BiTree::PosOrderTraverse(BiTNode* node) { if (node) { this->PosOrderTraverse(node->lchild); this->PosOrderTraverse(node->rchild); cout << node->data << "t"; } } BiTNode* BiTree::Copy(BiTNode* node) { BiTNode* temp; temp = new BiTNode; if (!node) temp= nullptr; else { if (!this->root) this->root = temp; temp->data = node->data; this->m_size++; temp->lchild = this->Copy(node->lchild); temp->rchild = this->Copy(node->rchild); } return temp; } int BiTree::Depth(BiTNode* node) { int m=0, n=0; if (!node) return 0; else { m = this->Depth(node->lchild); n = this->Depth(node->rchild); if (m > n) return m + 1; else return n + 1; } } int BiTree::NodeCount(BiTNode* node) { if (!node) return 0; else return NodeCount(node->lchild) + NodeCount(node->rchild) + 1; } int BiTree::LeadCount(BiTNode* node) { if (!node) return 0; if ((node->lchild == nullptr) && (node->rchild ==nullptr)) return 1; else return NodeCount(node->lchild) + NodeCount(node->rchild); } bool BiTree::IsSymmetric() { if (this->root == nullptr) return true; return this->IsSymmetrical(root->lchild, root->rchild); } bool BiTree::IsSymmetrical(BiTNode* node1, BiTNode* node2) { if (node1 == nullptr && node2 == nullptr) return true; if (node1 == nullptr || node2 == nullptr) return false; if (node1->data != node2->data) return false; return this->IsSymmetrical(node1->lchild, node2->rchild) && this->IsSymmetrical(node2->lchild, node2->rchild); } void BiTree::DestoryBiTree(BiTNode* node) { if (node == nullptr) return ; DestoryBiTree(node->lchild); DestoryBiTree(node->rchild); delete node; }
#pragma once #include哈夫曼树#include using namespace std; typedef char ElemType; class CSNode { public: ElemType data; CSNode* firstchild; CSNode* nextsibling; }; class Tree { public: Tree() { this->root = nullptr; } CSNode* CreateTree();//创建树 CSNode* GetRoot(); void PreTree(const CSNode* T);//先根遍历 void MidTree(const CSNode* T);//中根遍历 private: CSNode* root; }; CSNode* Tree::CreateTree() { CSNode* p; p = new CSNode; cout << "输入结点数据:" ; cin >> p->data; if (p->data == '#') p = nullptr; else { if (this->root == nullptr) root = p; p->firstchild = this->CreateTree(); p->nextsibling = this->CreateTree(); } return p; } CSNode* Tree::GetRoot() { return this->root; } void Tree::PreTree(const CSNode* T) { if (T) { cout << T->data << "t"; this->PreTree(T->firstchild); this->PreTree(T->nextsibling); } } void Tree::MidTree(const CSNode* T)//相当于二叉树的中序遍历 { if (T) { this->MidTree(T->firstchild); cout << T->data << "t"; this->MidTree(T->nextsibling); } } int main() { Tree K1; K1.CreateTree(); K1.PreTree(K1.GetRoot()); cout << endl; K1.MidTree(K1.GetRoot()); system("pause"); return 0; }
哈夫曼树虽然也是二叉树,但是他加上约束条件,就是带权路径长度WPL最短,由于哈夫曼树中没有结点度为1的结点,即一棵有n个叶子结点的哈夫曼树,共有n+(n+1)个结点,将其存储在定长的数组中,即采用顺序存储结构,每一个数组单元存储结点信息。
注意:如果想存储哈夫曼编码的信息,还需要附加一个node信息;
构造森林全是根,选择两小造新树,删除两小添新人,重复(2)(3)剩单根;
哈曼夫树的建立、存储及求出由哈夫曼树逆向的哈夫曼代码哈夫曼编码的相关理论和原理可参考诸多数据结构与算法。
#pragma once #include#include using namespace std; const int ERROR = 0; const int OK = 1; typedef char ElemType; class HTNode { public: int weight; int parent; int lchild; int rchild; string code; }; class HuffmanTree { public: HuffmanTree() { this->HT = nullptr; } void CreatHuffmanTree(int n);//构造哈夫曼树 void Select(int value,int& s1, int& s2); //[合并]就是将s1和s2的权值作为新节点的权值存入到第n + 1之后的数组中 //这个就是返回到构造哈夫曼树的函数里边了Select只完成[选择]和[删除]两步 void Print(int n);//打印哈夫曼树 //哈夫曼树的知识点函数 //1.根据哈夫曼树求哈夫曼编码,形成哈夫曼编码表 //2.在哈夫曼编码表的基础上,对数据文件进行编码 //3.在哈夫曼编码表的基础上,对数据文件进行译码 void CreatHuffmanCode(int n);//形成哈夫曼编码表存在HC中 private: HTNode* HT; }; void HuffmanTree::CreatHuffmanTree(int n) { if (n <= 1)return; int m = 2 * n - 1; HT = new HTNode[m+1];//开辟了2n个结点空间,但是我0位置不用,只用1~m个空间 //这2n个空间的初始化工作 for (int i = 0; i <= m; i++) { HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; HT[i].code = ""; } for (int i = 1; i <= n; i++) { cout << "请输入第" << i << "个结点的权重:" ; cin >> HT[i].weight; } //通过n-1次选择,删除,合并来创建哈夫曼树 for (int j = n + 1; j <= m; j++) { int s1, s2; this->Select(j, s1, s2); HT[s1].parent = j;//两个结点有了双亲 HT[s2].parent = j; HT[j].lchild = s1;//双亲也有了自己的孩子和权重 HT[j].rchild = s2; HT[j].weight = HT[s1].weight + HT[s2].weight; } } void HuffmanTree::Select(int value, int& s1, int& s2) { for (int i = 1; i < value; i++) { if (this->HT[i].parent == 0) { s1 = i; break;//先找到一个双亲是0的结点,就跳出循环,甭管他的权重值,先找到一个,去进行下边的循环比较 } } for (int i = 1; i < value; i++) { if (this->HT[i].parent == 0 && HT[i].weight < HT[s1].weight) { s1 = i;//这样的话就找到了权值最小的下标索引 } } for (int j = 1; j < value; j++) { if (this->HT[j].parent == 0&&j!=s1) { s2 = j; break;//先找到一个双亲是0的结点,就跳出循环,甭管他的权重值,先找到一个,去进行下边的循环比较 } } for (int j = 1; j < value; j++) { if (this->HT[j].parent == 0 && HT[j].weight < HT[s2].weight&&j!=s1) { s2 = j;//这样的话就找到了权值第二小的下标索引 } } } void HuffmanTree::Print(int n)//给你的输出结果,顺序存储结构是一个数组,那么也就是数组中元素的打印 { //输出打印那个HT数组 int m = 2 * n - 1; cout << "结点" << "t" << "weight" << "t" << "parent" << "t" << "lchild" << "t" << "rchild" << "t" << "HuffmanCode"< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)