二叉树的实现
这是我复习的第三部分,二叉树的实现,这次需要的代码比较少,所以把主函数贴出来了,注释也很清晰,所以大家直接看代码吧:
//树
#ifndef BINNODE_H
#define BINNODE_H
template<class Elem>
class BinNode{
public:
virtual Elem& val() = 0;
virtual void setVal(const Elem&) = 0;
virtual void setVal( BinNode<Elem>* b) = 0;
virtual BinNode* left() const = 0;
virtual void setLeft(BinNode*) = 0;
virtual BinNode* right() const = 0;
virtual void setRight(BinNode*) = 0;
virtual bool isLeaf() = 0;
};
#endif
//建树操作
#ifndef BINNODEPTR_H
#define BINNODEPTR_H
#include "BinNode.h"
template <class Elem>
class BinNodePtr:public BinNode<Elem>{
private:
Elem it;
BinNodePtr* lc;
BinNodePtr* rc;
public:
BinNodePtr(){lc = rc = NULL;}
BinNodePtr(Elem e,BinNodePtr* l = NULL,BinNodePtr* r = NULL){
it = e; lc = l; rc = r;
}
~BinNodePtr(){}
Elem& val(){
return it;
}
void setVal(const Elem& e){
it = e;
}
void setVal( BinNode<Elem>* b){
}
inline BinNode<Elem>* left()const{return lc;}
void setLeft(BinNode<Elem>* b){lc = (BinNodePtr*)b;}
inline BinNode<Elem>* right()const{return rc;}
void setRight(BinNode<Elem>* b){rc = (BinNodePtr*)b;}
bool isLeaf(){
return (lc==NULL)&&(rc==NULL);
}
};
#endif BINNODEPTR_H
//树,这里实现了树的几种方法
//
//(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根 - 左 - 右。
//
//(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左 - 根 - 右。
//
//(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左 - 右 - 根。
#include<iostream>
using namespace std;
#include"BinNode.h"
#include"BinNodePtr.h"
template <class Elem>
//建树
// a
// / \
// b c
// / \ \
// d e f
//建立此二叉树的方法为:(abd e c f )
BinNode<Elem>* CreateBinTree(){
BinNode<Elem>* t;
char ch;
if ((ch = getchar()) == ' ')
{
//如果是空格表示空,后面没有节点了;
return NULL;
}
else
{
//输入值
t = new BinNodePtr<Elem>(ch);
//左孩子
t->setLeft(CreateBinTree<Elem>());
//右孩子
t->setRight(CreateBinTree<Elem>());
}
return t;
}
template <class Elem>
//复制该树
BinNode<Elem>* CopyBinTree(BinNode<Elem>* p){
BinNode<Elem>* t;
t= new BinNodePtr();
t->setVal(p->val());
if (t->val()==NULL)return NULL;
else
{
t->setLeft(CopyBinTree<Elem>(p->left()));
t->setRight(CopyBinTree<Elem>(p->right()));
}
return t;
}
template <class Elem>
//输出单个节点
void visit(BinNode<Elem>* subroot){
cout<<subroot->val();
}
template <class Elem>
//前序
void preorder(BinNode<Elem>* subroot){
if(subroot == NULL) return;
visit(subroot);//根
preorder(subroot->left());//左
preorder(subroot->right());//右
}
template <class Elem>
//中序
void inorder(BinNode<Elem>* subroot){
if(subroot == NULL) return;
inorder(subroot->left());//左
visit(subroot);//根
inorder(subroot->right());//右
}
//后序遍历
template <class Elem>
void backorder(BinNode<Elem>* subroot){
if (subroot == NULL) return;
backorder(subroot->left());//左
backorder(subroot->right());//右
visit(subroot);//根
}
template <class Elem>
//左右孩子互换
//我们仍然举一个例子
// a
// / \
// b c
// / \ \
// d e f
void swithOrder(BinNode<Elem>* subroot){
//如果要置换的树是空的,结束
if(subroot==NULL) return;
visit(subroot);
//声明一个空间,用来临时存放节点
BinNode<Elem>* t;
char ch=' ';
t = new BinNodePtr<Elem>(ch);
//t临时存放右边节点
// a
// / \
// b c
// / \ \
// d e f
//t = b{d e}
t=subroot->left();
//用右边的节点覆盖左边节点
// a
// / \
// c c
// \ \
// f f
//t = b{d e}
subroot->setLeft(subroot->right());
//把t付给右边节点
// a
// / \
// c b
// \ /\
// f d e
subroot->setRight(t);
//递归,最终结果为
// a
// / \
// c b
// / /\
// f e d
swithOrder(subroot->left());
swithOrder(subroot->right());
}
int main(){
cout << "请输入:abd(空格)(空格)e(空格)(空格)c(空格)f(空格)(空格)(回车)" << endl;
BinNode<char>* tree;
tree = CreateBinTree<char>();
inorder<char>(tree);
cout<<endl;
swithOrder<char>(tree);
cout<<endl;
inorder<char>(tree);
cout << endl;
backorder<char>(tree);
cout<<endl;
system("pause");
}
相关推荐
可以学习的二叉树 最简单的人工智能 c++描写
4.5.1 简单计算机模型 4.5.2 缓存未命中对运行时间的影响 4.5.3 矩阵乘法 4.6 参考及推荐读物 第二部分 数据结构 第5章 线性表——数组描述 5.1 数据对象和数据结构 5.2 线性表数据结构 5.2.1 抽象数据类型linear...
*1.2 最简单的C++程序 1.3 C++程序的构成和书写形式 1.4 C++程序的编写和实现 1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++的数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 ...
*1.2 最简单的C++程序 1.3 C++程序的构成和书写形式 1.4 C++程序的编写和实现 1.5 关于C++上机实践 习题 第2章 数据类型与表达式 2.1 C++的数据类型 2.2 常量 2.2.1 什么是常量 2.2.2 数值常量 2.2.3 ...
本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法,比较经典的C++算法。 本例实现的功能为:给定n个带权的节点,如何构造一棵n个带有给定权值的叶节点的二叉树,使其带全路径长度WPL最小。 据此构造出最...
面试题5:如何以最简单的方式让电脑蜂鸣器发出声音 3.2 编程规范 面试题6:谈谈你对编程规范的理解或认识 面试题7:函数、变量等命名都有哪些规则 面试题8:写出bool、int、float、指针变量与“零值”比较的if语句 ...
首先用C++实现单链表编程,再基于编写好的单链表类,实现堆栈类的定义和实现。 c. 链表类和堆栈类都要包含必要的成员函数(按照教材要求)。 2、 已知a[n]为整数数组,试写出实现下列运算的递归代码(C或C++...
它们绝对不是最好的也不是最快的解决方案,只是我为解决它们各自的问题所做的。 ID 问题名称 关联 困难 解决方案 语 11 盛水最多的容器 中等的 C++ 129 根到叶数求和 中等的 C 137 单号二 中等的 Python3 226 反转...
霍夫曼编码是压缩数据的最简单算法之一。 即使它非常古老和简单,它仍然被广泛使用(例如:在JPEG,MPEG等的几个阶段中)。 在这个项目中,您将实现霍夫曼编码和解码。 您可以在Wikipedia或任何其他教程中阅读。 您...
本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找...
枚举将检查其语法,而宏是简单的文本替换。 7、 const的用法,以及声明const变量与宏的区别? 答: const的用法有四种: a): const对象和const类型的对象; b): const指针 和 指向const的指针 及两者结合; c): ...
C++ 代码。 # 标题 困难 解决方案 1 二和 简单的 5 最长回文子串 中等的 6 之字形转换 中等的 7 反转整数 简单的 9 回文数 简单的 12 整数转罗马 中等的 15 3总和 中等的 16 3和最近 中等的 22 生成括号 中等的 27 ...
3.2.1 表的简单数组实现 3.2.2 简单链表 3.3 STL中的向量和表 3.3.1 迭代器 3.3.2 示例:对表使用erase 3.3.3 const_iterator 3.4 向量的实现 3.5 表的实现 3.6 栈ADT ...
9:如果以上的知识你都学精通的话,就可以开始C++的课程了,找本C++上手的书,用一个星期的时间大概了解一下C++,然后找一本VC上手的书,再花一个星期的时间学习VC的界面和用法,就可以做一些简单的应用了!...
文件操作:一个简单的解析器,可以解析Leetcode中最常用的测试用例格式。 ["aaaaaaa",ccccccc"...] 常见的binary search模板。 二叉树: print 、 create 、 array based create 、 level print 。 去做: 更好地...
在用户输入关键词后可以进行选择词网树的根部级别和底部级别,然后系统会根据用户的输入,再依托大量的算法,在数据库中生成该关键词的词网二叉树结构,最后以树状图的形式显示到网页中,使用方便简单,便于设计与...
程序员,我认为最有效的学习方式就是多多练习,所以我选择在 . 这个 repo 将填充我在纯 Go 中对 leetcode 的解决方案,不是按照问题 ID 的顺序,而是按照问题类别。 由于 Golang 不如 C++ 或 Java 方便,因此对于...
使用python刷leetcode题目,包含思路的简单描述和代码,不定时更新 note: 从42开始,改用C++语言 1. 查找字符串中最长回文 2. 查找两个已排序数组的中位数 3. 查找字符串中的最长不重复子串的长度 4. 手动实现atio...