二叉樹實現c語言

Ⅰ c語言二叉樹遞歸演算法怎麼做

#include<stdio.h>
#include<string.h>

structtreenode{
intvalue;
treenode*left;
treenode*right;
};
typedeftreenode*BiTree;

voidvisit(treenode*node)
{
printf("%2d",node->value);
}

//結點總數
intnode(BiTreeT)
{
if(!T){
return0;
}
returnnode(T->left)+node(T->right)+1;
}

//前序
voidpreOrder(BiTreeT)
{
if(T){
visit(T);
preOrder(T->left);
preOrder(T->right);
}
}

//中序
voidinOrder(BiTreeT)
{
if(T){
inOrder(T->left);
visit(T);
inOrder(T->right);
}
}

//後序
voidpostOrder(BiTreeT)
{
if(T){
postOrder(T->left);
postOrder(T->right);
visit(T);
}
}

//葉子節點數
intleafnode(BiTreeT)
{
if(T){
if(!T->left&&!T->right)
return1;
else
leafnode(T->left)+leafnode(T->right);
}else{
return0;
}
}

intheight(BiTreeT)
{
if(T){
intlh=height(T->left);
intrh=height(T->right);
return(lh>rh?lh:rh)+1;
}else{
return0;
}
}

intmain()
{


return0;
}

Ⅱ 二叉樹 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");
}
先序和中序不能同時使用，要麼就光先序，要麼就再用另一個數做中序

Ⅲ 二叉排序樹的實現（c語言）

