• 数据结构的二叉链表中序遍历// Tree.cpp : Defines the entry point for the console application. //---二叉链表存储表示--- #include "stdafx.h" #include #include #include using namespace std; #define ...
数据结构的二叉链表中序遍历// Tree.cpp : Defines the entry point for the console application.
//---二叉链表存储表示---

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

#define STACK_INI_SIZE 100
#define STACKINCREMENT 10

typedef char TElemType;
typedef int Status;
typedef char SElemType;//数据类型

typedef struct BiTreeNode{
SElemType data;
struct BiTreeNode *lchild, *rchild;
}BiTreeNode,*BiTree;

typedef struct{
SElemType *base;
SElemType *top;
int stacksize;  //当前已分配空间
}SqStack;

bool InitStack(SqStack &s){
s.base = (SElemType *)malloc(sizeof(SElemType));
if (!s.base)
exit(OVERFLOW);
s.top = s.base;
s.stacksize = STACK_INI_SIZE;
return true;
}
bool getTop(SqStack &s, SElemType e){
if (s.top == s.base)//若栈不空，则用e 返回S的栈顶元素
return false;
e = *(s.top - 1);
return true;
}

bool Push(SqStack &S, SElemType e){
if (S.top - S.base >= S.stacksize){
S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
if (!S.base)
return false;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top = e;
S.top++;
return true;
}
bool Pop(SqStack &S, SElemType &e){
if (S.top == S.base)
return true;
else
return false;
}

bool createTree(BiTree &T){
char ch;
cin >> ch;
if (ch == '0')
T = NULL;
else{
if (!(T = (BiTreeNode *)malloc(sizeof(BiTreeNode))))
exit(OVERFLOW);
T->data = ch;
createTree(T->lchild);
createTree(T->rchild);
}
cout<<"to be Inorder"<<endl;
return true;
}
bool InorderTraverse(BiTree &T){
//中序遍历二叉树T的非递归算法
SqStack s;
InitStack(s);
BiTree p;
p = T;
while (p || s.top != s.base){
if (p){
Push(s, p->data);
p = p->lchild;
}
else{
Pop(s, p->data);
cout<<p->data<<endl;
p = p->rchild;
}
}
return true;
}

void main(){
cout << "enter the data";
BiTree t;
createTree(t);
cout << "here:" << endl;
InorderTraverse(t);
}

展开全文
• 设二叉树采用二叉链表存储，设计一个算法，利用二叉树的中序遍历，求中序 遍历序列的第 k 个结点。 #include<stdio.h> #define MAXSIZE 100 typedef char TElemType; typedef struct BiTNode{ TElemType data...
设二叉树采用二叉链表存储，设计一个算法，利用二叉树的中序遍历，求中序
遍历序列的第 k 个结点。
#include<stdio.h>
#define MAXSIZE 100
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode* lchild,*rchild;
}BiTNode,*BiTree;

//中序遍历程序
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild );//先访问左节点
printf("%c",T->data);//访问中间节点
InOrderTraverse(T->rchild ); //最后访问右节点
}
}

//按照线序遍历的顺序创建树
void CreateBiTree(BiTree&T){
char ch;
scanf("%c",&ch);
if(ch=='#')//用#表示子树为空
T=NULL;
else{
T=new BiTNode;//动态创建子树
T->data=ch;//子树指向的数据区
CreateBiTree(T->lchild);//创建左子树
CreateBiTree(T->rchild);//创建右子树
}
}

//获取中序遍历的第k个结点
int i = 0;//初值i
void getNode(BiTree T, int k) {
if (T==NULL)//子树T为空的话，返回上一级
return ;

getNode(T->lchild,k);//访问左子树

i++;
if (i == k) {// 寻找到第k个结点之后，输出该节点
printf("%c\n",T->data);
}

getNode(T->rchild,k);//访问右子树
}

int main(){
BiTree T;
printf("请输入二叉树的元素：\n");
CreateBiTree(T);
printf("中序遍历序列为：\n");
InOrderTraverse(T);
int k;
printf("\n输入k:");
scanf("%d",&k);
printf("中序遍历序列的第%d个结点为：",k);
getNode(T, k);
return 0;
}



展开全文
• 层序遍历二叉链表 （25 分） 设计程序，按先序创建二叉树的二叉链表；然后层序遍历二叉树。 输入格式: 按先序输入一棵二叉树。二叉树中每个结点的键值用字符表示，字符之间不含空格。注意空树信息也要提供，以#字符...
层序遍历二叉链表 （25 分）
设计程序，按先序创建二叉树的二叉链表；然后层序遍历二叉树。
输入格式:
按先序输入一棵二叉树。二叉树中每个结点的键值用字符表示，字符之间不含空格。注意空树信息也要提供，以#字符表示空树。
输出格式:
输出层序遍历二叉树的序列。序列中不含空格、不含#。
输入样例:
abc##d##e#f##

输出样例:
abecdf

#include<cstdio>
#include<queue>
using namespace std;
struct node{
char data;
node* left;
node* right;
};
typedef node* bt;
void build(bt p){
char c;
scanf("%c",&c);
if(c=='#') {
p->data=c;
p->left=p->right=NULL;
return ;
}
p->data=c;
p->left=p->right=NULL;
p->left=new node;
build(p->left);
p->right=new node;
build(p->right);
}
int main(){
bt p=new node;
build(p);
queue<bt> q;
q.push(p);
while(!q.empty()){
bt t=q.front();
q.pop();
printf("%c",t->data);
if(t->left->data!='#')
q.push(t->left);
if(t->right->data!='#')
q.push(t->right);
}
printf("\n");
return 0;
}



