- 浏览: 725921 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (1044)
- 数据结构 (36)
- UML与设计模式 (42)
- c++ (87)
- rust (36)
- Qt (41)
- boost模板元编程 (43)
- Linux (77)
- 汇编 (4)
- 其它 (2)
- 烹饪 (3)
- unix c / socket (73)
- 软件工程 (4)
- shell (53)
- Python (37)
- c++ primer 5th(c++11) (22)
- 数据库/MySQL (27)
- 数据存储 (4)
- lisp (7)
- git (4)
- Utility (3)
- CDN与DNS (54)
- Http (53)
- php (7)
- nginx/lua/openresty (41)
- redis (11)
- TCP/IP (16)
- 互联网 (6)
- kernel (2)
- go (34)
- 区块链 (43)
- 比特股 (13)
- 以太坊 (23)
- 比特币 (23)
- 密码学 (10)
- EOS (53)
- DAG (1)
- docker (1)
- filecoin (7)
- solidity (64)
- ipfs (8)
- 零知识证明 (1)
- openzeppelin (3)
- java (1)
- defi (7)
最新评论
binaryTree.h
binaryTree.cpp
#ifndef LINKEDBINARYTREE_H #define LINKEDBINARYTREE_H #include<iostream> using namespace std; template<typename T> class BinTreeNode{ public: T data; BinTreeNode<T> *leftChild,*rightChild; BinTreeNode():leftChild(NULL),rightChild(NULL){} BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T>*r=NULL) :data(x),leftChild(l),rightChild(r){} }; template<typename T> class BinaryTree{ public: BinaryTree():root(NULL){} BinaryTree(T value):RefValue(value),root(NULL){} BinaryTree(BinaryTree<T>& s); ~BinaryTree(){destroy(root);} bool IsEmpty(){ return root==NULL?true:false; } BinTreeNode<T> *Parent(BinTreeNode<T>* current){ return (root==NULL||root==current)? NULL:Parent(root,current); } BinTreeNode<T> *LeftChild(BinTreeNode<T>* current){ return current!=NULL?current->leftChild:NULL; } BinTreeNode<T> *rightChild(BinTreeNode<T>* current){ return current!=NULL?current->rightChild:NULL; } int Height(){ return Height(root); } int Size(){ return Size(root); } BinTreeNode<T> *getRoot()const{ return root; } void preOrder(void(* visit)(BinTreeNode<T> *p)){ preOrder(root,visit); } void inOrder(void(* visit)(BinTreeNode<T> *p)){ inOrder(root,visit); } void postOrder(void(* visit)(BinTreeNode<T> *p)){ postOrder(root,visit); } void levelOrder(void(* visit)(BinTreeNode<T> *p)); int Insert(const T& item); BinTreeNode<T> *Find(T& item)const; protected: BinTreeNode<T> *root; T RefValue;//数据输入停止标志 void createBinTree(istream& in,BinTreeNode<T>*& subTree); bool Insert(BinTreeNode<T> *& subTree,const T& x); void destroy(BinTreeNode<T> *& subTree); bool Find(BinTreeNode<T> * subTree,const T& x)const; BinTreeNode<T> *Copy(BinTreeNode<T> *orignode); int Height(BinTreeNode<T> *subTree)const; int Size(BinTreeNode<T> *subTree)const; BinTreeNode<T> *Parent(BinTreeNode<T>* subTree, BinTreeNode<T>* current); //BinTreeNode<T> *Find(BinTreeNode<T>* subTree,const T& x)const; void Traverse(BinTreeNode<T> *subTree,ostream& out); void preOrder(BinTreeNode<T>& subTree, void (*visit)(BinTreeNode<T> *p)); void inOrder(BinTreeNode<T>& subTree, void (*visit)(BinTreeNode<T> *p)); void postOrder(BinTreeNode<T>& Tree, void (*visit)(BinTreeNode<T> *p)); friend istream& operator>>(istream& in,BinaryTree<T>& Tree); friend ostream& operator<<(ostream& out,BinaryTree<T>& Tree){ out << "preOrder" << endl; Tree.Traverse(Tree.root,out); out << endl; return out; } }; #endif // LINKEDBINARYTREE_H
binaryTree.cpp
#include"LinkedBinaryTree.h" #include<iostream> #include<stdlib.h> #include"../T3/Stack.h" using namespace std; template<typename T> void BinaryTree<T>::destroy(BinTreeNode<T> *&subTree) { if(subTree!=NULL){ destroy(subTree->leftChild);//递归删除左子树 destroy(subTree->rightChild);//递归删除右子树 delete subTree; } } /* 从subTree向下搜索current的父结点 */ template<typename T> BinTreeNode<T>* BinaryTree<T>::Parent(BinTreeNode<T> *subTree, BinTreeNode<T> *current) { if(subTree==NULL) return NULL; if(subTree->leftChild||subTree->rightChild==current) return subTree; BinTreeNode<T> *p; if((p=Parent(subTree->leftChild,current))!=NULL) return p; else return Parent(subTree->rightChild,current); } template<typename T> void BinaryTree<T>::Traverse(BinTreeNode<T> *subTree, ostream &out) { if(subTree!=NULL){ out << subTree->data << ","; Traverse(subTree->leftChild,out); Traverse(subTree->rightChild,out); } } template<typename T> void BinaryTree<T>::createBinTree(istream &in, BinTreeNode<T> *&subTree) { Stack<BinTreeNode<char>*> s; subTree = NULL; BinTreeNode<char> *p,*t; int k; char ch; in >> ch; while(ch!=RefValue){ switch(ch){ case '(': s.Push(p); k=1; break; case ')': s.Pop(t); break; case ',': k=2; break; default: p=new BinTreeNode<char>(ch); if(subTree==NULL) subTree=p; else if(k==1){ s.getTop(t); t->leftChild=p; }else{ s.getTop(t); t->rightChild=p; } } in>>ch; } } template<typename T> void BinaryTree<T>::inOrder(BinTreeNode<T>& subTree, void (*visit)(BinTreeNode<T> *p)) { if(subTree!=NULL){ InOrder(subTree->leftChild,visit); visit(subTree); InOrder(subTree->rightChild,visit); } } template<typename T> void BinaryTree<T>::preOrder(BinTreeNode<T>& subTree, void (*visit)(BinTreeNode<T> *p)) { if(subTree!=NULL){ visit(subTree); PreOrder(subTree->leftChild,visit); PreOrder(subTree->rightChild,visit); } } /* 后序遍历 */ template<typename T> void BinaryTree<T>::postOrder(BinTreeNode<T>& subTree, void (*visit)(BinTreeNode<T> *p)) { if(subTree!=NULL){ postOrder(subTree->leftChild,visit); postOrder(subTree->rightChild,visit); visit(subTree); } } template<typename T> int BinaryTree<T>::Size(BinTreeNode<T> *subTree)const { if(subTree==NULL) return 0; return 1+Size(subTree->leftChild)+Size(subTree->rightChild); } template<typename T> int BinaryTree<T>::Height(BinTreeNode<T> *subTree) const { if(subTree==NULL) return 0; int leftHeight = Height(subTree->leftChild); int rightHeight = Height(subTree->rightChild); int height = leftHeight>rightHeight?leftHeight:rightHeight; height = height+1; return height; } template<typename T> BinTreeNode<T> *BinaryTree<T>::Copy(BinTreeNode<T> *orignode) { if(orignode==NULL) return NULL; BinTreeNode<T> *temp = new BinTreeNode<T>; temp->data = orignode->data; temp->leftChild = Copy(orignode->leftChild); temp->rightChild = Copy(orignode->rightChild); return temp; } template<typename T> BinaryTree<T>::BinaryTree(BinaryTree<T> &s) { root = Copy(s.root); } //template<typename T> //void BinaryTree<T>::CreateBinTree(ifstream& in,BinTreeNode<T>*& subTree) //{ // T item; // if(!in.eof()){ // in>>item; // if(item!=RefValue){ // subTree = new BinTreeNode<T>(item); // assert(subTree!=NULL); // CreateBinTree(in,subTree->leftChild); // CreateBinTree(in,subTree->rightChild); // }else{ // subTree=NULL; // } // } //} template<typename T> void PrintBTree(BinTreeNode<T> *BT) { if(BT!=NULL){ cout << BT->data; if(BT->leftChild!=NULL||BT->rightChild!=NULL){ cout << '('; PrintBTree(BT->leftChild); cout << ','; if(BT->rightChild!=NULL) PrintBTree(BT->rightChild); cout << ')'; } } }
发表评论
-
时间复杂度推导
2012-06-05 22:57 9191.用常数1取代运行时间中的所有加法常数 2.在修改后的运行次 ... -
数据结构概论2
2012-06-04 22:19 771数据元素:组成数据的,有一定意义的基本单位,在计算机中通常作为 ... -
排序概念
2011-06-24 14:51 760数据表:待排序数据元素的有很集合 排序码:通常数据元素有多个 ... -
图的基本概念
2011-06-20 16:18 728完全图:n个顶点,n*(n-1)/2个边的无向图,就是无向完全 ... -
红黑树
2011-06-16 14:29 483红黑树: 1.根结点和所有的叶结点都是黑色 2.从根结点到叶结 ... -
链表反转
2011-06-12 18:03 1069template<typename T> v ... -
散列表(哈希表)
2011-06-09 09:55 1028散列表(hash table):是表示集合和字典的另一种有效方 ... -
跳 表
2011-06-08 11:12 774#ifndef SKIPLIST_H #define S ... -
字 典
2011-06-08 10:06 892字典:以集合为基础,并支持支持Member,Insert和Re ... -
LinkedSet
2011-06-07 13:08 894改了很久的bug #ifndef LINKEDSET_H ... -
bitset
2011-06-06 12:27 853bitSet.h #ifndef BITSET_H #d ... -
Huffman树
2011-06-02 11:06 863Huffman树,又称最优二叉树,是一类加权路径长度最短的二叉 ... -
堆
2011-06-02 09:19 923在优先级队列的各种实现中,堆是最高效的一种数据结构 关键码: ... -
森 林
2011-06-01 11:09 562森林与二叉树互转,主要是子结点转左子树,兄弟结点转右子树 深 ... -
二叉树基本概念
2011-05-30 10:05 815一棵二叉树的结点的一个有限集合:该集合或者为空,或者是由一个根 ... -
树基本概念
2011-05-30 09:28 865结点(node):包含数据项及指向其他结点的分支。 结点的度( ... -
广义表
2011-05-27 10:57 899广义表的定义是递归的,因为在表的描述中又用到了表,允许表中有表 ... -
矩阵相关
2011-05-26 10:22 892矩阵:是一个具有m行n列的二维数组。 上三角矩阵:只存储对角 ... -
优先级队列
2011-05-21 11:24 576PQueue.h #ifndef PQUEUE_H #d ... -
链式队列
2011-05-20 12:05 803LinkedQueue.h #ifndef LINKEDQ ...
相关推荐
02二叉树链式结构实现_BiTreeLink.c
二叉树的链式存储实现代码
实现二叉树抽象数据类型的基本操作,有顺序和链式结构两种。
此代码主要是介绍了二叉树的链式存储结构的前序遍历,中序遍历,后序遍历三种方式
采用链式结构存放二叉树,实现二叉树的创建,实现二叉树的遍历(前序,后序,中序层次遍历),分别求二叉树的叶子结点和结点的数目,二叉树的查找,二叉树的深度。 。
1.对给定二叉树用链式链式存储结构;利用队列与栈对二叉树进行运算。 2.按层次输出所有结点。 3.输出所有叶子结点。 4.将所有左右子树值交换。
要求选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作。有个亮点是利用字符在dos界面显示二叉树的结构形态。 里面包含了完整的源程序和实验报告文档。 实验报告包含了完整的步骤包括: 一.抽象...
采用链式结构存放二叉树,实现二叉数的创建,实现二叉数的遍历(前序,后序,中序层次遍历),分别求二叉树的叶子结点和结点的数目,二叉树的查找,二叉树的深度。
实现二叉树的基本操作:建立、遍历、计算深度、结点数、叶子数等。 输入C,先序创建二叉树,#表示空节点; 输入H:计算二叉树的高度; 输入L:计算二叉树的叶子个数; 输入N:计算二叉树节点总个数; 输入1:先序...
本例程详细讲解了链式二叉树的实现方法和实现的函数,对于学习数据结构中的链式二叉树具有很好的学习作用,可以充分理解二叉树的结构和特性
利用DNA分子和连接酶的生物特性,提出DNA计算机中二叉树的链式存储结构的设计方法,并给出二叉树链式存储结构的形式描述。在连接酶的作用下,各节点之间产生杂交和连接反应形成DNA双链,其中用到的生物技术在实验室...
4.掌握计算二叉树的结点个数、二叉树的深度、二叉树的叶子结点和二叉树复制算法。 二、实验内容 1、构造基于先序遍历的二叉链表。 要求:按先序遍历规则,从键盘连续输入二叉树的先序序列,若无孩子结点,则用#代替...
内容概要:用c代码完成链式二叉树、有序二叉树、线索二叉树的的常见操作。其中包括构建、销毁、前序/后序/中序遍历、高度、密度、添加、删除、查询等操作 适合人群:具备一定编程基础,尤其是c语言基础,并很好地...
这是我用C++实现的二叉树,感觉思路还是不错的!!
编写程序,实现求采用链式存储结构存储的二叉树的树高
本资源包含了数据结构中链式二叉树的实现算法的完整程序(可以直接运行)以及实验报告文档
实验四 二叉树基本操作的实现 二叉树概念及其存储结构 二叉链储存结构的二叉树基本操作 举例说明什么样的二叉树采用顺序存储,什么样的二叉树采用二叉链存储
学习数据结构中 的图 。 实现其存储和遍历。
主要实现链式二叉树先序,中序,后序遍历
// 二叉树实现 // 可以在节点中插入新的节点, // 四种遍历方式, 1)前序 2) 中序 3)后序 4)层次 //封装成类 可自己添加功能 // 作者: 一路向南 // 2013.5.25 //////////////////////////...