数据结构之树
2018-06-27 10:06:18来源:未知 阅读 ()
树
树型结构是一类重要的非线性数据结构。树是n(n>=0)个结点的有限集。在任意一颗非空树中,有且仅有
一个特定的称为根的结点;当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tm,其中每一个
集合本身又是一棵树,并且称为根的子树。因此树的数据结构定义为:
#define ElemType char typedef struct BinTreeNode { ElemType data; BinTreeNode *leftChild; BinTreeNode *rightChild; }BinTreeNode; typedef struct BinTree { BinTreeNode *root; }BinTree;
在树型结构中可以进行以下操作:
void InitBinTree(BinTree *t); void CreateBinTree(BinTree *t); void CreateBinTree(BinTreeNode *&t); int Size(BinTree *t); int Size(BinTreeNode *t); int Height(BinTree *t); int Height(BinTreeNode *t); BinTreeNode* Find(BinTree *t, ElemType key); BinTreeNode* Find(BinTreeNode *t, ElemType key); BinTreeNode* LeftChild(BinTreeNode *t); BinTreeNode* RightChild(BinTreeNode *t); BinTreeNode* Parent(BinTree *t, ElemType key); BinTreeNode* Parent(BinTreeNode *t, ElemType key);bool Equal(BinTree *t1, BinTree *t2); bool Equal(BinTreeNode *t1, BinTreeNode *t2); void Copy(BinTree *t, BinTree *t1); void Copy(BinTreeNode *t, BinTreeNode *&t1); void ClearBinTree(BinTree *t); void ClearBinTree(BinTreeNode *&t);
上面声明的方法有:(1)初始化一个二叉树.(2)创建出二叉树.(3)求二叉树的结点个数.(4)求二叉树
的高度.(5)在一个二叉树中,查找出key值的结点,并返回其地址.(6)在二叉树中,求出该结点的左子树.(7)
在二叉树中,求出该结点的右子树.(8)在一个二叉树中,查找key值的结点的父结点,并返回地址.(9)比较两
个二叉树是否相等.(10)根据一个二叉树去复制出另一个二叉树.(11)清空一个二叉树.
将声明的方法进行实现有:
void InitBinTree(BinTree *t) { t->root = NULL; } void CreateBinTree(BinTree *t) { CreateBinTree(t->root); } void CreateBinTree(BinTreeNode *&t) { ElemType item; cin>>item; if(item == '#') t = NULL; else { t = (BinTreeNode*)malloc(sizeof(BinTreeNode)); assert(t != NULL); t->data = item; CreateBinTree(t->leftChild); CreateBinTree(t->rightChild); } } int Size(BinTree *t) { return Size(t->root); } int Size(BinTreeNode *t) { if(t == NULL) return 0; else return Size(t->leftChild) + Size(t->rightChild) + 1; } int Height(BinTree *t) { return Height(t->root); } int Height(BinTreeNode *t) { if(t == NULL) return 0; else { int left_height = Height(t->leftChild); int right_height = Height(t->rightChild); return (left_height > right_height ? left_height : right_height) + 1; } } BinTreeNode* Find(BinTree *t, ElemType key) { return Find(t->root, key); } BinTreeNode* Find(BinTreeNode *t, ElemType key) { if(t == NULL) return NULL; if(t->data == key) return t; BinTreeNode *r = Find(t->leftChild, key); if(r != NULL) return r; return Find(t->rightChild, key); } BinTreeNode* LeftChild(BinTreeNode *t) { if(t == NULL) return NULL; return t->leftChild; } BinTreeNode* RightChild(BinTreeNode *t) { if(t == NULL) return NULL; return t->rightChild; } BinTreeNode* Parent(BinTree *t, ElemType key) { return Parent(t->root, key); } BinTreeNode* Parent(BinTreeNode *t, ElemType key) { if(t==NULL || t->data==key) return NULL; BinTreeNode *p = Find(t, key); if(p == NULL) return NULL; if(t->leftChild==p || t->rightChild==p) return t; BinTreeNode *r = Parent(t->leftChild, key); if(r != NULL) return r; return Parent(t->rightChild, key); } bool Equal(BinTree *t1, BinTree *t2) { return Equal(t1->root, t2->root); } bool Equal(BinTreeNode *t1, BinTreeNode *t2) { if(t1==NULL && t2==NULL) return true; if(t1!=NULL && t2!=NULL && t1->data==t2->data && Equal(t1->leftChild,t2->leftChild) && Equal(t1->rightChild, t2->rightChild)) return true; else return false; } void Copy(BinTree *t, BinTree *t1) { Copy(t->root, t1->root); } void Copy(BinTreeNode *t, BinTreeNode *&t1) { if(t == NULL) t1 = NULL; else { t1 = (BinTreeNode*)malloc(sizeof(BinTreeNode)); assert(t1 != NULL); t1->data = t->data; Copy(t->leftChild, t1->leftChild); Copy(t->rightChild, t1->rightChild); } } void ClearBinTree(BinTree *t) { ClearBinTree(t->root); } void ClearBinTree(BinTreeNode *&t) { if(t != NULL) { ClearBinTree(t->leftChild); ClearBinTree(t->rightChild); free(t); t = NULL; } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:prufer序列笔记
下一篇:萌新的第一篇博客
- 数据结构—链表 2020-05-29
- 图 2020-05-02
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 数据结构之顺序表的实现 2020-04-06
- 数据结构-线性表 2020-03-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash