求二叉树前序遍历程序（C或C++)

#include "stdioh"

#include "stdlibh"

struct node{

int lc,rc;

}tree[1000];

void print(int root){

printf("%d ",root);

if(tree[root]lc!=-1)print(tree[root]lc);

if(tree[root]rc!=-1)print(tree[root]rc);

};

int main(){

int nop,n,root,i,t1,t2,t3;

scanf("%d",&nop);

while(nop!=0){

scanf("%d",&n);

scanf("%d",&root);

for(i=0;i<=n;i++){

tree[i]lc=-1;tree[i]rc=-1;

};

for(i=1;i<=n-1;i++){

scanf("%d",&t1);

scanf("%d",&t2);

scanf("%d",&t3);

if(t3==0)tree[t1]lc=t2;

else tree[t1]rc=t2;

};

print(root);

printf("\n");

nop--;

};

return 0;

};

其实这个程序很简单的。 代码如下：

#include<malloch>

#define MAX_TREE_SIZE  100

typedef struct {

int i;

}TElemType;

typedef struct BiTNode{

char data;

struct BiTNode lchild,rchild;

}BiTNode,BiTree;

int CreateBiTree(BiTree &T)

{

char ch;

scanf("%c",&ch);

getchar();

if(ch==' '||ch=='\n')

{

 T=NULL;

}

else{

 T=(BiTNode )malloc(sizeof(BiTNode));

 T->data=ch;

 CreateBiTree(T->lchild);

 CreateBiTree(T->rchild);

}

return 1;

}//CreateBiTree()

int Visit(char ch)

{

printf("%c",ch);

return 1;

}

int PreOrderTraverse(BiTree T,int ( Visit)(char ch))

{

if(T)

{

 if(Visit(T->data))

  if(PreOrderTraverse(T->lchild,Visit))

   if(PreOrderTraverse(T->rchild,Visit)) return 1;

}else return 1;

}

int InOrderTraverse(BiTree T,int ( Visit)(char ch))

{

if(T)

{

  if(InOrderTraverse(T->lchild,Visit))

   if(Visit(T->data))

    if(InOrderTraverse(T->rchild,Visit)) return 1;

}else return 1;

}

int PostOrderTraverse(BiTree T,int( Visit)(char ch))

{

if(T)

{

 if(PostOrderTraverse(T->lchild,Visit))

  if(PostOrderTraverse(T->rchild,Visit))

   if(Visit(T->data))  return 1;

}else return 1;

}

void  main()

{

BiTree  T;

printf("从根节点输入二叉树,存储方式采用中序遍历，无分支请输入空格：\n");

CreateBiTree(T);

printf("先序遍历为：");

PreOrderTraverse(T,Visit);

printf("\n");

printf("中序遍历为：");

InOrderTraverse(T,Visit);

printf("\n");

printf("后序遍历为：");

PostOrderTraverse(T,Visit);

}

以下代码参考：

Status

PreOrderTraverse(BiTree

T)

