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");
}