数据结构详解 |
您所在的位置：网站首页 › 树的结构分解图片高清图 › 数据结构详解 |
数据结构详解
|
树
文章目录
树树的定义树的基本术语树的存储结构双亲表示法孩子表示法
二叉树二叉树的性质二叉树的实现满二叉树完全二叉树二叉排序树平衡二叉树
欢迎支持
树的定义
树是由一个集合以及在该集合上定义的一种关系构成的，集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构，在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点。 数据结构中有很多树的结构，其中包括二叉树、二叉搜索树、2-3树、红黑树等等，本文着重介绍二叉树。 树的基本术语 节点的度：一个节点含有的子树的个数称为该节点的度；叶节点或终端节点：度为0的节点称为叶节点；非终端节点或分支节点：度不为0的节点；双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；兄弟节点：具有相同父节点的节点互称为兄弟节点；树的度：一棵树中，最大的节点的度称为树的度；节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；树的高度或深度：树中节点的最大层次；堂兄弟节点：双亲在同一层的节点互为堂兄弟；节点的祖先：从根到该节点所经分支上的所有节点；子孙：以某节点为根的子树中任一节点都称为该节点的子孙。森林：由m（m>=0）棵互不相交的树的集合称为森林； 树的存储结构 双亲表示法
二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构。 二叉树的定义：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。 二叉树的性质 二叉树的第 i i i层至多有 2 i − 1 2^{i-1} 2i−1 个结点；深度为 k k k 的二叉树至多有 2 k − 1 2^k-1 2k−1 个结点；对任何一棵二叉树 T T T ，如果其终端结点数为 n 0 n_0 n0 ，度为2的结点数为 n 2 n_2 n2 ，则 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1 。 二叉树的实现结构 template struct BiNode { DataType data; BiNode * lchild,*rchild; }; template class BiTree { public: BiTree(){root = Create(root);} ~BiTree(){Release(root);} void PreOrder(){PreOrder(root);} //前序遍历 void InOrder(){InOrder(root);} //中序遍历 void PostOrder(){PostOrder(root);} //后序遍历 private: BiNode * root; BiNode * Create(BiNode *bt); void Release(BiNode *bt); void PreOrder(BiNode *bt); void InOrder(BiNode *bt); void PostOrder(BiNode *bt); };建立二叉树 template BiNode *BiTree::Create(BiNode *bt) { DataType ch; cin>>ch; if(ch == '#') bt = NULL; else{ bt = new BiNode; bt->data = ch; bt->lchild = Create(bt->lchild); bt->rchild = Create(bt->rchild); } return bt; }释放二叉树 template void BiTree::Release(BiNode *bt) { if(bt != NULL){ Release(bt->lchild); Release(bt->rchild); delete bt; } }前序遍历 template void BiTree::PreOrder(BiNode *bt) { if(bt == NULL) return; else{ coutlchild); PreOrder(bt->rchild); } }中序遍历 template void BiTree::InOrder(BiNode *bt) { if(bt == NULL) return; else{ InOrder(bt->lchild); coutrchild); } }后序遍历 template void BiTree::PostOrder(BiNode *bt) { if(bt == NULL) return; else{ PostOrder(bt->lchild); PostOrder(bt->rchild); cout |
【本文地址】
今日新闻 |
推荐新闻 |