{

//先序遍历二叉树T的递归算法

if

(T)

{

printf("%d

",T->data);

if(T->lchild)

PreOrderTraverse(T->lchild);

if(T->rchild)

PreOrderTraverse(T->rchild);

return

FALSE;

}

else

return

OK;

}

Status

PreOrder(BiTree

T)

{

//先序遍历二叉树T的非递归算法

while(!(T==NULL&&top==NULL))

{

if(T)

{

printf("%d

",T->data);

push(T);

T=T->lchild;

}

else

{

T=(BiTree)pop();

T=T->rchild;

}

}

}

Status

InOrderTraverse(BiTree

T)

{

//中序遍历二叉树T的递归算法

if

(T)

{

if

(T->lchild)

InOrderTraverse(T->lchild);

printf("%d

",T->data);

if

(T->rchild)

InOrderTraverse(T->rchild);

return

FALSE;

}

else

return

OK;

}

Status

InOrder(BiTree

T)

{

//中序遍历二叉树T的非递归算法

while(!(T==NULL&&top==NULL))

{

while(T)

{

push(T);

T=T->lchild;

}

T=(BiTree)pop();

printf("%d

",T->data);

T=T->rchild;

}

}

Status

PostOrderTraverse(BiTree

T)

{

//后序遍历二叉树T的递归算法

if

(T)

{

if

(T->lchild)

PostOrderTraverse(T->lchild);

if

(T->rchild)

PostOrderTraverse(T->rchild);

printf("%d

",T->data);

return

FALSE;

}

else

return

OK;

}

Status

PostOrder(BiTree

T)

{

//后序遍历二叉树T的递归算法

unsigned

sign;//记录结点从栈中d出的次数

while(!(T==NULL&&top==NULL))

{

if(T)

{

push(T);//第一次遇到结点T时压入其指针

push(1);//置标志为1

T=T->lchild;

}

else

{

while(top)

{

sign=pop();

T=(BiTree)pop();

if(1==sign)//表示走过T的左子树

{

push(T);

push(2);

T=T->rchild;

break;

}

else

{

if(2==sign)//表示T的左右子树都已走过

{

printf("%d

",T->data);

T=NULL;

}

}

}

}

}

}

你的程序有诸多问题，你的程序运行时候应该也会报错的吧？

这个写法不是很通用，不过我还是按照你的源码修改成了你想要的结果。

结构上基本一致，可实现基本已经面目全非了。

我用字符串代替了手工输入，你要是喜欢手工输入，你可以把我那个注释掉，用你自己的……

以下是修改后可用的代码：

import javautil;

class Node {

Node left;

Node Right;

char data;// 节点数据

void print() {

Systemoutprintln(data + "");

}

public Node() {

thisleft = null;

thisRight = null;

}

public Node(char data) {

thisleft = null;

thisRight = null;

thisdata = data;

}

}

class BTree {

static Node root = new Node();// 为根节点分配空间

static char ch[];// 输入的字符串

static int i = 0;

static Node CreateTree()// 先序建立二叉树

{

Node node = null;

if (ch[i] == '#') {

node = null;

i++;

}else {

node = new Node();

nodedata = ch[i];

i++;

nodeleft = CreateTree();

nodeRight = CreateTree();

}

return node;

}

static public void preorder(Node node)// 先序遍历二叉树

{

if (node != null) {

nodeprint();

preorder(nodeleft);

preorder(nodeRight);

} else {

Systemoutprintln("Tree node is empty");

}

}

}

public class Tree {

public static void main(String args[]) {

Scanner reader = new Scanner(Systemin);

BTreech = new char[16];

BTreech[0] = 'a';

// 读取输入字符数组，以结尾

BTreech = "ABC##DE#G##F###"toCharArray();

//for (int i = 0; (BTreech[i] = readernext()charAt(0)) != ''; i++){}

BTreeroot = BTreeCreateTree();

BTreepreorder(BTreeroot);

}

}

#include <stdioh>

#include <iostream>

#include <queue>

#include <stack>

#include <malloch>

#define SIZE 100

using namespace std;

typedef struct BiTNode //定义二叉树节点结构

{

char data; //数据域

struct BiTNode lchild,rchild; //左右孩子指针域

}BiTNode,BiTree;

int visit(BiTree t);

void CreateBiTree(BiTree &T); //生成一个二叉树

void PreOrder(BiTree); //递归先序遍历二叉树

void InOrder(BiTree); //递归中序遍历二叉树

void PostOrder(BiTree); //递归后序遍历二叉树

void InOrderTraverse(BiTree T); //非递归中序遍历二叉树

void PreOrder_Nonrecursive(BiTree T);//非递归先序遍历二叉树

void LeverTraverse(BiTree T);//非递归层序遍历二叉树

//主函数

void main()

{

BiTree T;

char j;

int flag=1;

//---------------------程序解说-----------------------

printf("本程序实现二叉树的 *** 作。\n");

printf("叶子结点以空格表示。\n");

printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等 *** 作。\n");

//----------------------------------------------------

printf("\n");

printf("请建立二叉树。\n");

printf("建树将以三个空格后回车结束。\n");

printf("例如:1 2 3 4 5 6 (回车)\n"); CreateBiTree(T); //初始化队列

getchar();

while(flag)

{

printf("\n");

printf("请选择: \n");

printf("1递归先序遍历\n");

printf("2递归中序遍历\n");

printf("3递归后序遍历\n");

printf("4非递归中序遍历\n");

printf("5非递归先序遍历\n");

printf("6非递归层序遍历\n");

printf("0退出程序\n");

scanf(" %c",&j);

switch(j)

{

case '1':if(T)

{

printf("递归先序遍历二叉树:");

PreOrder(T);

printf("\n");

}

else printf("二叉树为空!\n");

break;

case '2':if(T)

{

printf("递归中序遍历二叉树:");

InOrder(T);

printf("\n");

}

else printf("二叉树为空!\n");

break;

case '3':if(T)

{

printf("递归后序遍历二叉树:");

PostOrder(T);

printf("\n");

}

else printf("二叉树为空!\n");

break;

case '4':if(T)

{

printf("非递归中序遍历二叉树:");

InOrderTraverse(T);

printf("\n");

}

else printf("二叉树为空!\n");

break;

case '5':if(T)

{

printf("非递归先序遍历二叉树:");

PreOrder_Nonrecursive(T);

printf("\n");

}

else printf("二叉树为空!\n");

break;

case '6':if(T)

{

printf("非递归层序遍历二叉树:");

LeverTraverse(T);

printf("\n");

}

else printf("二叉树为空!\n");

break;

default:flag=0;printf("程序运行结束，按任意键退出!\n");

}

}

}

//建立二叉树

void CreateBiTree(BiTree &T)

{

char ch;

scanf("%c",&ch); //读入一个字符

if(ch==' ') T=NULL;

else

{

T=(BiTNode )malloc(sizeof(BiTNode)); //生成一个新结点

T->data=ch;

CreateBiTree(T->lchild); //生成左子树

CreateBiTree(T->rchild); //生成右子树

}

}

//先序遍历的递归

void PreOrder(BiTree T)

{

if(T)

{

printf("%c ",T->data); //访问结点

PreOrder(T->lchild); //遍历左子树

PreOrder(T->rchild); //遍历右子树

}

}

//中序遍历的递归

void InOrder(BiTree T)

{

if(T)

{

InOrder(T->lchild); //遍历左子树

printf("%c ",T->data); //访问结点

InOrder(T->rchild); //遍历右子树

}

}

//后序遍历的递归

void PostOrder(BiTree T)

{

if(T)

{

PostOrder(T->lchild); //遍历左子树

PostOrder(T->rchild); //访问结点

printf("%c ",T->data); //遍历右子树

}

}

//非递归中序遍历

void InOrderTraverse(BiTree T)

{

stack<BiTree> S;

BiTree p;

Spush(T);//跟指针进栈

while(!Sempty())

{

p=new BiTNode;

while((p=Stop())&&p)

Spush(p->lchild);//向左走到尽头

Spop(); //空指针退栈

if(!Sempty())

{

p=Stop();

Spop();

cout<<p->data<<" ";

Spush(p->rchild);

}

}

}

//先序遍历的非递归

void PreOrder_Nonrecursive(BiTree T)

{

stack<BiTree> S;

BiTree p;

Spush(T);//根指针进栈

while(!Sempty())//栈空时结束

{

while((p=Stop())&&p)

{

cout<<p->data<<" ";

Spush(p->lchild);

}//向左走到尽头

Spop();//d出堆栈

if(!Sempty())

{

p=Stop();

Spop();

Spush(p->rchild);//向右走一步

}

}

}

void LeverTraverse(BiTree T)

{//非递归层次遍历

queue <BiTree> Q;

BiTree p;

p = T;

if(visit(p)==1)

Qpush(p);

while(!Qempty())

{

p = Qfront();

Qpop();

if(visit(p->lchild) == 1)

Qpush(p->lchild);

if(visit(p->rchild) == 1)

Qpush(p->rchild);

}

}

int visit(BiTree T)

{

if(T)

{

printf("%c ",T->data);

return 1;

}

else

return 0;

}

你的算法没啥大问题，毕竟是教材上的嘛。但咱就是说，你是不是当成单链表来输入了。。。要根据二叉树的结构来啊。

输入二叉树不像输入单链表那样输完加上一个终止符' '（空格）就行，而可能需要多个终止符，因为树有多个结尾处。这说得可能比较抽象，下面以你连续输入a，b，c为例。首先根据你的代码，输入方式类似前序遍历，那么系统会将b写为a的左孩子、c写为b的左孩子，接下来的一个' '仅表示c的左子树为空，而不代表整棵树结束（你以为结束了）——接下来来到c的右子树，需要第二个' '表明c的右子树为空，其次还有b的右子树、a的右子树需要' '来结束。（所以总计需要四个' '，才能结束输入）

void browseByFirst(char Tree[], int len)

{

for(int i = 0; i < len; i++) //由于是先序顺序存储因此直接输出即可

printf("%c ",Tree[i]);

}

void browseByMiddle(char Tree[], int len, int cur)

{

if ((cur 2 + 1) < len)

{

browseByMiddle(Tree,len,cur 2 + 1);

}

printf("%c ",Tree[cur]);

if ((cur 2 + 2) < len)

{

browseByMiddle(Tree,len,cur 2 + 2);

}

}

void browseByLast(char Tree[], int len, int cur)

{

if ((cur 2 + 1) < len)

{

browseByLast(Tree,len,cur 2 + 1);

}

if ((cur 2 + 2) < len)

{

browseByLast(Tree,len,cur 2 + 2);

}

printf("%c ",Tree[cur]);

}

void main()

{

char Tree[] = {'A','B','J','F','C','M'};

browseByFirst(Tree,6); //先序

printf("\n");

browseByMiddle(Tree,6,0);//中序

printf("\n");

browseByLast(Tree,6,0);//后序

printf("\n");

}

以上就是关于求二叉树前序遍历程序（C或C++)全部的内容，包括:求二叉树前序遍历程序（C或C++)、怎样建立一个二叉树实现二叉树的先序中序后序和遍历、数据结构先序构建一棵二叉树，中序非递归遍历二叉树的程序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！