導航:首頁 > 編程語言 > 遍歷遞歸建立二叉樹python

遍歷遞歸建立二叉樹python

 發布時間：2022-07-04 19:39:28

『壹』 關於python中一個遞歸二叉樹遍歷的問題

if subsetWork+s[WORK]>maxWork:中，
s[WORK]是否應該改為s[WORK][2]

『貳』 python怎麼做二叉查找樹

可以的，和C++中類的設計差不多，以下是二叉樹的遍歷
class BTree:
def __init__(self,value):
self.left=None
self.data=value
self.right=None

def insertLeft(self,value):
self.left=BTree(value)
return self.left
#return BTree(value)

def insertRight(self,value):
self.right=BTree(value)
return self.right

def show(self):
print self.data

def preOrder(node):
node.show()
if node.left:
preOrder(node.left)
if node.right:
preOrder(node.right)

def inOrder(node):
if node:
if node.left:
inOrder(node.left)
node.show()
if node.right:
inOrder(node.right)

if __name__=='__main__':
Root=BTree('root')
A=Root.insertLeft('A')
C=A.insertLeft('C')
D=A.insertRight('D')
F=D.insertLeft('F')
G=D.insertRight('G')
B=Root.insertRight('B')
E=B.insertRight('E')

preOrder(Root)
print 'This is binary tree in-traversal'
inOrder(Root)

『叄』 建立二叉樹,並實現先序遍歷（ 用遞歸）

你看這2個哪個符合你的要求
我想了半天了,我不太會弄這個
#include <stdio.h> /*如發現bug請給我留言*/
#include <conio.h>
#include <stdlib.h>
#define LEN sizeof(struct node)
struct node
{
char data;
struct node *lchild,*rchild;
};
struct node *build()
{
struct node *stack[20]={NULL},*root,*temp,*p;
char c;
int i=-1;
c=getch();
if(c=='0')
return NULL;
root=p=(struct node *)malloc(LEN);
p->data=c;
c=getch();
while(1)
{
while(c!='0')
{
stack[++i]=p;
p=(struct node *)malloc(LEN);
p->data=c;
stack[i]->lchild=p;
c=getch();
}
p->lchild=NULL;
c=getch();
while(c=='0'&&i>=0)
{
p->rchild=NULL;
p=stack[i--];
c=getch();
}
if(c!='0')
{
temp=(struct node *)malloc(LEN);
p->rchild=temp;
temp->data=c;
p=temp;
c=getch();
}
else if(c=='0'&&i<0)
return root;
}
}
void output(struct node *head) /*中序輸入出二叉樹*/
{
struct node *stack[20],*p1=head;
int i=-1;
char c;
if(head==NULL)
return;
while(1)
{
while(p1->lchild!=NULL)
{
stack[++i]=p1;
p1=p1->lchild;
}
printf("%c",p1->data);
while(p1->rchild==NULL&&i>=0)
{
p1=stack[i--];
printf("%c",p1->data);
}

if(p1->rchild!=NULL)
{

p1=p1->rchild;

}
else if(p1->rchild==NULL&&i<0)
break;
}
}
int main(int argc, char *argv[])
{
struct node *head;
head=build();
output(head);
printf("\n");
return 0;
}

#include<stdio.h>
#include<stdlib.h>

#define D 2
#define R 10
#define N 11
typedef int KeyType;
typedef int DataType;

struct Node;
typedef struct Node radixNode;
struct Node
{
KeyType key[D];
/* DataType info; */
radixNode *next;
};

typedef radixNode * radixList;
typedef struct QueueNode
{
radixNode *f;
radixNode *e;
} Queue;
Queue queue[R];

void display(radixNode *plist)
{
int i;
radixNode *p;
p=plist->next;

while(p!=NULL)
{
printf("->");
for(i=0;i<D;i++)
printf("%1d",p->key[i]);
p=p->next;
}
printf("\n");
}

void radixSort(radixNode *plist,int d,int r)
{
int i,j,k;
radixNode *p,*head;
head=plist->next;
for(j=d-1;j>=0;j--)
{
p=head;
for(i=0;i<r;i++)
{
queue[i].f=NULL;
queue[i].e=NULL;
}
while(p!=NULL)
{
k=p->key[j];
if(queue[k].f==NULL)
queue[k].f=p;
else
(queue[k].e)->next=p;
queue[k].e=p;
p=p->next;
}
i=0;
while(queue[i].f==NULL)
i++;
p=queue[i].e; head=queue[i].f;
for(i++;i<r; i++)
if(queue[i].f!=NULL)
{
p->next=queue[i].f;
p=queue[i].e;
}
p->next=NULL;
printf("j=%d",j);
}
plist->next=head;
}

