遍历递归建立二叉树python

‘壹’ 关于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;
}
//我这里输入的东西是要求叶子节点的子节点为'.'
但仍无铃声，则送维修店维修。三无受话现象：