/*二叉樹的基本運算與實現*/
#include <stdio.h>
#include <malloc.h>
#define MAXNODE 256
typedef int datatype;
typedef struct BiTNode
{
datatype data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct
{
BiTree link;
int flag;
}stacktype;void menu();
int Initiate(BiTree *bt,datatype x);
BiTree InsertL(BiTree bt,datatype x,BiTree parent);
BiTree InsertR(BiTree bt,datatype x,BiTree parent);
BiTree DeleteL(BiTree bt,BiTree parent);
BiTree DeleteR(BiTree bt,BiTree parent);
void PreOrder(BiTree bt);
void InOrder(BiTree bt);
void PostOrder(BiTree bt);
void LevelOrder(BiTree bt);
BiTree Find(BiTree parent,datatype a);
void NRPreOrder(BiTree bt);
void NRInOrder(BiTree bt);
void NRPostOrder(BiTree bt);void main()
{
int n,m=1;
BiTree t; /*clrscr();*/
while(m)
{
menu();
scanf("%d",&n);
switch(n)
{
case 1:{/*初始化*/
int flag;
datatype x;
printf("please input head point x:\n");
scanf("%d",&x);
flag=Initiate(&t,x);
if(flag==1)
printf("\nInitiate success!");
else
printf("\nInitiate fail!");
break;
}
case 2:{/*建樹*/
break;
}
case 3:{/*插入結點x作為a的左孩子*/
datatype a,x;/*x作為a的左孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",&a,&x);
parent=Find(parent,a);
parent=InsertL(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 4:{/*插入結點x作為a的右孩子*/
datatype a,x;/*x作為a的右孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",&a,&x);
parent=Find(parent,a);
parent=InsertR(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 5:{/*刪除結點a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",&a);
parent=Find(parent,a);
parent=DeleteL(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 6:{/*刪除結點a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",&a);
parent=Find(parent,a);
parent=DeleteR(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 7:{/*遞歸先序遍歷*/
PreOrder(t);
break;
}
case 8:{/*遞歸中序遍歷*/
InOrder(t);
break;
}
case 9:{/*遞歸後序遍歷*/
PostOrder(t);
break;
}
case 10:{/*層次遍歷*/
LevelOrder(t);
break;
}
case 11:{/*先序遍歷的非遞歸實現*/
NRPreOrder(t);
break;
}
case 12:{/*中序遍歷的非遞歸實現*/
NRInOrder(t);
break;
}
case 13:{/*後序遍歷的非遞歸實現*/
NRPostOrder(t);
break;
}
case 0:m=0;
}
}
}
void menu()
{
/*clrscr();*/
printf("\n");
printf("\t\t1.initiate\n\n");
printf("\t\t2.create thread\n\n");
printf("\t\t3.insert Left\n\n");
printf("\t\t4.insert Right\n\n");
printf("\t\t5.delete Left\n\n");
printf("\t\t6.delete Right\n\n");
printf("\t\t7.preorder\n\n");
printf("\t\t8.inorder\n\n");
printf("\t\t9.postorder\n\n");
printf("\t\t10.levelorder\n\n");
printf("\t\t11.nrpreorder\n\n");
printf("\t\t12.nrinorder\n\n");
printf("\t\t13.nrpostorder\n\n");
printf("\t\t0.exit\n\n");
printf("\n\n\n\tplease select:");
}
int Initiate(BiTree *bt,datatype x)
{
if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return 0;
(*bt)->data=x;
(*bt)->lchild=NULL;
(*bt)->rchild=NULL;
return 1;
}
BiTree InsertL(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->lchild==NULL)
parent->lchild=p;
else
{
p->lchild=parent->lchild;
parent->lchild=p;
}
return bt;
}
BiTree InsertR(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->rchild==NULL)
parent->rchild=p;
else
{
p->rchild=parent->rchild;
parent->rchild=p;
}
return bt;
}
BiTree DeleteL(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->lchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent->lchild;
parent->lchild=NULL;
free(p);
return bt;
}
BiTree DeleteR(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent->rchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent->rchild;
parent->rchild=NULL;
free(p);
return bt;
}
void PreOrder(BiTree bt)
{
if(bt==NULL)
return;
printf("%5d",bt->data);
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
void InOrder(BiTree bt)
{
if(bt==NULL)
return;
InOrder(bt->lchild);
printf("%5d",bt->data);
InOrder(bt->rchild);
}
void PostOrder(BiTree bt)
{
if(bt==NULL)
return;
PostOrder(bt->lchild);
PostOrder(bt->rchild);
printf("%5d",bt->data);
}
void LevelOrder(BiTree bt)
{
BiTree Queue[MAXNODE];
int front,rear;
if(bt==NULL)
{
return;
}
front = -1;
rear = 0;
Queue[rear] = bt;
while(front!=rear)
{
front++;
printf("%5d",Queue[front]->data);
if(Queue[front]->lchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->lchild;
}
if(Queue[front]->rchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]->rchild;
}
}//end while
}
BiTree Find(BiTree parent,datatype a)
{
BiTree p;
if(parent==NULL)
p=NULL;
else if(parent->data==a)
p=parent;
else
{
p=Find(parent->lchild,a);
if(p==NULL)
p=Find(parent->rchild,a);
}
return p;
}
void NRPreOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
printf("%5d",p->data);
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p->lchild;
} /* end while p */
p=stack[top];
top--;
p=p->rchild;
} /* end while p && top */
}
void NRInOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p->lchild;
} /* end while p */
p=stack[top];
top--;
printf("%5d",p->data);
p=p->rchild;
} /* end while p && top */
}
void NRPostOrder(BiTree bt)
{
stacktype stack[MAXNODE];
BiTree p;
int top,sign;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
if(p!=NULL) /*結點第一次入棧*/
{
top++;
stack[top].link=p;
stack[top].flag=1; /*標記第一次入棧*/
p=p->lchild;
} /* end if */
else
{
p=stack[top].link;
sign=stack[top].flag;
top--;
if(sign==1) /*結點第二次入棧*/
{
top++;
stack[top].link=p;
stack[top].flag=2; /*標記第二次入棧*/
p=p->rchild;
} /* end if */
else
{
printf("%5d",p->data);
p=NULL;
} /* end if-else */
} /* end if-else */
} /* end while */
}

Ⅳ 二叉樹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);
}

Ⅳ 如何用C語言實現層次遍歷二叉樹

下面是c語言的前序遍歷二叉樹的演算法，在這里假設的節點元素值假設的為字元型，
說明：演算法中用到了結構體，也用到了遞歸的方法，你看看怎麼樣，祝你好運！
#include"stdio.h"
typedef
char
elemtype;
typedef
struct
node
//定義鏈表結構
{
elemtype
data;
//定義節點值
struct
note
*lchild;
//定義左子節點值
struct
note
*rchild;
//定義右節點值
}btree;
preorder(btree
*root)
//前序遍歷
{
if(roof!=null)
//如果不是空節點
{
printf("%c\n",root->data);
//輸出當前節點
preorder(root->lchild);
//遞歸前序遍歷左子節點
preorder(root->rchild);
//遞歸前序遍歷右子節點
}
return;
//結束
}

