线索二叉树C++实现
2024-08-31 11:13:24
#include<iostream>
#include<stdlib.h>
#define maxsize 100
using namespace std;
typedef struct BTNode{
char val;
struct BTNode *lchild, *rchild;
int ltag, rtag;
}BTNode, *BiNode;
BTNode* stack[maxsize];
int top = -1;
/**
* 找到中序遍历的第一个起始顶点
*/
inline BTNode* First(BTNode *root){
while(root->ltag == 0)
root = root->lchild;
return root;
}
/**
* 找到中序遍历的下一个顶点，树已被中序线索化
*/
inline BTNode* InOrderNext(BTNode *root){
if(root->rtag == 0)
return First(root->rchild);
else
return root->rchild;
}
/**
* debug，用来打印线索化之后的树的信息
*/
inline void debug(){
for(int i = 0; i <= top; i++){
cout << "[debug]: BTNode->[";
cout << (void *) stack[i];
cout << "]" << endl;
cout << " [val] :" << stack[i]->val << endl;
cout << " [lchild]:";
cout << (void *) stack[i]->lchild << endl;
cout << " [rchild]:";
cout << (void *) stack[i]->rchild << endl;
cout << " [ltag] :" << stack[i]->ltag << endl
<< " [rtag] :" << stack[i]->rtag << endl;
}
}
void CreateTree(BTNode *&root);
void PreOrderThreading(BTNode *root, BTNode *&pre);
void InOrderThreading(BTNode *root, BTNode *&pre);
void PreOrderThreadingTraversal(BTNode *root);
void InOrderThreadingTraversal(BTNode *root);
void PostOrderThreading(BTNode *root, BTNode *&pre);
void PostOrderThreadingTraversal(BTNode *root);
void CreateTree(BTNode *&root){
char c;
cin >> c;
if(c != '#'){
root = (BTNode *) malloc(sizeof(struct BTNode));
if(!root){
cerr << "No More Memory!" << endl;
exit(-1);
}
root->val = c;
root->lchild = root->rchild = NULL;
root->ltag = root->rtag = 0;
CreateTree(root->lchild);
CreateTree(root->rchild);
}else{
root = NULL;
}
}
void PreOrderThreading(BTNode *root, BTNode *&pre){
if(root){
if(!root->lchild){
root->lchild = pre;
root->ltag = 1;
}
if(pre && !pre->rchild){
pre->rchild = root;
pre->rtag = 1;
}
pre = root;
if(root->ltag == 0){
PreOrderThreading(root->lchild, pre);
}
if(root->rtag == 0){
PreOrderThreading(root->rchild, pre);
}
}
}
void PreOrderThreadingTraversal(BTNode *root){
if(root){
cout << root->val << " ";
if(root->ltag == 0){
PreOrderThreadingTraversal(root->lchild);
}else{
PreOrderThreadingTraversal(root->rchild);
}
}
}
void InOrderThreading(BTNode *root, BTNode *&pre){
if(root){
stack[++top] = root;
InOrderThreading(root->lchild, pre);
if(!root->lchild){
root->lchild = pre;
root->ltag = 1;
}
if(pre && !pre->rchild){
pre->rchild = root;
pre->rtag = 1;
}
pre = root;
InOrderThreading(root->rchild, pre);
}
}
void InOrderThreadingTraversal(BTNode *root){
for(BTNode *p = First(root); p; p = InOrderNext(p))
cout << p->val << " ";
}
void PostOrderThreading(BTNode *root, BTNode *&pre){
if(root){
stack[++top] = root;
PostOrderThreading(root->lchild, pre);
PostOrderThreading(root->rchild, pre);
if(!root->lchild){
root->lchild = pre;
root->ltag = 1;
}
if(pre && !pre->rchild){
pre->rchild = root;
pre->rtag = 1;
}
pre = root;
}
}
void PostOrderThreadingTraversal(BTNode *root){
//PostOrder需要在原有的节点的类型定义上增加一个
//parent节点，否则，遍历的时候可能会没有办法
//回到上一层节点当中
}
int main(){
BTNode *root, *pre = NULL;
CreateTree(root);
//PostOrderThreading(root, pre);
//debug();
//PostOrderThreadingTraversal(root);
return 0;
}
最新文章
- 节日来了发个HTML5红包
- 查看机器上安装的jdk能支持多大内存
- Code First is a bad name，这些年我们对Code First的理解都错了 ！很震惊吧？
- C# 反射创建对象,包括创建引用外部程序集类的实例
- 网站后台的lnmp启动与重启
- jmeter随笔（3）-从csv中获取带引号的数据详情
- 一站式Hadoop&Spark云计算分布式大数据和Android&HTML5移动互联网解决方案课程（Hadoop、Spark、Android、HTML5）V2的第一门课程
- HBuilder：最快的Web开发IDE
- java中的多线程——进度1
- 数据结构——N皇后放置方法种数
- 在vim里每行增加//注释
- Android : 如何在WebView显示的页面中查找内容
- python初探-copy
- C random C ++rand函数应用
- nyoj_600:花儿朵朵（树状数组+坐标离散化）
- Oracle GoldenGate微服务架构的服务Shell脚本
- SQLServer之创建索引视图
- 不使用DataContext直接将ViewModels绑定到ItemsControl控件
- 死锁的原因及解决办法RLock递归锁
- Python 利用字典实现类似 java switch case 功能