求代码——二叉树——要C语言的
#include
#include
#include
#define MAX 20
#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree CreateBiTree(BiTree T)
{
char ch;
scanf("%c",&ch);
if (ch=='#') T=NULL; /* #代表空指针*/
else
{
T=(BiTNode*)malloc(sizeof(BiTNode));
if(!T) exit(OVERFLOW); /*申请结点 */
T->data=ch; /*生成根结点 */
T->lchild=CreateBiTree(T->lchild); /*构造左子树 */
T->rchild=CreateBiTree(T->rchild); /*构造右子树 */
}
return T;
}
void PreOrder(BiTree T)
{
if (T) {
printf("%c",T->data); // 访问结点
PreOrder(T->lchild); // 遍历左子树
PreOrder(T->rchild);// 遍历右子树
}
}
void InOrder( BiTree T )
{/*中序遍历*/
if (T) {
InOrder(T->lchild); // 遍历左子树
printf("%c",T->data); // 访问结点
InOrder(T->rchild);// 遍历右子树
}
}
void PostOrder( BiTree T )
{/*后序遍历*/
if (T) {
PostOrder(T->lchild); // 遍历左子树
PostOrder(T->rchild);// 遍历右子树
printf("%c",T->data); // 访问结点
}
}
void LevleOrder(BiTree T)
{ /*层次遍历二叉树T,从第一层开始,每层从左到右*/
BiTree Queue[MAX],b;/*用一维数组表示队列,front和rear分别表示队首和队尾指针*/
int front,rear;
front=rear=0;
if(T) /*若树非空*/
{
Queue[rear++]=T; /*根结点入队列*/
while (front!=rear)
{ /*当队列非空*/
b=Queue[front++]; /*队首元素出队列,并访问这个结点*/
printf("%2c",b->data);
if(b->lchild!=NULL) Queue[rear++]=b->lchild; /*左子树非空,则入队列*/
if(b->rchild!=NULL) Queue[rear++]=b->rchild; /*右子树非空,则入队列*/
}
}
}/*LevelOrder*/
void main()
{
BiTree B,T;
//BiTNode T;
printf("
请读入构造二叉树的字符序列:");
B=CreateBiTree(T); /*建立一棵二叉树T*/
//B=&T;
printf("
该二叉树的先序遍历是:");
PreOrder(B); /*先序遍历二叉树*/
printf("
该二叉树的中序遍历");
InOrder( B); /*中序遍历二叉树*/
printf("
该二叉树的后序遍历");
PostOrder( B); /*后序遍历二叉树*/
printf("
该二叉树的层次遍历是:");
LevleOrder(B); /*层次遍历二叉树*/
}
先序输入 如 abc##d##e## (#表示空)
输出 cbdae
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#include "cstdlib"
#include "malloc.h"
typedef int Status;
typedef char TElemType;
#include
#include
using namespace std;
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
Status CreateBiTree(BiTree &T){//构造二叉树
TElemType ch;
scanf("%c",&ch);
if(ch=='#') T=NULL;
else{
if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}//CreateBiTree
Status Visit(char Data)
{
printf("%c",Data);
return OK;
}
Status InOrderTraval(BiTree pTree)
{
if(pTree)
{
if(InOrderTraval(pTree->lchild))
{
if(Visit(pTree->data))
{
if(InOrderTraval(pTree->rchild))
{
return OK;
}
}
return ERROR;
}
return ERROR;
}
else
{
return OK;
}
}
Status v(char a)
{
printf("%c",a);
return OK;
}
void main()
{
BiTree A,b;
printf("先序输入,空用 # 表示:
");
CreateBiTree(A);
b=A;
printf("中序输出:
");
InOrderTraval(b);
} 1
#include <stdlib.h>
#define STACK_MAX_SIZE 30
#define QUEUE_MAX_SIZE 30
#ifndef elemType
typedef char elemType;
#endif
/************************************************************************/
/* 以下是关于二叉树操作的11个简单算法 */
/************************************************************************/
struct BTreeNode{
elemType data;
struct BTreeNode *left;
struct BTreeNode *right;
};
/* 1.初始化二叉树 */
void initBTree(struct BTreeNode* *bt)
{
*bt = NULL;
return;
}
/* 2.建立二叉树(根据a所指向的二叉树广义表字符串建立) */
void createBTree(struct BTreeNode* *bt, char *a)
{
struct BTreeNode *p;
struct BTreeNode *s[STACK_MAX_SIZE];/* 定义s数组为存储根结点指针的栈使用 */
int top = -1; /* 定义top作为s栈的栈顶指针,初值为-1,表示空栈 */
int k; /* 用k作为处理结点的左子树和右子树,k = 1处理左子树,k = 2处理右子树 */
int i = 0; /* 用i扫描数组a中存储的二叉树广义表字符串,初值为0 */
*bt = NULL; /* 把树根指针置为空,即从空树开始建立二叉树 */
/* 每循环一次处理一个字符,直到扫描到字符串结束符\0为止 */
while(a[i] != '\0'){
switch(a[i]){
case ' ':
break; /* 对空格不作任何处理 */
case '(':
if(top == STACK_MAX_SIZE - 1){
printf("栈空间太小!\n");
exit(1);
}
top++;
s[top] = p;
k = 1;
break;
case ')':
if(top == -1){
printf("二叉树广义表字符串错误!\n");
exit(1);
}
top--;
break;
case ',':
k = 2;
break;
default:
p = (BTreeNode *)malloc(sizeof(struct BTreeNode));
p->data = a[i];
p->left = p->right = NULL;
if(*bt == NULL){
*bt = p;
}else{
if( k == 1){
s[top]->left = p;
}else{
s[top]->right = p;
}
}
}
i++; /* 为扫描下一个字符修改i值 */
}
return;
}
/* 3.检查二叉树是否为空,为空则返回1,否则返回0 */
int emptyBTree(struct BTreeNode *bt)
{
if(bt == NULL){
return 1;
}else{
return 0;
}
}
/* 4.求二叉树深度 */
int BTreeDepth(struct BTreeNode *bt)
{
if(bt == NULL){
return 0; /* 对于空树,返回0结束递归 */
}else{
int dep1 = BTreeDepth(bt->left); /* 计算左子树的深度 */
int dep2 = BTreeDepth(bt->right); /* 计算右子树的深度 */
if(dep1 > dep2){
return dep1 + 1;
}else{
return dep2 + 1;
}
}
}
/* 5.从二叉树中查找值为x的结点,若存在则返回元素存储位置,否则返回空值 */
elemType *findBTree(struct BTreeNode *bt, elemType x)
{
if(bt == NULL){
return NULL;
}else{
if(bt->data == x){
return &(bt->data);
}else{ /* 分别向左右子树递归查找 */
elemType *p;
if(p = findBTree(bt->left, x)){
return p;
}
if(p = findBTree(bt->right, x)){
return p;
}
return NULL;
}
}
}
/* 6.输出二叉树(前序遍历) */
void printBTree(struct BTreeNode *bt)
{
/* 树为空时结束递归,否则执行如下操作 */
if(bt != NULL){
printf("%c", bt->data); /* 输出根结点的值 */
if(bt->left != NULL || bt->right != NULL){
printf("(");
printBTree(bt->left);
if(bt->right != NULL){
printf(",");
}
printBTree(bt->right);
printf(")");
}
}
return;
}
/* 7.清除二叉树,使之变为一棵空树 */
void clearBTree(struct BTreeNode* *bt)
{
if(*bt != NULL){
clearBTree(&((*bt)->left));
clearBTree(&((*bt)->right));
free(*bt);
*bt = NULL;
}
return;
}
/* 8.前序遍历 */
void preOrder(struct BTreeNode *bt)
{
if(bt != NULL){
printf("%c ", bt->data); /* 访问根结点 */
preOrder(bt->left); /* 前序遍历左子树 */
preOrder(bt->right); /* 前序遍历右子树 */
}
return;
}
/* 9.前序遍历 */
void inOrder(struct BTreeNode *bt)
{
if(bt != NULL){
inOrder(bt->left); /* 中序遍历左子树 */
printf("%c ", bt->data); /* 访问根结点 */
inOrder(bt->right); /* 中序遍历右子树 */
}
return;
}
/* 10.后序遍历 */
void postOrder(struct BTreeNode *bt)
{
if(bt != NULL){
postOrder(bt->left); /* 后序遍历左子树 */
postOrder(bt->right); /* 后序遍历右子树 */
printf("%c ", bt->data); /* 访问根结点 */
}
return;
}
/* 11.按层遍历 */
void levelOrder(struct BTreeNode *bt)
{
struct BTreeNode *p;
struct BTreeNode *q[QUEUE_MAX_SIZE];
int front = 0, rear = 0;
/* 将树根指针进队 */
if(bt != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = bt;
}
while(front != rear){ /* 队列非空 */
front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */
p = q[front];
printf("%c ", p->data);
/* 若结点存在左孩子,则左孩子结点指针进队 */
if(p->left != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->left;
}
/* 若结点存在右孩子,则右孩子结点指针进队 */
if(p->right != NULL){
rear = (rear + 1) % QUEUE_MAX_SIZE;
q[rear] = p->right;
}
}
return;
}
/************************************************************************/
int main(int argc, char *argv[])
{
struct BTreeNode *bt; /* 指向二叉树根结点的指针 */
char *b; /* 用于存入二叉树广义表的字符串 */
elemType x, *px;
initBTree(&bt);
printf("输入二叉树广义表的字符串:\n");
/* scanf("%s", b); */
b = "a(b(c), d(e(f, g), h(, i)))";
createBTree(&bt, b);
if(bt != NULL)
printf(" %c ", bt->data);
printf("以广义表的形式输出:\n");
printBTree(bt); /* 以广义表的形式输出二叉树 */
printf("\n");
printf("前序:"); /* 前序遍历 */
preOrder(bt);
printf("\n");
printf("中序:"); /* 中序遍历 */
inOrder(bt);
printf("\n");
printf("后序:"); /* 后序遍历 */
postOrder(bt);
printf("\n");
printf("按层:"); /* 按层遍历 */
levelOrder(bt);
printf("\n");
/* 从二叉树中查找一个元素结点 */
printf("输入一个待查找的字符:\n");
scanf(" %c", &x); /* 格式串中的空格跳过空白字符 */
px = findBTree(bt, x);
if(px){
printf("查找成功:%c\n", *px);
}else{
printf("查找失败!\n");
}
printf("二叉树的深度为:");
printf("%d\n", BTreeDepth(bt));
clearBTree(&bt);
return 0;
}
【图解】数据结构代码领背-二叉树的后序遍历(递归法、非递归法)_百度...
数据结构代码详解:二叉树的后序遍历(递归法与非递归法)二叉树后序遍历方法清晰直观,我们通过递归和非递归两种方式来理解。首先,递归法的逻辑是:1. 对左子树进行后序遍历,2. 对右子树进行后序遍历,3. 访问根节点。以示例二叉树为例,其后序遍历结果为:4, 5, 2, 6, 7, 3, 1。非递归...
二叉树的前中后序及层次遍历及代码实现
首先,让我们通过一个示例树理解这些遍历方法:(参阅博客链接)前序遍历前序遍历遵循“根-左-右”的顺序,递归实现如下:递归代码:非递归代码:在非递归方法中,从根节点开始,先将其入栈,然后左子树,接着右子树,确保左子树先于右子树遍历。中序遍历中序遍历遵循“左-根-右”的顺序,中序遍历结果...
Java中关于二叉树详解
遍历方式包括前序、中序、后序遍历。测试代码输出结果分别展示遍历顺序。构建二叉树 通过测试代码展示构建过程,实现前序、中序遍历的构建。求结点个数 提供测试代码,通过递归或子问题思路实现。求叶子结点个数 通过测试代码展示求叶子结点个数的递归或子问题实现。求第k层结点个数 提供测试代码,展示求...
数据结构——二叉树
数据结构——二叉树详解二叉树是一种特殊的树形数据结构,每个节点最多有两个子节点,且子节点有明确的左右之分,其子节点的顺序不能随意调整。它在存储和访问数据时具有特定的规则。存储结构上,二叉树通常采用结构体表示,包含节点值和指向左右子节点的指针。结构图展示了一棵树的组织形式,通过先序遍...
求代码——二叉树——要C语言的
\/* 1.初始化二叉树 *\/ void initBTree(struct BTreeNode* *bt){ bt = NULL;return;} \/* 2.建立二叉树(根据a所指向的二叉树广义表字符串建立) *\/ void createBTree(struct BTreeNode* *bt, char *a){ struct BTreeNode *p;struct BTreeNode *s[STACK_MAX_SIZE];\/* 定义s数组为存储根...
知识分享:数据结构—树的基本操作!主要遍历及其代码示例
分享今日树的基本操作C语言实现,主要遍历方法及其代码示例。二叉树示意图如下:先序遍历:ABCDEGF 中序遍历:CBEGDFA 后序遍历:CGEFDBA 层次遍历:ABCDEFG 二叉树创建与遍历主函数:1. 先序创建二叉树:输入"ABC_ _DE_G_ _F_ _ _",注意无左右子树时输入空格。2. 先序遍历(递归算法)3. 中...
平衡二叉树简介与C++代码实现
这个平衡二叉树的应用源于阿里TDM召回模型,其中N个物品对应每个叶子节点。树的高度K决定了搜索的效率,而分组规则的调整使得相似度高的物品聚类在一起。搜索过程从模糊(全集)逐渐聚焦到特定物品,如从男性喜好到数码家电,再到手机类别,最后到苹果的iPhone 14 Max Pro,其时间复杂度为O(logN)。尽管...
跪求二叉树相关代码
这是我曾经编写的一个二叉树的程序,包括建立树,求各种节点,各种遍历等。希望对你有点帮助: (c++)include <iostream.h> include <stdlib.h> void Visit(int &x){ cout<<x<<'\\t';} struct Node \/\/每棵树的节点 { int element;Node *left;Node *right;Node(int x){element=x;left=...
用清华大学数据结构书上代码创建二叉树怎么创建
1、要明确的一点是只有中序是无法创建二叉树的,要结合先序,两者相联系才可以。二、根据二叉树的图,得出先序的顺序是ABDECFG,而与此同时的中序DBEAFCG,根据这个建立。三、然后就是要根据二叉树的原则编写代码。
数据结构中二叉树的顺序存储结构代码怎么编写?
(以下有一段代码,自己先看看学学吧) 数据结构C语言版 二叉树的顺序存储表示和实现 P126 编译环境:Dev-C++ 4.9.9.2 日期:2011年2月13日 *\/#include <stdio.h>typedef char TElemType;\/\/ 二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 \/\/ 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_TREE_SIZE...
捷功迪巧: #include <stdio.h> #include <stdlib.h> #define STACK_MAX_SIZE 30 #define QUEUE_MAX_SIZE 30 #ifndef elemType typedef char elemType; #endif /************************************************************************/ /* 以下是关于二叉树操作的11...
孟村回族自治县13455877478: 急求二叉树C语言代码 - ?
捷功迪巧: BinaryTree.h: /******************************************************************** created: 2006/07/04 filename: BinaryTree.h author: 李创 purpose: 演示二叉树的算法 *********************************************************************/ #ifndef BinaryTree_H ...
孟村回族自治县13455877478: 请问C语言如何创建二叉树???? - ?
捷功迪巧: 创建二叉树的源程序如下: #include <cstdlib>#include <stdio.h>typedef struct node{ //树的结点int data;struct node* left;struct node* right;} Node;typedef struct{ //树根Node* root;} Tree;void insert(Tree* tree, int value)//创建树{Node* ...
孟村回族自治县13455877478: 求二叉树的非递归后序遍历的c语言代码? - ?
捷功迪巧: #include<iostream> #include<stdio.h> #define N 10 using namespace std;char *a;typedef struct NODE{char data;struct NODE *lch, *rch,*parent; } *BINTREE,Node;void visit(char data){ printf("%5c",data); }void preorder(BINTREE T){ // 先...
孟村回族自治县13455877478: 二叉树(C语言)怎么创建? - ?
捷功迪巧: C语言中二叉树的创建需要用到结构体来定义一个树的数据类型.树这个数据结构有一些数据域,和多个指针域.当然,对于二叉树而言,一般可以定义两个指针域,分别指向root节点的左右子节点.数据结构定义:struct tree{ int data; //这里数据域以此为例 tree*right,*left;}; 真正构建二叉树可以使用动态内存申请,这是一种比较常见的方法(如果不会动态内存申请,可以先看看),但是这样做在子树很多时会耗费较多时间.因此可以事先开辟好一段内存空间用于存储树.比如 tree T[2000];如果需要建立新的子树,那么只需将数组中某个左右子节点赋值即可.如有疑问,欢迎继续追问.
孟村回族自治县13455877478: 求数据结构(C语言版)建立二叉树的代码~~急~~谢谢了 - ?
捷功迪巧: BT.H文件 #include <stdio.h> #include <malloc.h> #include <conio.h> #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OK 1 #define Stack_Size 50 #define NUM 50 #define MAXSIZE 50 //队列的最大长度 //定义二叉树 typedef char ...
孟村回族自治县13455877478: c语言二叉树代码求解 - ?
捷功迪巧: #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define MAX 20#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW 0 typedef char TElemType; typedef int Status; typedef struct BiTNode{ TElemType data; struct BiTNode *...
孟村回族自治县13455877478: 需要C语言二叉树的详细实现代码+解释. - ?
捷功迪巧: //数据结构 实现静态二叉树三种遍历方式 这是我写的 不懂追问 # include <stdio.h> # include <malloc.h> typedef struct tree { char data; struct tree * l; struct tree * r; }tr,* ptr; ptr init(void) { ptr a = (ptr)malloc(sizeof(tree)); ptr b = (ptr)malloc(sizeof(tree)); ...
孟村回族自治县13455877478: 有关二叉树的简单C语言程序. - ?
捷功迪巧: 先序输入 如 abc##d##e## (#表示空) 输出 cbdae#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#include "cstdlib"#include "malloc.h" typedef int Status; typedef char TElemType;#include #include ...
孟村回族自治县13455877478: 用C语言实现二叉树的操作 - ?
捷功迪巧: #include#define STACK_MAX_SIZE 30 #define QUEUE_MAX_SIZE 30 #ifndef elemType typedef char elemType; #endif /************************************************************************/ /* 以下是关于二叉树操作的11个简单算法...