展开全文
• 先序遍历的顺序创建二叉链表中序遍历 1.算法步骤： 1）扫描数字序列，读入数字n。 2）如果n是一个 0 数字，则表明该二叉树为空树，即T=NULL;否则执行一下操作。 申请一个节点空间T 将n赋给(*T)->data ...
先序遍历的顺序创建二叉链表并中序遍历

1.算法步骤：

1）扫描数字序列，读入数字n。

2）如果n是一个 0 数字，则表明该二叉树为空树，即T=NULL;否则执行一下操作。

申请一个节点空间T
将n赋给(*T)->data
递归创建T的左子树
递归创建T的右子树
2.创建的结果图：

3.数字的输入顺序：

1 2 3 0 0 0 4 5 0 0 6 0 0

4.C语言完整程序

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct BiNode{
ElemType data;
struct BiNode *leftChild,*rightChild;
}BiNode,*BiTree;

/*Function:先序遍历的顺序创建二叉链表*/
void CreateBiTree(BiTree *T){
ElemType n;
printf("请输入元素：\n");
scanf("%d",&n);
if(n==0){
(*T)=NULL;
}else{
(*T)=(BiNode *)malloc(sizeof(BiNode));
(*T)->data=n;
CreateBiTree(&((*T)->leftChild));
CreateBiTree(&((*T)->rightChild));
}
}
/*Function:中序遍历二叉树的递归算法*/
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->leftChild);
printf("%d",T->data);
InOrderTraverse(T->rightChild);
}
}
/*主函数*/
void main(){
BiTree tree;
printf("请输入建立二叉链表的序列：\n");
CreateBiTree(&tree);
printf("二叉树中序遍历为：\n");
InOrderTraverse(tree);
}

5.程序中的指针问题：

在程序中我们会注意到：在创建结构体时定义了结构体指针*BiTree,在CreateBiTree()方法中传入的参数是BiTree *T,没错传入的参数就是二维指针，即指向指针的指针。

这是因为：在申请根结点空间时，地址可能会发生变化，而这种变化是无法判断的，单个指针就无法找到变化后的地址，所以 ，用指针的指针，找到变化后的地址。

6.执行结果：


展开全文
• 【算法步骤】 扫描字符序列，读入字符ch. ...创建二叉链表如图所示： 代码如下： #include <iostream> using namespace std; typedef struct BiNode { char date; //二叉链表的定义 struct BiNode *lchi
• 数据结构-二叉树-二叉链表-先序遍历-中序遍历-后序遍历-递归-非递归 //代码附有详细注释，完整代码在我的资源中有 定义常量 #define stackinitsize 100 #define OK 1 #define ERROR 0 #define OVERFLOW -1 给元素起...
• 将有双亲域的二叉链表进行中序遍历的递推式算法
• structfun.h //数据结构函数头文件 #include <stdio.h> #include <iostream> #include<string> using std::cout; using std::cin;...//二叉链表存储结构（二叉链表存储结构跟树的孩子兄弟表
• 中序遍历序列(1,2,3,4,5,6,7) 后序遍历序列(2,3,1,5,7,6,4) 观察遍历的方式，我们可以知道，一棵树的先序遍历的第一个元素是树的根，后序遍历的最后一个元素是树的根。 如果给出一棵树的先序遍历或者后序遍历让你...
• 二叉链表建立二叉树链式存储结构，实现前序遍历、求叶子结点的个数计算、中序遍历、后序遍历、求深度。
• 过程初始指针指向根节点。1. 若此节点不为空，此节点入栈。2. 指针指向此节点的左孩子。3. 若此节点为空，指针指向栈顶元素并输出值，栈顶元素出栈。4. 指针指向栈顶元素的右孩子，并重复1、2、3步。...//二叉树遍历
• 　二叉搜索树的左孩子比父节点的值小，右孩子比父节点的值大，通过中序遍历即可得到一个排序的队列。在遍历的过程中调整节点指针的指向就可以将它转换成一个排序的双向链表了 　此前曾分析过二叉树的中序遍历的非...
• 转载自：...#include //定义节点 typedef struct btnode { char value; struct btnode *left; struct btnode *right;...//该函数的作用是：返回在中序遍历序列数组中
• （容器法）首先看到下图的数字排序，明显就是一个中序遍历的结果，那么只需要对二叉搜索树做中序遍历，将遍历结果的每个节点保存进一个容器中，然后对容器中的每一个值，也就是二叉树的每一个节点按照规则重新链接好...
• #include <iostream>...//二叉链表 struct BinNode { int data; struct BinNode * lchild, *rchild; }; typedef struct BinNode BinNode; typedef struct BinNode * BinTree; //三叉链表 ...
• 二叉树采用二叉链表存储结构，按照先序遍历的方式创建下面这棵二叉树。然后分别用中序遍历的两种非递归算法遍历这棵二叉树。最后释放二叉树的每个结点的存储空间。提示：释放二叉树结点时要先释放左子树，然后释放右...
• #pragma once template <typename T> class node { public: T val; node *left; node *right; node() { left = nullptr; right = nullptr; }; node(T v) { val = v; left = nullptr;...
• 由二叉树的前序遍历和中序遍历能确定唯一的一棵二叉树，用C语言或者C++实现由已知某二叉树的前序遍历序列和中序遍历序列，生成一棵用二叉链表表示的二叉树，并打印出后续遍历序列的算法。（算法要求有定义，且有...
• 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉...

...