『壹』 c語言中，遞歸先序遍歷和非遞歸先序遍歷的有何區別各自優缺點
1、遞歸就是函數調用函數本身，運行起來就是函數嵌套函數，層層嵌套，所以函數調用、參數堆棧都是不小的開銷，但是程序簡單。
2、非遞歸就是不斷地對參數入棧、出棧，省去了函數層層展開、層層調用的開銷。雖然參數出入棧次數多了，但是一般都開辟固定的足夠大的內存來一次性開辟、重復使用。
3、非遞歸是從堆棧的角度來編寫程序，速度快，但代碼復雜。
遞歸是從問題本身的邏輯角度來編寫，雖然速度相對慢，但代碼容易理解。
如果對速度要求不高，建議用遞歸方式。
4、摘錄例子如下：
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;//二叉樹的節點類型
typedef struct QNode
{
BiTNode data;
struct QNode *next;
} QNode,*QueuePtr;//隊列節點類型
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;//隊列的頭尾指針
void InitQueue(LinkQueue *Q)//創建隊列
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->rear->next=NULL;
}
void EnQueue(LinkQueue *Q,BiTNode e)//入隊操作
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
BiTNode DeQueue(LinkQueue *Q)//出對操作
{
BiTNode e;QueuePtr p;
p=Q->front->next;
e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return (e);
}
int QueueEmpty(LinkQueue *Q)//判斷隊列是否為空
{
if(Q->front==Q->rear )
return 1;
else
return 0;
}
BiTree CreateBiTree()//創建二叉樹
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=p;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return (T);
}
void PreOrder(BiTree T)//先序
{
if(T!=NULL)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void LevelOrder(BiTree T)//層次遍歷
{
LinkQueue Q; BiTNode p;
InitQueue(&Q);
EnQueue(&Q,*T);
while(!QueueEmpty(&Q))
{
p = DeQueue(&Q);
printf("%c",p.data);
if(p.lchild!=NULL)
EnQueue(&Q,*(p.lchild));
if(p.rchild!=NULL)
EnQueue(&Q,*(p.rchild));
}
}
void main()
{
BiTree Ta;
Ta=CreateBiTree();
printf("層次遍歷:");
printf("\n");
LevelOrder(Ta);
printf("\n");
printf("先序遍歷:");
printf("\n");
PreOrder(Ta);
}
層次使用非遞歸的，用到隊列
先序是用遞歸的
創建樹使用先序遞歸建樹
輸入個例子：
abc**de*f**g***(注意*代表空格，因為空格你看不到就不好表示).
『貳』 C語言數據機構：由中序遍歷和層次遍歷能不能唯一確定一顆二叉樹為什麼說法不一致哪
由中序遍歷和層次遍歷能夠唯一確定一顆二叉樹。從下面的演算法可知，每一步構造得到的二叉樹結果是唯一的。
以下構造部分的答案來自網路知道：
假定樹的層次遍歷ABCDEFG
HIJ中序遍歷DBGEHJACIF
兩種遍歷順序要結合著分析，才能畫出這顆樹的圖
比如，層次遍歷，先訪問到A節點，說明A是樹的根節點
那麼在中序遍歷結果里看：
DBGEHJ在A前面，說明這些節點，都在A左子樹上
CIF在A的後面，說這些節點，都在A的右子樹上
那麼，樹可以先這樣畫：
__________A________
________/____\_____
_____DBGEHJ__CIF___
再看層次遍歷，A後面是B，說明B是A左子樹的根節點
從上圖中的先序遍歷順序DBGEHJ中看到：
D在B的前面，說明D在B的左子樹上
GEHJ在B的後面，說明它們在B的右子樹上
那麼，樹又可以畫成：
_________A________
_______/____\_____
_____B________CIF__
____/__\____________
___D__GEHJ_________
如此循環，直到將整個樹都畫完全
結果如下：
_____________A_______________
___________/____\_____________
________B_________C__________
______/___\_________\_________
_____D_____E_________F_______
__________/__\_________\______
_________G____H_________I____
_______________\______________
_________________J____________
『叄』 由中序遍歷和層次遍歷還原二叉樹。C語言實現
經測，該代碼已經修改正確，只需在void BuildTree(char *level,char *inorder,pBiTree T)這里的最後一個變數T改為引用即可。還有一個地方判斷調用右子樹的地方的判斷條件。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedefstruct_BiTree
{
chardata;
struct_BiTree*lchild;
struct_BiTree*rchild;
}BiNode,*pBiTree;
voidBuildTree(char*level,char*inorder,pBiTree&T)
{
inti;
intlen=strlen(level);//取得層次遍歷長度
intpos=0;
if(len==0)
return;
char*p=strchr(inorder,level[0]);
if(p==NULL)//如果為空則拋棄第隱叢一個，跳到下一個；
{
char*L=(char*)malloc(sizeof(char)*len);//開辟數組
strncpy(L,level+1,len-1);//舍棄第一個
L[len-1]=0;
BuildTree(L,inorder,T);//調用建樹函數
return;
}
虧碧pos=p-inorder;//得到中序遍歷左子樹字元串長度
T->data=level[0];//為根節點賦值
T->lchild=NULL;
T->rchild=NULL;
if(pos!=0)//左子樹的遞歸調用
{
T->lchild=(pBiTree)malloc(sizeof(BiNode));
char*left_level=(char*)malloc(sizeof(char)*len);
char*left_inor=(char*)malloc(sizeof(char)*(pos));
strncpy(left_level,level+1,len-1);//捨去層次遍歷第一個
strncpy(left_inor,inorder,pos);//截取左子樹字元銷攜舉串
left_level[len-1]=0;
left_inor[pos]=0;
BuildTree(left_level,left_inor,T->lchild);
}
if(pos<strlen(inorder)-1)//右子樹的遞歸調用
{
T->rchild=(pBiTree)malloc(sizeof(BiNode));
char*right_level=(char*)malloc(sizeof(char)*(len));
char*right_inor=(char*)malloc(sizeof(char)*(len-pos));
strncpy(right_level,level+1,len-1);
strncpy(right_inor,inorder+pos+1,len-pos-1);
right_level[len-1]=0;
right_inor[len-pos-1]=0;
BuildTree(right_level,right_inor,T->rchild);
}
}
voidpriOrder(pBiTreeT)
{
if(T!=NULL){
printf("%c",T->data);
priOrder(T->lchild);
priOrder(T->rchild);
}
}
voidpostOrder(pBiTreeT)
{
if(T!=NULL){
postOrder(T->lchild);
postOrder(T->rchild);
printf("%c",T->data);
}
}
voidfreeNode(pBiTree&T)
{
if(T!=NULL){
freeNode(T->lchild);
freeNode(T->rchild);
free(T);
}
}
intmain()
{
pBiTreeroot;
charlevel[28],inorder[28];
intn;
scanf("%d",&n);
//fflush(stdin);
getchar();
while(n--){
scanf("%s%s",level,inorder);
root=(pBiTree)malloc(sizeof(BiNode));
BuildTree(level,inorder,root);
priOrder(root);
printf(" ");
postOrder(root);
printf(" ");
//freeNode(root);
}
return0;
}
『肆』 C語言實現左孩子右兄弟樹的建立，插入，層次遍歷，可以加分
問的有些問題，程序建立的2叉樹只能是完全2叉樹，其他的樹只能手動建立，我這里給你完全2叉樹的建立和遍歷，完全2叉樹是沒有插入的，給你函數
#include
#include
typedef
struct
_node_
{
int
data;
struct
_node_
*lchild,*rchild;
}bitree;
//遞歸建立完全2x樹，root每次遍歷後都會返回上層樹的根節點，這點容易理解錯，最終返回的root是整個2x樹的根節點，傳參int
i
是給2x樹賦值：1,2,3,4,5……，int
n是想建立的總共節點數。
bitree
*CreatBitree(int
i,int
n)
{
bitree
*root
=
(bitree*)malloc(sizeof(bitree));
root->data
=
i;
if(i
*
2
<=
n)
root->lchild
=
CreatBitree(2
*
i,n);
else
root->lchild
=
NULL;
if(i
*
2
+
1
<=n)
root
->rchild
=
CreatBitree
(2
*
i
＋1，n）；
else
root->rchild
=
NULL;
return
root;
}
//遍歷
void
proorder(bitree*
root)
{
if(root
==
NULL)
return;
printf("%d
",root->data);
proorder(root->lchild);
proorder(root->rchild);
}//這是根左右遍歷即前序遍歷，如果想改成中序或者後序只需要把printf改到lchild後和rchild後即可
寫完才發現你要層次遍歷啊？！，那個還要引入個隊列的建立，需要建隊，出隊，入隊的函數，全寫出來很麻煩的，寫2x樹的都不是初學了，我假設你已經有了隊列相關函數，給出函數功能注釋，然後直接給你層次遍歷的函數吧：
void
noorder(bitree
*root)
{
sequeue
*sq;//用的順序隊列，沒有用鏈式的，要不更麻煩了，sequeue是typedef的隊列結構體
sq
=
CreatEmptySequeue();//建立空隊列
EnSequeue(sq,root);//根節點入隊
while(!EmptySequeue(sq))//判斷隊列是否空
{
root
=
Desequeue;//出列
printf("%d",root->data);
if(root->lchild
!=NULL)
EnSequeue(sq,root->lchild);
if(root->rchild
!=
NULL)
EnSequeue(sq
,root->rchild);
}
return;
}
演算法描述，
利用隊列的先進先出的特性，首先把根節點入隊列，然後開始循環，先判斷隊列是否空，取出隊首元素並列印，然後檢查出列節點的左節點，有的話入隊，沒有的話檢查右節點，有的話入隊，開始下次循環，這時隊列里是第二層的左節點和有節點，這次是先列印2層左節點，然後讓2層的左孩子節點入隊，右孩子入隊，然後列印2層右節點，然後2層右節點的左孩子入隊，右孩子入隊，隊列中現在是第3層節點左邊依次向右，依次類推，層次列印2x樹
看在我折騰了那麼多，時隔這么久才有我給答案，分就別吝嗇了哈~~~嘿嘿
『伍』 如何用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語言遞歸有什麼用處，又有什麼缺點
遞歸好處：代碼更簡潔清晰，可讀性更好
遞歸可讀性好這一點，對於初學者可能會反對。實際上遞岩漏辯歸的代碼更清晰，但是從學習的角度要理解遞歸真正發生的什麼，是如何調用的，調用層次和路線，調用堆棧中保存了什麼，可能是不容易。但是不可否認遞歸的代碼更簡潔。一般來說，一個人可能很容易的寫出前中後序的二叉樹遍歷的遞歸演算法，要寫出相應的非遞歸演算法就搜滲比較考粗缺驗水平了，恐怕至少一半的人搞不定。所以說遞歸代碼更簡潔明了。
遞歸壞處：由於遞歸需要系統堆棧，所以空間消耗要比非遞歸代碼要大很多。而且，如果遞歸深度太大，可能系統撐不住。
『柒』 二叉樹的層次遍歷演算法
二叉樹的層次遍歷演算法有如下三種方法：
給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：
之後大家就可以自己畫圖了，下面給出程序代碼：
[cpp] view plain
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
最後給出完成代碼的測試用例：124##57##8##3#6##
[cpp] view plain
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == '#') {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)->data = c;
create_tree(&(*T)->lchild);
create_tree(&(*T)->rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout << T->data << " ";
print_tree(T->lchild);
print_tree(T->rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level < 0)
return 0;
if (0 == level) {
cout << T->data << " ";
return 1;
}
return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout << endl;
}
void print_by_level_2(Tree T) {
deque<tree_node_t*> q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout << temp->data << " ";
if (temp->lchild)
q_second.push_back(temp->lchild);
if (temp->rchild)
q_second.push_back(temp->rchild);
}
cout << endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
int main(int argc, char *argv[]) {
Tree T = NULL;
create_tree(&T);
print_tree(T);
cout << endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
『捌』 C語言根據層次遍歷和中序遍歷求二叉樹的前序遍歷和後序遍歷。下面有我的建樹函數，有注釋的。
#include"cstdio"
#include"vector"
#include"cstring"
#include"algorithm"
using namespace std;
const int maxn =30;
struct node{
int data;
node* lchild;
node* rchild;
};
int n;
int in[maxn];
bool vis[maxn]={false};
vector<int> lev;
node* create(vector<int> lev,int inl,int inr){
if(lev.size()==0) return NULL;
if(inl>inr) return NULL;
//printf("00\n");
node* root= new node;
root->data =lev[0];
int k;
for(k=inl;k<=inr;k++){
if(lev[0]==in[k])
break;
}
for(int j=inl;j<=k-1;j++)
vis[in[j]]=true;
vector<int> tempLeft,tempRight;//要函旁埋閉數體內新建
for(int i=1;i<運裂lev.size();i++){
if(vis[lev[i]]==true)
tempLeft.push_back(lev[i]);
else
tempRight.push_back(lev[i]);
}
root->液吵lchild =create(tempLeft,inl,k-1);
root->rchild =create(tempRight,k+1,inr);
return root;
}
void preorder(node* root){
if(root==NULL)
return;
printf("%d ",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
int main(){
scanf("%d",&n);
int x;
for(int i=0;i<n;i++){
scanf("%d",&x);
lev.push_back(x);
}
for(int j=0;j<n;j++)
scanf("%d",&in[j]);
node *root =create(lev,0,n-1);
preorder(root);
return 0;
}