1. c语言二叉树的应用
对于你的这种情况我觉得比较适合用数组来实现。对于长度为t的输入，申请类型为Node、长度为t的数组nodeArray[t]，然后进行两次遍历。第一次，nodeArray[i].data对应输入的第i个字符，nodeArray[i].lchild和rchild都为空；（如果输入#则nodeArray[i]=null）第二次，在[0,n-1]的范围内，令nodeArray[i].lchild=&(nodeArray[i*2])，nodeArray[i].rchild=&(nodeArray[i*2+1])。完成后，nodeArray[0]即为所求二叉树。应该有法一次遍历就构造好这棵树，懒得想了。
2. 二叉树c语言实现
#include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char data;
struct node *lchild,*rchild;//
}BiTNode,*BiTree;
void CreatBiTree(BiTree &T)
{
char ch;
ch=getchar();
if (ch == ' ')
T = 0;
else {
T=(BiTNode*)malloc(sizeof(BiTNode));
T->data=ch;//生成根节点
CreatBiTree(T->lchild);//构造左子树
CreatBiTree(T->rchild);//构造右子树
}
}
void preorder(BiTree T)//前序遍历
{
if (T!=NULL){
printf ("%c",T->data);
preorder(T->lchild);
preorder(T->rchild);
}
}
void inorder(BiTree T)//中序遍历
{
if (T!=NULL){
inorder(T->lchild);
printf ("%c",T->data);
inorder(T->rchild);
}
}
void postorder(BiTree T)//后序遍历
{
if (T!=NULL){
postorder(T->lchild);
postorder(T->rchild);
printf ("%c",T->data);
}
}
void main ()
{
cout<<"请输入要创建的二叉树包括空格:"<<endl ;
BiTree T;
CreatBiTree(T);//创建二叉树
cout<<"前序遍历的结果为:"<<endl;
preorder(T);
cout<<endl;
cout<<"中序遍历的结果为:"<<endl;
inorder(T);
cout<<endl;
cout<<"后序遍历的结果为:"<<endl;
postorder(T);
}
3. c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
4. c语言二叉树的删除
int TreeDelete(TreeNode *root,EleType data) //删除二叉树的结点
{
TreeNode *delp;
if(!root) return 0;
delp=Find(root,data);
if(!delp) return 0;
if(delp==root)
{
Destroy(root);
printf("Destroy the tree...");
exit(0);
}
if(delp->parent->lchild==delp) delp->parent->lchild=0;
if(delp->parent->rchild==delp) delp->parent->rchild=0;
Destroy(delp);
return 2;
}
int Destroy(TreeNode *root) //销毁二叉树
{
if(!root) return 0;
Destroy(root->lchild);
Destroy(root->rchild);
free(root);
printf("Destroy the tree...");
exit(0);
}
5. 二叉树的C语言程序求教
typedef char DataType;//给char起个别名 DataType
//定义二叉树的数据结构
typedef struct node{
DataType data;//二叉树存储的数据
struct node *lchild, *rchild;//二叉树的左、右子树的指针
}BinTNode;
typedef BinTNode *BinTree ; //自定义一个数据类型（二叉树的指针类型）
#include <stdio.h>
#include <malloc.h>
//以前序遍历构建二叉树
void CreatBinTree(BinTree *T)
{
char ch;//定义临时变量ch，用来接受数据
if ((ch=getchar())==' ')
*T=NULL;//如果输入为空，则停止构建二叉树
else{*T=(BinTNode *)malloc(sizeof(BinTNode));//为二叉树分配内存空间
(*T)->data=ch;//把输入的数据存入二叉树
CreatBinTree(&(*T)->lchild);//构建左子树（递归）
CreatBinTree(&(*T)->rchild);//构建左子树（递归）
}
}
//求二叉树的结点数
int Node(BinTree T)
{ int static nodes=0;//定义一个变量存储二叉树的结点数
if(T)//如果二叉树不为空（是结点），执行此语句
{
Node(T->lchild);//看左子树是不是个结点（递归）
nodes++;//结点数加1
Node(T->rchild);//看右子树是不是个结点（递归）
}
return nodes;//返回结点数
}
//求二叉树的叶子数
int Leaf(BinTree T)
{ int static leaves=0;//定义一个变量存储二叉树的叶子数
if(T)//如果二叉树不为空，执行此语句
{
Leaf(T->lchild);//看左子树是不是叶子（递归）
if(!(T->lchild||T->rchild))//如果二叉树T的左、右结点都为空，则执行此语句（即是叶子）
leaves++;//叶子数加1
Leaf(T->rchild);//看右子树是不是叶子（递归）
}
return leaves;//返回叶子数
}
#include <stdio.h>
void main()
{ BinTree root;
CreatBinTree(&root);//构建二叉树
int nodes=Node(root);//求此二叉树的结点数
int leaves=Leaf(root);//求此二叉树的叶子数
printf("\nnodes=%d leaves=%d",nodes,leaves);
}
上面是我的理解，好久没有写过代码了，如有错误，请指出。
6. 销毁二叉树
free(T)仅仅收回内存，不会改变T的指向。T=NULL是为了防止下面的代码使用这个已经收回的空间，让程序更安全。
7. 二叉树 C语言实现
编译通过
先序创建并输出
#include <stdio.h>
#include <stdlib.h>
typedef struct BTree{
char data;
struct BTree *lchild;
struct BTree *rchild;
}BinTree;
BinTree *pre_order()
{
BinTree *p;
char ch;
scanf("%c",&ch);
if(ch==' ')
return NULL;
p=(BinTree *)malloc(sizeof(BinTree));
p->data=ch;
p->lchild=pre_order();
p->rchild=pre_order();
return p;
}
BinTree *in_order()
{
BinTree *p;
char ch;
p->lchild=in_order();
scanf("%c",&ch);
if(ch==' ')
return NULL;
p->rchild=in_order();
}
void post_order(BinTree *p)
{
if(p!=NULL)
{
post_order(p->lchild);
post_order(p->rchild);
printf("%c ",p->data);
}
}
void main()
{
BinTree *tree;
printf("Please Enter the pre_order:\n");
tree=pre_order();
printf("\n");
//printf("Please Enter the in_order:\n");
//tree=in_order();
//printf("\n");
post_order(tree);
printf("\n");
}
先序和中序不能同时使用，要么就光先序，要么就再用另一个数做中序
8. 求解：一个二叉树的C语言程序
本程序在VC上调试运行无错误！
#include <iostream>
#include <stack>
#include <string>
using namespace std;
class Node
{
public:
char oper;//操作数或运算符
Node *left;//左子树
Node *right;//右子树
Node()
{
left=right=NULL;
oper=0;
}
Node(char op)
{
left=right=NULL;
oper=op;
}
};
bool isOper(char op)
{//判断是否为运算符
char oper[]={'(',')','+','-','*','/','^'};
for(int i=0;i<sizeof(oper);i++)
{
if(op==oper[i])
{
return true;
}
}
return false;
}
int getOperPri(char op)
{//求运算符的优先级
switch(op)
{
case '(':
return 1;
case '+':
case '-':
return 2;
case '*':
case '/':
return 3;
case '^':
return 4;
default:
return 0;
}
}
inline void freeTree(Node *p)
{//销毁二叉树
if(p->left!=NULL)
{
freeTree(p->left);
}
if(p->right!=NULL)
{
freeTree(p->right);
}
delete(p);
}
void postOrderTraverse(Node *p)
{//后序遍历
if(p)
{
postOrderTraverse(p->left);
postOrderTraverse(p->right);
cout<<p->oper;
}
}
void preOrderTraverse(Node *p)
{//先序遍历
if(p)
{
cout<<p->oper;
preOrderTraverse(p->left);
preOrderTraverse(p->right);
}
}
void inOrderTraverse(Node *p)
{//中序遍历
if(p)
{
if(p->left)
{
if(isOper(p->left->oper)
&& getOperPri(p->left->oper)
<getOperPri(p->oper))
{
cout<<"(";
inOrderTraverse(p->left);
cout<<")";
}
else
{
inOrderTraverse(p->left);
}
}
cout<<p->oper;
if(p->right)
{
if(isOper(p->right->oper)
&& getOperPri(p->right->oper)
<=getOperPri(p->oper))
{
cout<<"(";
inOrderTraverse(p->right);
cout<<")";
}
else
{
inOrderTraverse(p->right);
}
}
}
}
void generateTree(Node *&p, string expr)
{//生成二叉树
stack <char> operStack;
stack <Node*> dataStack;
char tmpchr,c;
int idx=0;
tmpchr=expr[idx++];
while(operStack.size()!=0 || tmpchr!='\0')
{
if(tmpchr!='\0' && !isOper(tmpchr))
{//不是运算符，则进操作数的栈
p=new Node(tmpchr);
dataStack.push(p);
tmpchr=expr[idx++];
}
else
{
switch(tmpchr)
{
case '('://进栈
operStack.push('(');
tmpchr=expr[idx++];
break;
case ')'://脱括号
while(true)
{
c=operStack.top();
operStack.pop();
if(c=='(')
{
break;
}
p=new Node(c);
if(dataStack.size())
{
p->right=dataStack.top();
dataStack.pop();
}
if(dataStack.size())
{
p->left=dataStack.top();
dataStack.pop();
}
dataStack.push(p);
}
tmpchr=expr[idx++];
break;
default:
if(operStack.size()==0 || tmpchr!='\0'
&& getOperPri(operStack.top())
< getOperPri(tmpchr))
{//进栈
operStack.push(tmpchr);
tmpchr=expr[idx++];
}
else
{//出栈
p=new Node(operStack.top());
p->oper=operStack.top();
if(dataStack.size())
{
p->right=dataStack.top();
dataStack.pop();
}
if(dataStack.size())
{
p->left=dataStack.top();
dataStack.pop();
}
dataStack.push(p);
operStack.pop();
}
break;
}
}
}
p=dataStack.top();
dataStack.pop();
}
int main()
{
int testCaseNum;
string expression;
Node *tree;
cout<<"请输入测试用例的数目:";
cin>>testCaseNum;
while(testCaseNum--)
{
cout<<endl<<"请输入字符串表达式:";
cin>>expression;
generateTree(tree,expression);
cout<<"中缀表达式为:";
inOrderTraverse(tree);
cout<<endl;
cout<<"前缀表达式为:";
preOrderTraverse(tree);
cout<<endl;
cout<<"后缀表达式为:";
postOrderTraverse(tree);
cout<<endl;
freeTree(tree);
}
return 0;
}
9. 设计一个c语言程序，实现二叉树的前序、中序、后序的递归、非递归遍历运算
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树： ");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树： ");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf(" \n后序递归遍历二叉树：");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
printf("\n");
}