#include <iostream>
#include <sstream>
using namespace std;
template<class T>
struct tbtnode
{
T s_t;
bool lflag;
bool rflag;
tbtnode *lchild;
tbtnode *rchild;
};
template<class T>
tbtnode<T>* createtbt(tbtnode<T>* tbt, int k, ostream& out, istream& in)
{
tbtnode<T> *p, *t;
T tmp;
out << "Input key: " << endl;
in >> tmp;
out << '\t' << tmp << endl;
if ('0' != tmp)
{
p = new tbtnode<T>;
p->s_t = tmp;
p->lchild = NULL;
p->rchild = NULL;
p->lflag = 0;
p->rflag = 0;
if (0 == k) t = p;
if (1 == k) tbt->lchild = p;
if (2 == k) tbt->rchild = p;
createtbt(p, 1, out, in);
createtbt(p, 2, out, in);
}
return (t);
}
template<class T>
void pretraverse(tbtnode<T> *root)
{
if (NULL != root)
{
cout << root->s_t << " ";
pretraverse(root->lchild);
pretraverse(root->rchild);
}
}
template<class T>
void intraverse(tbtnode<T> *root)
{
if (NULL != root)
{
intraverse(root->lchild);
cout << root->s_t << " ";
intraverse(root->rchild);
}
}
template<class T>
void postraverse(tbtnode<T> *root)
{
if (NULL != root)
{
postraverse(root->lchild);
postraverse(root->rchild);
cout << root->s_t << " ";
}
}
template<class T>
void inthread(tbtnode<T> *tbt, tbtnode<T> **h)
{
if (NULL != tbt)
{
inthread(tbt->lchild, h);
if (tbt->lchild == NULL)
{
tbt->lchild = *h;
tbt->lflag = 1;
}
if ((*h != NULL) && ((*h)->rchild == NULL))
{
(*h)->rchild = tbt;
(*h)->rflag = 1;
}
*h = tbt;
inthread(tbt->rchild, h);
}
}
template<class T>
void prethread(tbtnode<T> *tbt, tbtnode<T> **h)
{
if (NULL != tbt)
{
if (tbt->lchild == NULL)
{
tbt->lchild = *h;
tbt->lflag = 1;
}
if ((*h != NULL) && ((*h)->rchild == NULL))
{
(*h)->rchild = tbt;
(*h)->rflag = 1;
}
*h = tbt;
//*h = tbt->lchild;
if (tbt->lflag == 0)
prethread(tbt->lchild, h);
if (tbt->rflag == 0)
prethread(tbt->rchild, h);
}
}
template<class T>
void posthread(tbtnode<T> *tbt, tbtnode<T> **h)
{
if (NULL != tbt)
{
posthread(tbt->lchild, h);
posthread(tbt->rchild, h);
if (tbt->lchild == NULL)
{
tbt->lchild = *h;
tbt->lflag = 1;
}
if ((*h != NULL) && ((*h)->rchild == NULL))
{
(*h)->rchild = tbt;
(*h)->rflag = 1;
}
*h = tbt;
}
}
template<class T>
void inthtraverse(tbtnode<T> *tbt)
{
tbtnode<T> *h;
if (tbt == NULL) return;
h = tbt;
while (h->lflag == 0) h = h->lchild;
cout << h->s_t << " ";
while (h->rchild != NULL)
{
if (h->rflag == 1)
h = h->rchild;
else
{
h = h->rchild;
while ((h->lflag == 0) && (h->lchild != NULL))
h = h->lchild;
}
cout << h->s_t << " ";
}
}
template<class T>
void prethtraverse(tbtnode<T> *tbt)
{
tbtnode<T> *h;
if (tbt == NULL) return;
h = tbt;
cout << tbt->s_t << " ";
while (h->rchild != NULL)
{
if ((h->lflag == 0) && (h->lchild != NULL))
{
h = h->lchild;
}
else
{
h = h->rchild;
}
cout << h->s_t << " ";
}
}
template<class T>
void posthtraverse(tbtnode<T> *tbt)
{
tbtnode<T> *h;
if (tbt == NULL) return;
h = tbt;
}
int main()
{
typedef tbtnode<char> tbtnode_char;
tbtnode_char *root;
//istringstream ssin(string("AB0DG000CE0H00F00"));
istringstream ssin(string("ABCD00E00FG00H00IJK00L00MN00O00"));
root = createtbt(root, 0, cout, ssin);
pretraverse(root);
cout << endl;
intraverse(root);
cout << endl;
postraverse(root);
cout << endl;
cout << "通过穿线二叉树进行遍历" << endl;
tbtnode_char *h = NULL;
//inthread(root, &h);
//inthtraverse(root);
prethread(root, &h);
prethtraverse(root);
cout << endl;
return 0;
}
分享到:
相关推荐
穿线二叉树的基本功能基本上都有,构造,前序,中序,后序周游,层次周游,删除结点
二叉树实现-完美版-二叉树操作-整个实现用C++实现
平衡二叉树实现代码
二叉树 二叉树最基本的实现。建立插入删除等操作。 二叉树听会了代码还是不会敲啊。。。。
java二叉树实现 (简单实现,入门用) /**创建二叉树*/ public BinaryTree createTree(String treeStr); /**寻找结点*/ public BinaryTree findNode(BinaryTree tree ,char sign); /**找所给结点的左子树*/ ...
二叉树实现源代码 经典版c++源码 *建立二叉树算法描述: 用ch扫描采用括号表示法表示二叉树的字符串Str。分以下几种情况: 1、若ch='('则将前面刚创建的结点作为双亲结点进栈,并置k=1,表示其后创建的结点将做为这...
PHP实现二叉树图
(3)中序遍历二叉树:非递归算法(最好也能实现先序,后序非递归算法)。 (4)求二叉树的高度 。 (5)求二叉树的叶子个数。 (6)对于树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。 (8...
二叉树的java实现
二叉树操作C++实现 二叉树操作C++实现 二叉树操作C++实现 二叉树操作C++实现 二叉树操作C++实现
用二叉树实现简单计算器
资源是txt版本,整合了思路及程序。内容仅供参考,不可用于商业,否则后果自负。
用递归的方法实现: 1、创建二叉树 2、先序遍历输出 3、后序遍历输出 4、中序遍历输出 5、二叉树深度
汇编语言小程序二叉树实现汇编语言小程序二叉树实现汇编语言小程序二叉树实现汇编语言小程序二叉树实现汇编语言小程序二叉树实现汇编语言小程序二叉树实现汇编语言小程序二叉树实现汇编语言小程序二叉树实现汇编语言...
利用平衡二叉树的调平衡操作,实现学生成绩的输入,存储和读取,涉及平衡二叉树,文件等操作,实现学生成绩的基本管理
二叉树 二叉树_基于Objective-C的完全二叉树实现的优先队列
线索二叉树的一些基本功能 遍历 二叉树线索化 等等
2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问结点的操作修改为叶结点计数,统计度为0的;度为1...
本实验报告仅用于学习,严禁商业用途造成后果本人概不负责
利用二叉顺序树实现一个动态查找表,实现动态查找表的三项基本功能:查找,插入,删除操作。开始进行顺序二叉树的建立,输入元素的个数以及元素,动态创建一个二叉树,然后进行选择对二叉顺序树进行的操作,即选择,...