Ⅵ C語言 二叉樹的建立

從鍵盤輸入字元，然後回車，字元會停留在緩沖區內，之後你每次scanf("%c", &ch)就會從緩沖區取出一個來

Ⅶ 二叉樹的基本操作 C語言版的

#include<stdio.h>
#include<malloc.h>
int count=0;
typedef struct BiTNode { // 結點結構
char data;
struct BiTNode *lchild, *rchild; // 左右孩子指針
} BiTNode, *BiTree;

void CreateBiTree(BiTree &T){
char ch;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
if(!(T = (BiTNode * )malloc(sizeof(BiTNode)))) return;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}//CreatBiTree
int PreOrder(BiTree T)//先序遍歷二叉樹的遞歸演算法
{
if (!T) return 0;
printf("%c ",T->data); // 訪問結點
PreOrder(T->lchild); // 遍歷左子樹
PreOrder(T->rchild);// 遍歷右子樹
return 1;
}
int InOrder(BiTree T)//先序遍歷二叉樹的遞歸演算法
{
if (!T) return 0;

InOrder(T->lchild); // 遍歷左子樹
printf("%c ",T->data); // 訪問結點
InOrder(T->rchild);// 遍歷右子樹
return 1;
}
int PostOrder(BiTree T)//先序遍歷二叉樹的遞歸演算法
{
if (!T) return 0;

PostOrder(T->lchild); // 遍歷左子樹
PostOrder(T->rchild);// 遍歷右子樹
printf("%c ",T->data); // 訪問結點
return 1;
}
int CountLeaf (BiTree T){
//返回指針T所指二叉樹中所有葉子結點個數
if (!T ) return 0;//空樹
if (!T->lchild && !T->rchild) return 1;//只有樹根
int m;
int n;
m = CountLeaf( T->lchild);

n = CountLeaf( T->rchild);

return (m+n);

} // CountLeaf

void main(){
int a;
BiTree T;
CreateBiTree(T);
printf("先序遍歷：");
PreOrder(T);
printf("中序遍歷：");
InOrder(T);
printf("後序遍歷：");
PostOrder(T);
a=CountLeaf(T);
printf("葉子節點個數：");
printf("%d",a);
}

Ⅷ 請問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* node=(Node*)malloc(sizeof(Node));//創建一個節點

node->data = value;

node->left = NULL;

node->right = NULL;

if (tree->root == NULL)//判斷樹是不是空樹

{

tree->root = node;

}

else

{//不是空樹

Node* temp = tree->root;//從樹根開始

while (temp != NULL)

{

if (value < temp->data)//小於就進左兒子

{

if (temp->left == NULL)

{

temp->left = node;

return;

}

else

{//繼續判斷

temp = temp->left;

}

}

else {//否則進右兒子

if (temp->right == NULL)

{

temp->right = node;

return;

}

else {//繼續判斷

temp = temp->right;

}

}

}

}

return；

}

void inorder(Node* node)//樹的中序遍歷

{

if (node != NULL)

{

inorder(node->left);

printf("%d ",node->data);

inorder(node->right);

}

}

int main()

{

Tree tree;

tree.root = NULL;//創建一個空樹

int n;

scanf("%d",&n);

for (int i = 0; i < n; i++)//輸入n個數並創建這個樹

{

int temp;

scanf("%d",&temp);

insert(&tree, temp);

}

inorder(tree.root);//中序遍歷

getchar();

getchar();

return 0;

}

(8)二叉樹實現c語言擴展閱讀：

簡單二叉樹定義範例：此樹的順序結構為：ABCDE

#include <cstdlib>

#include <stdio.h>

#include <string>

int main()

{

node* p = newnode;

node* p = head;

head = p;

string str;

cin >> str;

creat(p, str, 0)//默認根結點在str下標0的位置

return 0;

}

//p為樹的根結點（已開辟動態內存）,str為二叉樹的順序存儲數組ABCD##E或其他順序存儲數組，r當前結點所在順序存儲數組位置

void creat(node* p, string str, int r)

