#include <iostream>
#include <stack>
using namespace std;
struct Bintree {
Bintree *left;
Bintree *right;
Bintree *parent;
int data;
Bintree():left(NULL),right(NULL),parent(NULL),data(0){}
};
int mycount = 3;
int i = 0;
Bintree *create_bintree()
{
p = new Bintree();
p->data = ++i;
if (--mycount >= 0) {
p->left = create_bintree(p->left);
p->right = create_bintree(p->right);
}
return p;
}
Bintree *create_bintree1(int depth)
{
p = new Bintree();
p->data = ++i;
if (depth) {
p->left = create_bintree1(p->left, depth-1);
p->right = create_bintree1(p->right, depth-1);
}
return p;
}
Bintree *create_bintree2(int parent, int depth)
{
p = new Bintree();
p->data = parent;
if (depth) {
p->left = create_bintree2(p->left, 2*parent, depth-1);
p->right = create_bintree2(p->right, 2*parent+1, depth-1);
p->left->parent = p->right->parent = p;
}
return p;
}
void ldr(Bintree *p) //递归
{
if (!p) return;
ldr(p->left);
cout << p->data << " ";
ldr(p->right);
}
void nonrecLdr(Bintree *p) //基于栈的非递归
{
if (!p) return;
stack<Bintree *> s;
while(1) {
while (p) {
s.push(p);
p = p->left;
}
if (s.empty()) {
cout << endl;
return;
}
p = s.top();
s.pop();
cout << p->data << " ";
p = p->right;
}
}
void nonrecNonstackLdr(Bintree *p) //用了父结点指针的无额外空间消耗的非递归
{
if (!p) return;
while (p) {
while (p->left) {
p = p->left;
}
cout << p->data << " ";
while (p) {
if (p->right) {
p = p->right;
break;
} else {
while (p->parent && p->parent->right == p) p = p->parent;
p = p->parent;
if (p) cout << p->data << " ";
}
}
}
cout << endl;
}
int main()
{
Bintree *root;
root = create_bintree2(root, 1, 2);
ldr(root);
cout << endl;
nonrecLdr(root);
nonrecNonstackLdr(root);
return 0;
}
分享到:
相关推荐
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
小小学习,C语言数据结构,中序遍历二叉树非递归算法
(1)输入字符序列,建立二叉链表 (2)中序遍历二叉树:递归 (3)中序遍历二叉树:非递归 (3)二叉树高度
//二叉树的二叉链表存储表示 typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; //左右孩子指针 } BiTNode, *BiTree; typedef struct { BiTree *base; BiTree *top; int stacksize; //当前...
C语言实现二叉树的中序遍历(递归)。大家下载看看哦!有用的!
二叉树的非递归中序遍历 C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码C代码
中序遍历递归算法在VC6.0环境下运行成功!
利用栈的基本操作实现二叉树的中序遍历非递归算法。
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
二叉树中序遍历的非递归算法实现[借鉴].pdf
2)对这棵二叉树进行先序遍历(采用递归算法实现)与中序遍历(采用非递归算法实现),分别输出结点的遍历序列; 2)求二叉树的深度(选做)。 这是本人所做的作业,虽然分有点多,但还是有所值的!
用递归先序算法建立二叉树。要求通过键盘输入二叉树的先序遍历顺序从而建立一棵二叉树。利用栈实现一棵二叉树的中序非递归遍历。要求显示遍历次序。
使用C++模板、类的技术实现了二叉树的中序遍历,在BC3.1已经测试成功
二叉树先序、中序、后序三种遍历的非递归算法
C语言实现二叉树的前序、中序、后续遍历(递归法),大家可以看看哈。。。
数据结构中关于二叉树的遍历,非递归算法数上未给出
数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
这是数据结构中二叉树的后序遍历的非递归算法的源代码。
二叉树的基本操作,包括前序、中序、后序遍历的递归和非递归算法,不得不下的资源