求样板：二叉树建立，显示出创建的结果，先序遍历，并显示遍历的结果。在线等！
数据结构的初学者，请有经验兄弟指点一把，实在想不明白了…………
谢谢！
[解决办法]
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct btnode
{
char data;
struct btnode *lchild,*rchild;
}btnode,*BiTree;
BiTree PreCreateBiTree(BiTree &root) /*构造二叉链表表示的二叉树T,按先序次序输入二叉树中结点的值（一个字符),?字符表示空树*/
{
char ch;
printf ( "please enter the BiTree in the preorder: ");
fflush(stdin);
scanf( "%c ",&ch);
if (ch== '? ')
{
root=NULL;
return (root);
}
else
{
root=(BiTree)malloc(sizeof(btnode));
root-> data=ch;
PreCreateBiTree(root-> lchild);
PreCreateBiTree(root-> rchild);
return (root);
}
}
void preorder(BiTree root) /*先序遍历二叉树*/
{
if (root!=NULL)
{
printf ( "%c ",root-> data);
preorder(root-> lchild);
preorder(root-> rchild);
}
}
void inorder(BiTree root) /*中序遍历的递归算法*/
{
if (root!=NULL)
{
inorder (root-> lchild);
printf ( "%c ",root-> data);
inorder (root-> rchild);
}
}
void postorder(BiTree root) /*后序遍历递归算法*/
{
if (root!=NULL)
{
postorder (root-> lchild);
postorder (root-> rchild);
printf ( "%c ",root-> data);
}
}
void levelorder(BiTree root) /*层次遍历二叉树的非递归算法*/
{
BiTree queue[MAXSIZE];
BiTree p=root;
int front=0,rear=0;
if (p!=NULL)
{
queue [++rear]=p;
while (front <rear)
{
p=queue[++front];
printf ( "%c ",p-> data);
if (p-> lchild!=NULL)
queue[++rear]=p-> lchild;
if (p-> rchild!=NULL)
queue[++rear]=p-> rchild;
}
}
}
int search_depth(BiTree root) /* 求二叉树的深度*/
{
BiTree queue[MAXSIZE];
BiTree p;
int front=0,rear=0,depth=0,level;
if (root!=NULL)
{
queue[++rear]=root;
level=rear;
while (front <rear)
{
p=queue[++front];
if (p-> lchild!=NULL)
queue[++rear]=p-> lchild;
if (p-> rchild!=NULL)
queue[++rear]=p-> rchild;
if (front==level)
{
depth++;
level=rear;
}
}
}
return (depth);
}
int search_nodenum(BiTree root) /*求二叉树结点数目*/
{
int num=0,top;
BiTree stack[MAXSIZE];
BiTree p;
if (root!=NULL)
{
top=1;
stack[top]=root;
while (top> 0)
{
p=stack[top--];
num++;
if (p-> rchild!=NULL)
stack[++top]=p-> rchild;
if (p-> lchild!=NULL)
stack[++top]=p-> rchild;
}
}
return (num);
}
int search_leaves(BiTree root) /*求二叉树叶子结点数目*/
{
int num=0;
BiTree queue[MAXSIZE];
BiTree p=root;
int front=0,rear=0;
if (p!=NULL)
{
queue [++rear]=p;
while (front <rear)
{
p=queue[++front];
if (p-> lchild==NULL&&p-> rchild==NULL)
num++;
if (p-> lchild!=NULL)
queue[++rear]=p-> lchild;
if (p-> rchild!=NULL)
queue [++rear]=p-> rchild;
}
}
return (num);
}
void main ()
{
int choice,depth,nodenumber,leavesnum;
BiTree root=(BiTree)malloc(sizeof(btnode));
root-> lchild=root-> rchild=0;
printf ( "0 Exit\n ");
printf ( "1 Pre Create a BiTree\n ");
printf ( "2 Printf the preorder\n ");
printf ( "3 Printf the inorder\n ");
printf ( "4 Printf the postorder\n ");
printf ( "5 Printf the levelorder\n ");
printf ( "6 Search for the depth\n ");
printf ( "7 Search for the nodenum\n ");
printf ( "8 Search for the leaves\n ");
printf ( "please choice: ");
scanf( "%d ",&choice);
while (choice!=0)
{
switch (choice)
{
case 0:
case 1:
PreCreateBiTree(root);
break;
case 2:
printf ( "the BiTree in the preorder is: \n ");
preorder(root);
printf( "\n ");
break;
case 3:
printf ( "the BiTree in the midorder is: \n ");
inorder(root);
printf( "\n ");
break;
case 4:
printf ( "the BiTree in the postorder is: \n ");
postorder(root);
printf( "\n ");
break;
case 5:
printf ( "the BiTree in the levelorder is: \n ");
levelorder(root);
printf( "\n ");
break;
case 6:
depth=search_depth(root);
printf ( "the depth of the BiTree is:%d\n ",depth);
break;
case 7:
nodenumber=search_nodenum(root);
printf ( "the nodenumber of the BiTree is:%d\n ",nodenumber);
break;
case 8:
leavesnum=search_leaves(root);
printf ( "the leavesnum of the BiTree is:%d\n ",leavesnum);
break;
}
printf ( "please choice: ");
scanf( "%d ",&choice);
}
getchar();
}
[解决办法]
这样很浪费资源阿
[解决办法]
#include <iostream>
using namespace std;
#define MaxSize 100
typedef struct bnode
{
char data;
bnode *lchild, *rchild;
}BTNode;
int
main(void)
{
void CreateBTNode(BTNode *&root, const char *str);
void PerOrder(BTNode *&root);
void InOrder(BTNode *&root);
void PostOrder(BTNode *&root);
void DispBTNode(BTNode *&root);
BTNode *root;
const char *str = "1(2, 3(4, 5)) ";
CreateBTNode(root, str);
cout < <endl;
cout < < "after CreateBTNode(root), root is : " < <endl;
DispBTNode(root);
cout < <endl;
cout < < "the result of PerOrder(root) is : " < <endl;
PerOrder(root);
cout < <endl;
cout < < "the result of InOrder(root) is : " < <endl;
InOrder(root);
cout < <endl;
cout < < "the result of PostOrder(root) is : " < <endl;
PostOrder(root);
cout < <endl;
return 0;
}
void PerOrder(BTNode *&root)
{
if (root != NULL)
{
cout < <root-> data;
PerOrder(root-> lchild);
PerOrder(root-> rchild);
}
}
void InOrder(BTNode *&root)
{
if (root != NULL)
{
InOrder(root-> lchild);
cout < <root-> data;
InOrder(root-> rchild);
}
}
void PostOrder(BTNode *&root)
{
if (root != NULL)
{
PostOrder(root-> lchild);
PostOrder(root-> rchild);
cout < <root-> data;
}
}
void DispBTNode(BTNode *&root)
{
if (root != NULL)
{
cout < <root-> data;
if (root-> lchild != NULL && root-> rchild != NULL)
{
cout < < "( ";
DispBTNode(root-> lchild);
if (root-> rchild != NULL)
cout < < ", ";
DispBTNode(root-> rchild);
cout < < ") ";
}
}
}
void CreateBTNode(BTNode *&root, const char *str)
{
int i = 0, top = -1, k;
char ch;
BTNode *st[MaxSize], *node = NULL;
root = NULL;
ch = str[i];
while (ch != '\0 ')
{
switch (ch)
{
case '( ' : top++; st[top] = node; k = 1; break;
case ', ' : k =2; break;
case ' ' : break;
case ') ' : top--; break;
default : node = new BTNode;
node-> data = ch;
node-> lchild = node-> rchild = NULL;
if (root == NULL)
root = node;
else
switch (k)
{
case 1 : st[top]-> lchild = node; break;
case 2 : st[top]-> rchild = node; break;
}
}
i++;
ch = str[i];
}
}
[解决办法]
#include <iostream>
using namespace std;
#define MaxSize 100
typedef struct bnode
{
char data;
bnode *lchild, *rchild;
}BTNode;
int
main(void)
{
void CreateBTNode(BTNode *&root, const char *str);
void PerOrder(BTNode *&root);
void InOrder(BTNode *&root);
void PostOrder(BTNode *&root);
void DispBTNode(BTNode *&root);
BTNode *root;
const char *str = "1(2, 3(4, 5)) ";
CreateBTNode(root, str);
cout < <endl;
cout < < "after CreateBTNode(root), root is : " < <endl;
DispBTNode(root);
cout < <endl;
cout < < "the result of PerOrder(root) is : " < <endl;
PerOrder(root);
cout < <endl;
cout < < "the result of InOrder(root) is : " < <endl;
InOrder(root);
cout < <endl;
cout < < "the result of PostOrder(root) is : " < <endl;
PostOrder(root);
cout < <endl;
return 0;
}
void PerOrder(BTNode *&root)
{
if (root != NULL)
{
cout < <root-> data;
PerOrder(root-> lchild);
PerOrder(root-> rchild);
}
}
void InOrder(BTNode *&root)
{
if (root != NULL)
{
InOrder(root-> lchild);
cout < <root-> data;
InOrder(root-> rchild);
}
}
void PostOrder(BTNode *&root)
{
if (root != NULL)
{
PostOrder(root-> lchild);
PostOrder(root-> rchild);
cout < <root-> data;
}
}
void DispBTNode(BTNode *&root)
{
if (root != NULL)
{
cout < <root-> data;
if (root-> lchild != NULL && root-> rchild != NULL)
{
cout < < "( ";
DispBTNode(root-> lchild);
if (root-> rchild != NULL)
cout < < ", ";
DispBTNode(root-> rchild);
cout < < ") ";
}
}
}
void CreateBTNode(BTNode *&root, const char *str)
{
int i = 0, top = -1, k;
char ch;
BTNode *st[MaxSize], *node = NULL;
root = NULL;
ch = str[i];
while (ch != '\0 ')
{
switch (ch)
{
case '( ' : top++; st[top] = node; k = 1; break;
case ', ' : k =2; break;
case ' ' : break;
case ') ' : top--; break;
default : node = new BTNode;
node-> data = ch;
node-> lchild = node-> rchild = NULL;
if (root == NULL)
root = node;
else
switch (k)
{
case 1 : st[top]-> lchild = node; break;
case 2 : st[top]-> rchild = node; break;
}
}
i++;
ch = str[i];
}
}