{

p->data = str[r];

if (str[r * 2 + 1] == '#' || r * 2 + 1 > str.size() - 1)p->lch = NULL；

else

{

p->lch = newnode;

creat(p->lch, str, r * 2 + 1);

}

if (str[r * 2 + 2] == '#' || r * 2 + 2 > str.size() - 1)p->rch = NULL;

else

{

p->rch = newnode;

creat(p->rch, str, r * 2 + 2);

}

}

Ⅸ 二叉樹C語言演算法,急!!!!

清華大學
嚴蔚敏
的<數據結構里>都有完整的代碼,解釋的也很清楚
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
typedef
struct
tree
{
struct
tree
*left;
int
date;
struct
tree
*right;
}treenode,*b_tree;
///////插入節點/////////////////////
b_tree
insert(b_tree
root,int
node)
{
b_tree
newnode;
b_tree
currentnode;
b_tree
parentnode;
newnode=(b_tree)malloc(sizeof(treenode));
newnode->date=node;
newnode->right=NULL;
newnode->left=NULL;
if(root==NULL)
return
newnode;
else
{
currentnode=root;
while(currentnode!=NULL)
{
parentnode=currentnode;
if(currentnode->date>node)
currentnode=currentnode->left;
else
currentnode=currentnode->right;
}
if(parentnode->date>node)
parentnode->left=newnode;
else
parentnode->right=newnode;
}
return
root;
}
//////建立樹///////////////////
b_tree
creat(int
*date,int
len)
{
b_tree
root=NULL;
int
i;
for(i=0;i<len;i++)
root=insert(root,date[i]);
return
root;
}
//////中序列印////////////////
void
print1(b_tree
root)
{if(root!=NULL)
{
print1(root->left);
printf("%d->",root->date);
print1(root->right);
}
}
//////後序列印////////////////
void
print2(b_tree
root)
{if(root!=NULL)
{
print2(root->left);
print2(root->right);
printf("%d->",root->date);
}
}
//////前序列印////////////////
void
print3(b_tree
root)
{if(root!=NULL)
{
printf("%d->",root->date);
print3(root->left);
print3(root->right);
}
}
//////////在二叉樹中查找給定關鍵字
////////////
b_tree
lookfor(b_tree
root,int
e)
{
b_tree
p1,p2;
if(root!=NULL)
{
if(root->date==e)
return
root;
else
p1=lookfor(root->left,e);
p2=lookfor(root->right,e);
if(p1!=NULL)
return
p1;
else
if(p2!=NULL)
return
p2;
else
return
NULL;
}
else
return
NULL;
}
///////測試函數//////////////////
void
main()
{
b_tree
root=NULL;
int
i,index;
int
value;
int
nodelist[20];
cout<<"輸入樹的節點，輸入0結束\n";
index=0;
cin>>value;
while(value!=0)
{
nodelist[index]=value;
index=index+1;
cin>>value;
}
root=creat(nodelist,index);
printf("\n中序列印\n");
print1(root);
printf("\n後序列印\n");
print2(root);
printf("\n前序列印\n");
print3(root);
printf("\n查找的詞：\n");
int
a;
scanf("%d",&a);
b_tree
p3=lookfor(root,a);
if(p3!=NULL)
printf("%d\n",p3->date);
else
printf("沒你要找的詞");
}

Ⅹ 用c語言寫二叉樹，源代碼。

二叉樹是採用遞歸定義的，實現起來代碼簡潔（也許並不簡單）。並且它在具體的計算機科學中有很重要的運用，是一種很重要的數據結構，二叉樹有三種遍歷和建立的方式。今天先學習一下它的建立和列印。
以下代碼在Win-Tc1.9.1下編譯通過。

#include <stdio.h>
#define ElemType char
//節點聲明，數據域、左孩子指針、右孩子指針
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序建立二叉樹
BiTree CreateBiTree(){
char ch;
BiTree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根節點
}
//先序遍歷二叉樹
void PreOrderTraverse(BiTree T){
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

//中序遍歷
void InOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
printf("%c",T->data);
PreOrderTraverse(T->rchild);
}
}
//後序遍歷
void PostOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
void main(){
BiTree T;
T = CreateBiTree();//建立
PreOrderTraverse(T);//輸出
getch();
}