- 浏览: 508869 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
jkxydp:
算法运行的结果根本就不对。
BM算法. -
soarwindzhang:
感谢博主的分享,我今天看了您的UFSET非递归的路径压缩时感觉 ...
并查集 -
zhangning290:
楼主好像只考虑了坏字符规则,。没有考虑好后缀
BM算法. -
lsm0622:
文字描述有错误 误导新学者
求有向图的强连通分量(scc):Tarjan算法 -
knightchen:
博主,你太强了!这篇文章对我学习C++多线程很有帮助!谢谢
并发学习之一_windows下ZThread在CodeBlocks上的安装与配置
1,这段时间看书有点多了,以前熟悉的东西反而淡忘了.
是总结下基础的时候了.
2,实例代码:
是总结下基础的时候了.
2,实例代码:
#include <iostream> #include <stack> #include <queue> #include <stdexcept> using namespace std; template <class T> struct BSTNode { BSTNode(); BSTNode(const T& val,BSTNode<T>* l=NULL,BSTNode<T>* r=NULL); //成员函数只是两个构造函数 T key; BSTNode<T>* left; BSTNode<T>* right; }; template <class T> BSTNode<T>::BSTNode(const T& val,BSTNode<T>* l,BSTNode<T>* r) :key(val),left(l),right(r) {} template <class T> BSTNode<T>::BSTNode():left(NULL),right(NULL) {} template <class Type> class BSTree { public: BSTree(); ~BSTree() { destroy(root); } bool isempty() { return root==NULL; } void visit(BSTNode<Type>* p); void insert(Type p); //在二叉树中插入一个节点 int height() //返回高度 { return height(root); } int nodecount() { return nodecount(root); } int leafcount() { return leafcount(root); } void inorder() { inorder(root); } void preorder() { preorder(root); } void postorder() { postorder(root); } void levelorder() { levelorder(root); } BSTNode<Type>* copytree(BSTNode<Type>* p); BSTree& operator=(const BSTree& tr); private: int height(BSTNode<Type>* p); int nodecount(BSTNode<Type>* p); int leafcount(BSTNode<Type>* p); void destroy(BSTNode<Type>* p); void preorder(BSTNode<Type>* p); void inorder(BSTNode<Type>* p); void postorder(BSTNode<Type>* p); void levelorder(BSTNode<Type>* p); private: BSTNode<Type> * root; }; template <class Type> BSTree<Type>::BSTree():root(NULL) {} //初始化NULL非常的重要,便于以后对每个节点判断是否为0 template <class Type> void BSTree<Type>::insert(Type p) { if(root==NULL) root=new BSTNode<Type>(p); //注意,节点的每一个指针都保证是用new动态分配资源 else { BSTNode<Type>* pre; BSTNode<Type>* tmp=root; while(tmp!=NULL) { pre=tmp; if(tmp->key==p) { return;//假设只能插入不同的节点 } else if(p<tmp->key) { tmp=tmp->left; } else { tmp=tmp->right; } } if(p<pre->key) pre->left=new BSTNode<Type>(p); else if(p>pre->key) pre->right=new BSTNode<Type>(p); } } template <class Type> int BSTree<Type>::height(BSTNode<Type>* p) { if(p==NULL) return 0; else return 1+( height(p->left)>height(p->right)? height(p->left):height(p->right) ); } template <class Type> int BSTree<Type>::nodecount(BSTNode<Type>* p) { if(p==NULL) return 0; else return 1+nodecount(p->left)+nodecount(p->right); } template <class Type> int BSTree<Type>::leafcount(BSTNode<Type>* p) //就编了这么一个出来 { if(p==NULL) return 0; else if(p->left==NULL&&p->right==NULL) return 1; else return leafcount(p->left)+leafcount(p->right); } template <class Type> void BSTree<Type>::destroy(BSTNode<Type>* p) { if(p!=NULL) { destroy(p->left); destroy(p->right); delete p; p=NULL; } } template <class Type> void BSTree<Type>::visit(BSTNode<Type>* p) { cout<<p->key<<" "; } template <class Type> void BSTree<Type>::inorder(BSTNode<Type>* p) { if(p!=NULL) { inorder(p->left); visit(p); inorder(p->right); } } template <class Type> void BSTree<Type>::preorder(BSTNode<Type>* p) { if(p!=NULL) { visit(p); preorder(p->left); preorder(p->right); } } template <class Type> void BSTree<Type>::postorder(BSTNode<Type>* p) { if(p!=NULL) { postorder(p->left); postorder(p->right); visit(p); } } template <class Type> void BSTree<Type>::levelorder(BSTNode<Type>* p) { if(p==NULL) return; queue< BSTNode<Type>* > que; que.push(p); BSTNode<Type>* tmp; while(!que.empty()) { tmp=que.front(); visit(tmp); que.pop(); if(tmp->left!=NULL) que.push(tmp->left); if(tmp->right!=NULL) que.push(tmp->right); } } template <class Type> BSTNode<Type>* BSTree<Type>::copytree(BSTNode<Type>* p) { if(p==NULL) return NULL; BSTNode<Type>* l=copytree(p->left); BSTNode<Type>* r=copytree(p->right); BSTNode<Type>* tree=new BSTNode<Type>(p->key,l,r); return tree; } template <class Type> BSTree<Type>& BSTree<Type>::operator=(const BSTree& tr) { if(this!=&tr) { destroy(); //释放当前的 copytree(tr.root); return *this; } } int main() { BSTree<char> bstchar; cout<<bstchar.isempty()<<endl; cout<<"叶子个数:"<<bstchar.leafcount()<<endl; BSTree<int> bstlist; for(int i=0;i!=15;i++) bstlist.insert(i); //实际上是一个但链表, cout<<"bstlist的高度:"<<bstlist.height()<<endl; cout<<"叶子个数:"<<bstlist.leafcount()<<endl; int val[]={5,3,7,1,4,6,8,9}; BSTree<int> bstarray; for(int i=0;i<sizeof(val)/sizeof(val[0]);i++) bstarray.insert(val[i]); //实际上是一个但链表, cout<<"bstarray的高度:"<<bstarray.height()<<endl; cout<<"递归中序遍历的结果:"; bstarray.inorder(); cout<<endl; cout<<"递归先序遍历的结果:"; bstarray.preorder(); cout<<endl; cout<<"递归后序遍历的结果:"; bstarray.postorder(); cout<<endl; cout<<"水平遍历的结果:"; bstarray.levelorder(); cout<<endl; cout<<"节点个数:"<<bstarray.nodecount()<<endl; cout<<"叶子个数:"<<bstarray.leafcount()<<endl; return 0; }
发表评论
-
称球问题
2010-12-16 14:13 1263[节选]http://mindhacks.cn/2008/06 ... -
平均要取到第几个随机数才会让序列第一次下降
2010-12-15 12:05 1284[转载]http://www.matrix67.com/blo ... -
输出一个数列的逆序数
2010-12-10 20:39 26771,这个问题算法导论讲归并排序时,提到过。 找到一个实现代码, ... -
给出前序和中序序列,输出后序序列
2010-12-10 11:46 15121,给出一个实现代码: #include <stdi ... -
输入是一个n*m的矩阵,要求找到其中最大的全0字矩阵
2010-11-25 12:16 15201,分析: 这个题其实就是最大子矩阵,只不过把0的权设为1,其 ... -
一些常见的海量数据处理题目
2010-11-25 11:23 1592很长时间没有更新blog了,先唠叨两句. 这段时间发生了几件不 ... -
不限数目的1、5、10、20、50面额的纸币,有多少种方法凑出100元
2010-09-21 17:22 20091,有不限数目的1、5、10、20、50面额的纸币,有多少种方 ... -
输出1到最大的N位数
2010-09-01 14:23 13231,题意: 输入数字n,按顺序输出从1最大的n位10进制数。比 ... -
找出数组中两个只出现一次的数字
2010-08-26 13:13 18451,题意: 一个整型数组里除了两个数字之外,其他的数字都出现了 ... -
字符串的逆序
2010-08-26 11:23 8211,老题目了,给个自己的版本. #include < ... -
寻找丑数
2010-08-26 10:57 31121,题意: 把只包含质因子2、3和5的数称作丑数(Ugly N ... -
寻找连续序列,使其和等于n
2010-08-26 10:15 11741,分析: 首尾两个游标. 如果当前sum < n, 尾 ... -
n个筛子的和出项的次数
2010-08-25 15:47 8361, 题目:把n个骰子扔在地上,所有骰子朝上一面的点数之和为S ... -
从文件中随即提取一个字符串
2010-05-12 12:54 763算法思路: 读入第一个:概率1保留。 读入第二个:1/2保留上 ... -
编写一些代码,确定一个变量是有符号数还是无符号数。
2010-05-12 12:53 9391,参数是一个值: #define ISUNSIGNED(va ... -
寻找移位有序数组的转折点
2010-05-09 00:22 14331,题意: 原来一个有序数组,分成前后两部分并将两部分交换得到 ... -
递归返回最大值
2010-05-06 19:20 7971,实例代码: #include<iostream& ... -
设定哨兵,返回最大值
2010-05-06 19:16 10221,精炼的代码总是那么迷人. 实例代码: #include ... -
最长平台
2010-05-06 19:01 9811,已知一个已经从小到大排序的数组,这个数组中的一个平台(Pl ... -
返回'+','-'表达式的计算结果
2010-05-04 17:07 7371,实例代码: #include <iostream ...
相关推荐
二叉树的基本操作源代码 二叉树是一种重要的数据结构,在计算机科学中有广泛的应用,本文将对二叉树的基本操作进行详细的介绍和分析。 一、实验目的 本实验的目的是为了熟悉二叉树的结构和基本操作,掌握对二叉树...
运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的...
南邮数据结构实验使用C++描述,二叉树的基本操作
在本实验报告中,我们探讨了二叉树的基本操作,主要涉及了二叉树的构建以及遍历。二叉树是一种特殊的数据结构,每个节点最多有两个子节点,通常分为左子节点和右子节点。本实验的目标是使用二叉链表作为存储结构,...
二叉树基本操作实现 二叉树是一种基本的数据结构,它广泛应用于计算机科学和软件工程中。在本实验中,我们将学习二叉树的基本操作,包括二叉树的建立、遍历、结点数统计、深度计算和叶子结点个数统计。 一、实验...
在这个《数据结构课程设计》项目中,我们专注于二叉树的基本操作,通过两个源文件(file1.cpp 和 file2.cpp)以及一个头文件(head.h)实现了一系列的二叉树操作。以下是这些操作的详细说明: 1. **创建二叉树**:...
下面我们将详细探讨平衡二叉树的基本操作。 1. 插入操作: 在平衡二叉树中插入一个新节点,首先需要像普通二叉搜索树那样进行操作,找到合适的位置插入。如果插入导致某子树高度失衡,需要通过旋转操作来重新平衡...
设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1. 按先序次序建立一个二叉树 ,用#表示某结点的左右子树是否为空,用于表示该结点是否...
以上就是关于二叉树基本操作的Java实现。理解这些操作对于理解和编写涉及数据结构的算法至关重要,因为二叉树在搜索、排序和许多其他应用中都有广泛的应用。通过实际的代码练习,你可以更好地掌握这些概念并提升编程...
二叉树的先序遍历,判断二叉树是否为空,深度的计算,结点多少的计算
### 二叉树基本操作知识点解析 #### 一、实验目的 在本实验中,学习者将通过实际编程练习来加深对二叉树这一数据结构的理解,并熟练掌握其基本操作。具体目标包括: 1. **熟悉二叉树结点的结构和对二叉树的基本...
建立一棵用二叉链表方式存储的二叉树(以先序来建立),并实现下列操作: 先序遍历二叉树; 2.中序遍历二叉树;3.后序遍历二叉树。 算法思想: 算法中主要用到的函数如下: ①void main() //主函数 ②void ...
递归二叉树的基本操作,递归创建,递归先序遍历、中序遍历、后序遍历,求树的高度,求叶子结点的个数,交换树的左右孩子
数据结构课程设计-二叉树的基本操作 本资源摘要信息是关于数据结构课程设计的,主题是二叉树的基本操作。该设计报告的主要内容包括创建二叉树、以先序、中序、后序遍历二叉树、查找子节点元素等操作。 一、 创建...
目的:1、掌握二叉链表上实现二叉树基本操作。 2、学会设计基于遍历的求解二叉树应用问题的递归算法。 3、理解哈夫曼树的构造算法,学习设计哈夫曼编码和译码系统 要求:能成功演示二叉树的有关算法,运算完毕后能...
以下是对C++实现的二叉树基本操作的深入分析。 ### 二叉树节点定义 在代码中,二叉树节点`BiNode`被定义为一个结构体,包含三个成员:`data`存储节点的数据,`lchild`指向左子节点,`rchild`指向右子节点。这个...
本节我们将深入探讨二叉树的基本操作,包括递归与非递归的先序、中序、后序遍历,以及计算叶子数目和树的高度。 首先,我们来看**先序遍历**。先序遍历的顺序是:根节点 -> 左子树 -> 右子树。递归实现的方法是,...
在本实验中,我们将深入探讨数据结构中的一个重要概念——二叉树,并实现其基本操作。二叉树是一种非线性的数据结构,它由一个有限集合的节点构成,每个节点最多有两个子节点,通常称为左子节点和右子节点。这个实验...