void main()
{
radixNode *p,*q,*head;
int a[]={30,12,20,17,40,60,34,42,29,35,47};
int i;

p=(radixNode *) malloc(sizeof(struct Node));
head=p;

p->next=NULL;
printf("test...\n");
for(i=0;i<11;i++)
{
q=(radixNode *) malloc(sizeof(struct Node));

q->key[0]=a[i]/10;
q->key[1]=a[i]%10;
q->next=NULL;
p->next=q;
p=p->next;

}
printf("before:\n");
display(head);
printf("\n");
radixSort(head,D,R);
printf("after:\n");
display(head);
}

『肆』 簡單的遞歸遍歷二叉樹

不知道你這代碼是怎麼調通了的，我稍微改了一點，運行不報錯，你自己試試，就改了main函數前面點。

voidmain()
{/*測試各個遍歷程序*/
BTnodeA[11];
charData[12]="-+/a*efb-cd";
inti=0;
for(i=0;i<11;i++)
A[i].data=Data[i];
A[0].Lchild=&A[1];A[0].Rchild=&A[2];
A[1].Lchild=&A[3];A[1].Rchild=&A[4];
A[2].Lchild=&A[5];A[2].Rchild=&A[6];
A[3].Lchild=NULL;A[3].Rchild=NULL;
A[4].Lchild=&A[7];A[4].Rchild=&A[8];
A[5].Lchild=NULL;A[5].Rchild=NULL;
A[6].Lchild=NULL;A[6].Rchild=NULL;
A[7].Lchild=NULL;A[7].Rchild=NULL;
A[8].Lchild=&A[9];A[8].Rchild=&A[10];
A[9].Lchild=NULL;A[9].Rchild=NULL;
A[10].Lchild=NULL;A[10].Rchild=NULL;
printf("gouzaoshu
");
printf("
preordertree
");
PreOrder(A);
printf("
inordertree
");
InOrder(A);
printf("
postordertree
");
PostOrder(A);
printf("
");
}

『伍』 建立二叉樹，層序、先序遍歷（ 用遞歸或非遞歸的方法都可以）

//聲明類BiTree及定義結構BiNode,文件名為bitree.h
#ifndef BITREE_H
#define BITREE_H

template <class T>
struct BiNode //二叉樹的結點結構
{
T data;
BiNode<T> *lchild, *rchild;
};

template <class T>
class BiTree
{
public:
BiTree( ); //構造函數，初始化一棵二叉樹，其前序序列由鍵盤輸入
~BiTree(void); //析構函數，釋放二叉鏈表中各結點的存儲空間
BiNode<T>* Getroot(); //獲得指向根結點的指針
void PreOrder(BiNode<T> *root); //前序遍歷二叉樹
void InOrder(BiNode<T> *root); //中序遍歷二叉樹
void PostOrder(BiNode<T> *root); //後序遍歷二叉樹
void LeverOrder(BiNode<T> *root); //層序遍歷二叉樹
private:
BiNode<T> *root; //指向根結點的頭指針
BiNode<T> *Creat( ); //有參構造函數調用
void Release(BiNode<T> *root); //析構函數調用
};
#endif

//定義類中的成員函數，文件名為bitree.cpp
#include<iostream>
#include<string>
#include"bitree.h"
using namespace std;

/*
*前置條件：二叉樹不存在
*輸 入：無
*功 能：構造一棵二叉樹
*輸 出：無
*後置條件：產生一棵二叉樹
*/
template<class T>
BiTree<T>::BiTree( )
{
this->root = Creat( );
}
/*
*前置條件：二叉樹已存在
*輸 入：無
*功 能：釋放二叉鏈表中各結點的存儲空間
*輸 出：無
*後置條件：二叉樹不存在
*/
template<class T>
BiTree<T>::~BiTree(void)
{
Release(root);
}
/*
*前置條件：二叉樹已存在
*輸 入：無
*功 能：獲取指向二叉樹根結點的指針
*輸 出：指向二叉樹根結點的指針
*後置條件：二叉樹不變
*/
template<class T>
BiNode<T>* BiTree<T>::Getroot( )
{
return root;
}
/*
*前置條件：二叉樹已存在
*輸 入：無
*功 能：前序遍歷二叉樹
*輸 出：二叉樹中結點的一個線性排列
*後置條件：二叉樹不變
*/
template<class T>
void BiTree<T>::PreOrder(BiNode<T> *root)
{
if(root==NULL) return;
else{
cout<<root->data<<" ";
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}

/*
*前置條件：二叉樹已存在
*輸 入：無
*功 能：中序遍歷二叉樹
*輸 出：二叉樹中結點的一個線性排列
*後置條件：二叉樹不變
*/
template <class T>
void BiTree<T>::InOrder (BiNode<T> *root)
{
if (root==NULL) return; //遞歸調用的結束條件
else{
InOrder(root->lchild); //中序遞歸遍歷root的左子樹
cout<<root->data<<" "; //訪問根結點的數據域
InOrder(root->rchild); //中序遞歸遍歷root的右子樹
}
}
/*
*前置條件：二叉樹已存在
*輸 入：無
*功 能：後序遍歷二叉樹
*輸 出：二叉樹中結點的一個線性排列
*後置條件：二叉樹不變
*/
template <class T>
void BiTree<T>::PostOrder(BiNode<T> *root)
{
if (root==NULL) return; //遞歸調用的結束條件
else{
PostOrder(root->lchild); //後序遞歸遍歷root的左子樹
PostOrder(root->rchild); //後序遞歸遍歷root的右子樹
cout<<root->data<<" "; //訪問根結點的數據域
}
}

/*
*前置條件：二叉樹已存在
*輸 入：無
*功 能：層序遍歷二叉樹
*輸 出：二叉樹中結點的一個線性排列
*後置條件：二叉樹不變
*/
template <class T>
void BiTree<T>::LeverOrder(BiNode<T> *root)
{
const int MaxSize = 100;

int front = 0;
int rear = 0; //採用順序隊列，並假定不會發生上溢

BiNode<T>* Q[MaxSize];
BiNode<T>* q;

if (root==NULL) return;
else{
Q[rear++] = root;
while (front != rear)
{
q = Q[front++];
cout<<q->data<<" ";
if (q->lchild != NULL) Q[rear++] = q->lchild;
if (q->rchild != NULL) Q[rear++] = q->rchild;
}
}
}

/*
*前置條件：空二叉樹
*輸 入：數據ch;
*功 能：初始化一棵二叉樹,構造函數調用
*輸 出：無
*後置條件：產生一棵二叉樹
*/
template <class T>
BiNode<T>* BiTree<T>::Creat( )
{
BiNode<T>* root;
T ch;
cout<<"請輸入創建一棵二叉樹的結點數據"<<endl;
cin>>ch;
if (ch=="#") root = NULL;
else{
root = new BiNode<T>; //生成一個結點
root->data=ch;
root->lchild = Creat( ); //遞歸建立左子樹
root->rchild = Creat( ); //遞歸建立右子樹
}
return root;
}

/*
*前置條件：二叉樹已經存在
*輸 入：無
*功 能：釋放二叉樹的存儲空間，析構函數調用
*輸 出：無
*後置條件：二叉樹不存在
*/
template<class T>
void BiTree<T>::Release(BiNode<T>* root)
{
if (root != NULL){
Release(root->lchild); //釋放左子樹
Release(root->rchild); //釋放右子樹
delete root;
}
}

//二叉樹的主函數，文件名為bitreemain.cpp
#include<iostream>
#include<string>
#include"bitree.cpp"
using namespace std;

void main()
{
BiTree<string> bt; //創建一棵樹
BiNode<string>* root = bt.Getroot( ); //獲取指向根結點的指針

cout<<"------前序遍歷------ "<<endl;
bt.PreOrder(root);
cout<<endl;
cout<<"------中序遍歷------ "<<endl;
bt.InOrder(root);
cout<<endl;
cout<<"------後序遍歷------ "<<endl;
bt.PostOrder(root);
cout<<endl;
cout<<"------層序遍歷------ "<<endl;
bt.LeverOrder(root);
cout<<endl;
}

『陸』 關於二叉樹遍歷的遞歸實現

我把上星期做的給你參考一下。有用就頂一下吧。
PS：你寫代碼的時候最好寫多點注釋，方便自己以後閱讀，也方便人家閱讀。

#include "stdio.h"
#include "stdlib.h"
typedef char TElemType;
#define ERROR -1;

typedef struct BitNode{
TElemType data;
struct BitNode *lchild,*rchild;//左右孩子指針
}BitNode,*BitTree;

//按先序次序輸入二叉樹中的結點的值（一個字元），空格字元表示空樹
//構造二叉樹表表示的二叉樹T
void CreateBitTree(BitTree &T){
char ch;
scanf("%c",&ch);
if(ch==' ') T=NULL;
else
{ T=(BitNode *)malloc(sizeof(BitNode));
T->data=ch;//生成根結點
CreateBitTree(T->lchild);//構造左子樹
CreateBitTree(T->rchild);//構造右子樹
}//else
}//CreateBitTree

//訪問函數——列印
int visit(TElemType e)
{ printf("%c",e);
return 1;
}//visit

//先序遍歷(根->左->右),visit()訪問每一個樹結點
//規律：最先訪問data
int PreOrderTraverse(BitTree T,int (*visit)(TElemType)){
if(T)
{
if(visit(T->data))
if(PreOrderTraverse(T->lchild,visit))
if(PreOrderTraverse(T->rchild,visit))
return 1;
}//if
else
return 1;
}//PreOrderTraverse

//中序遍歷(左->根->右)，visit()訪問每一個樹結點
//規律：在遞歸右指針前訪問data
int InOrderTraverse(BitTree T,int (*visit)(TElemType)){
if(T)
{
if(InOrderTraverse(T->lchild,visit))
visit(T->data);
if(InOrderTraverse(T->rchild,visit))
return 1;
}//if
else
return 1;
}//InOrderTraverse

//後序遍歷(左->右->根)，visit()訪問每一個樹結點
//規律：在遞歸右指針後訪問data
int PostOrderTraverse(BitTree T,int (*visit)(TElemType)){
if(T){
PostOrderTraverse(T->lchild,visit);
PostOrderTraverse(T->rchild,visit);
visit(T->data);
}//if
else
return 1;
}//PostOrderTraverse

void main()
{ BitTree T;
printf("請輸入二叉樹的結點（空格表示空樹）：");
CreateBitTree(T);
printf("先序遍歷的二叉樹輸出如下：");
PreOrderTraverse(T,visit);
printf("\n");
printf("中序遍歷的二叉樹輸出如下：");
InOrderTraverse(T,visit);
printf("\n");
printf("後序遍歷的二叉樹輸出如下：");
PostOrderTraverse(T,visit);
printf("\n");
system("pause");
}//main

『柒』 遍歷二叉樹的遞歸程序詳解

這是一個先序遍歷遞歸演算法void preorder(struct bitree *root){
struct bitree *p;
p=root;
if(p!=NULL)//不為空樹
{
printf("%d\n",p->data);//先訪問數據區，即根結點
preorder(p->lchild);//再訪問左孩子(樹)
preorder(p->rchild);//再訪問右孩子(樹)
}
}比如一顆完全二叉樹,層次遍歷為(A)(BC)(DEFG)(HIJKLMNO)按照這的先序遍歷過程為:第一次調用,所以訪問到A<進入第一層遞歸>訪問以B為根結點的樹(A的左子樹),所以訪問到B.<進入第二層遞歸>訪問以D為根結點的樹(B的左子樹),.所以訪問到D.<進入第三層遞歸>訪問以H為根結點的樹(D的左子樹),.所以訪問到H.<進入第四層遞歸>訪問H的左子樹,因為H是葉子結點(即左孩子指針P=NULL),返回第三層遞歸,<再進入第四層遞歸>訪問H的右子樹,因為H是葉子結點(即右孩子指針P=NULL),返回第三層遞歸.到這里H的左右子樹訪問完,退回到第二層遞歸.<再進入第三層遞歸>訪問以I為根結點的樹(D的右子樹),所以訪問到I<進入第四層遞歸>訪問I的左子樹,因為I是葉子結點(即左孩子指針P=NULL),返回第三層遞歸,<再進入第四層遞歸>訪問I的右子樹,因為I是葉子結點(即右孩子指針P=NULL),返回第三層遞歸.到這里I的左右子樹訪問完,退回到第二層遞歸.到這里D的左右子樹訪問完,退回到第一層遞歸.<再進入第二層遞歸>訪問以E為根結點的樹(B的右子樹),.所以訪問到E.這樣依次下去.......最後訪問到O

『捌』 建立二叉樹，並利用遞歸方法實現先序、中序、後序遍歷。

#include
#include
#include
#include
#include

using namespace std;

struct node;

typedef node *tree;

struct node{
char data;
tree lchild,rchild;
};

tree bt;

void build(tree &bt){
char ch;
ch=getchar();
if(ch!='.'){
bt=new node;
bt->data=ch;
build(bt->lchild);
build(bt->rchild);
}
else
bt=NULL;
}

void prework(){
ios::sync_with_stdio(false);
//freopen("data.in","r",stdin);
build(bt); //建樹
}

void preorder(tree bt){
if(bt){
cout<data;
preorder(bt->lchild);
preorder(bt->rchild);
}
}

void midorder(tree bt){
if(bt){
preorder(bt->lchild);
cout<data;
preorder(bt->rchild);
}
}

void backorder(tree bt){
if(bt){
preorder(bt->lchild);
cout<data;
preorder(bt->rchild);
}
}

void mainwork(){
preorder(bt);
cout<<endl;
midorder(bt);
cout<<endl;
backorder(bt);
}

int main(){
prework();
mainwork();
return 0;
}
//我這里輸入的東西是要求葉子節點的子節點為'.'
但仍無鈴聲，則送維修店維修。三無受話現象：

閱讀全文

與遍歷遞歸建立二叉樹python相關的資料

熱點內容
自己購買雲主伺服器推薦 瀏覽：422
個人所得稅java 瀏覽：761
多餘的伺服器滑道還有什麼用 瀏覽：192
pdf劈開合並 瀏覽：28
不能修改的pdf 瀏覽：752
同城公眾源碼 瀏覽：489
一個伺服器2個埠怎麼映射 瀏覽：298
java字元串ascii碼 瀏覽：79
台灣雲伺服器怎麼租伺服器 瀏覽：475
旅遊手機網站源碼 瀏覽：332
android關聯表 瀏覽：946
安卓導航無聲音怎麼維修 瀏覽：333
app怎麼裝視頻 瀏覽：431
安卓系統下的軟體怎麼移到桌面 瀏覽：96
windows拷貝到linux 瀏覽：772
mdr軟體解壓和別人不一樣 瀏覽：904
單片機串列通信有什麼好處 瀏覽：340
游戲開發程序員書籍 瀏覽：860
pdf中圖片修改 瀏覽：288
匯編編譯後 瀏覽：491
  • chifeng
  • we
  • might
  • finally
  • left
  • spot
  • fit
  • capture
  • scholar
  • expense
  • stream
  • gentleman
  • salary
  • buck
  • offense
  • angle
  • adjustment
  • prize
  • accounting
  • hopefully
  • web
  • momentum
  • jurisdiction
  • grandparent
  • charm
  • caller
  • prospective
  • separately
  • precedent
  • terminal
  • artery
  • sanctuary
  • homosexuality
  • alpha
  • incorrect
  • scattered
  • computerized
  • navigation
  • hefty
  • handicap
  • ranger
  • raspberry
  • horrific
  • inscribe
  • academically
  • asshole
  • ordinarily
  • incarnation
  • flinch
  • confidently
  • thematic
  • supremacy
  • stony
  • discontinue
  • teamwork
  • unruly
  • literate
  • mounted
  • scallop
  • whirlwind
  • dislocation
  • postmodernism
  • personalize
  • decentralized
  • hydrocarbon
  • gully
  • spire
  • forefinger
  • enlargement
  • artistry
  • cpu
  • vandalism
  • idealized
  • zap
  • fictitious
  • perfectionism
  • hypnosis
  • fortified
  • disobey
  • morbid
  • mirage
  • flashing
  • passover
  • topless
  • abreast
  • callous
  • dismayed
  • auditing
  • beau
  • exasperate
  • fell
  • sarcastically
  • alum
  • occupying
  • yuppie
  • vandal
  • earthen
  • sax
  • patter
  • dentistry