用C语言实现数据结构的一个算法 5C

用C语言实现递归法先序创建二叉树,用非递归法进行先序和层次遍历输出节点。希望各位IT精英可以加以详细注释

0

6个回答

#include // malloc()等
#include // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等
#include // atoi(),exit()
#include // 数学函数头文件,包括floor(),ceil(),abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果:构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件:二叉树T存在。操作结果:销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数。修改算法6.1
// 操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树:\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树:\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
网上很多的

1

#include

#include

#include

struct Node
{
void *data;
struct Node *next;
};

typedef struct Node Queue;

Queue* Enqueue(Queue **rear, void data, int *count)
{
Queue *node = (Queue
)malloc(sizeof(Queue));
node->data = data;
node->next = NULL;

if (*rear != NULL)
{
    (*rear)->next = node;
}

*rear = node;
(*count)++;
return node;

}

void Dequeue(Queue **head, int *count)
{
Queue *node = (*head);
(*head) = node->next;

free(node);
(*count)--;

}

typedef struct Node Stack;

void Push(Stack **top, void data, int *count)
{
Stack *node = (Stack
)malloc(sizeof(Stack));
node->data = data;
node->next = NULL;

node->next = *top;
*top = node;
(*count)++;

}

void Pop(Stack **top, int *count)
{
Stack *node = (*top);
(*top) = node->next;

free(node);
(*count)--;

}

struct TreeNode
{
int data;
struct TreeNode* left;
struct TreeNode* right;
};

struct TreeNode* CreateNode(int data)
{
struct TreeNode node = (struct TreeNode)malloc(sizeof(struct TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

void CreateTree(struct TreeNode** root)
{
int data;
scanf("%d", &data);
if (data == 0)
return;

struct TreeNode* node = CreateNode(data);

printf("添加数据 %d\n", data);
(*root) = node;

printf("添加左节点:");
CreateTree(&((*root)->left));
printf("添加右节点:");
CreateTree(&((*root)->right));

}

void FirstOrderPrintTree(struct TreeNode* root)
{
Stack *top = NULL;
int count = 0;

Push(&top, root, &count);

while (top)
{
    struct TreeNode* node = (struct TreeNode*)top->data;
    printf("%d\n", node->data);

    Pop(&top, &count);
    if (node->right)
        Push(&top, node->right, &count);
    if (node->left)
        Push(&top, node->left, &count);
}

}

void LevelPrintTree(struct TreeNode* root)
{
Queue *head = NULL, *rear = NULL;
int count = 0;

Enqueue(&rear, root, &count);
head = rear;

while (count != 0)
{
    struct TreeNode* node = (struct TreeNode*)head->data;
    printf("%d \n", node->data);
    if (node->left)
        Enqueue(&rear, node->left, &count);
    if (node->right)
        Enqueue(&rear, node->right, &count);

    Dequeue(&head, &count);
}

}

void main()
{
struct TreeNode* root = NULL;
CreateTree(&root);

FirstOrderPrintTree(root);
LevelPrintTree(root);

system("pause");

}

哪里需要注释再说

0

非递归需要借助一个堆栈,这里有个例子代码,包括了堆栈的实现和使用它非递归遍历树

http://blog.csdn.net/fisherwan/article/details/21455287

0

#include
#include
#define MAXSIZE 255

typedef struct BiNode
{
char data;
struct BiNode *lchild;
struct BiNode *rchild;
}BiTree;

BiTree *CreateBitreepre(char *str)
{
BiTree *bt,*stack[MAXSIZE],*p=NULL;
int top=-1,k,j=0;
char ch;

bt=NULL;
ch=str[j];

while(ch!='\0')
{
    switch(ch)
    {
    case '(':
        top++;
        stack[top]=p;
        k=1;
        break;
    case ')':
        top--;
        break;
    case ',':
        k=2;
        break;
    default:
        {
            p=(BiTree *)malloc(sizeof(BiTree));
            p->data=ch;
            p->lchild=p->rchild=NULL;

            if(bt==NULL)
                bt=p;
            else
            {
                switch(k)
                {
                case 1:
                    stack[top]->lchild=p;
                    break;
                case 2:
                    stack[top]->rchild=p;
                    break;
                }
            }
        }
    }
j++;
ch=str[j];
}
return bt;

}

void OutBiTree(BiTree *bt)
{
BiTree *stack[MAXSIZE],*p;
int level[MAXSIZE][2],top,n,i,width=4;
char type;

if(bt!=NULL)
{
    top=1;
    stack[top]=bt;
    level[top][0]=width;
    level[top][1]=2;

    while(top>0)
    {
        p=stack[top];
        n=level[top][0];

        switch(level[top][1])
        {
        case 0:
            type='0';
            break;
        case 1:
            type='1';
            break;
        case 2:
            type='2';
            break;
        }

        for(i=1;i<=n;i++)
            printf(" ");
        printf("%c(%c)\n",p->data,type);

        for(i=n+1;i<=1;i+=2)
            printf("——");

        top--;
        if(p->rchild!=NULL)
        {
            top++;
            stack[top]=p->rchild;
            level[top][0]=n+width;
            level[top][1]=1;
        }

        if(p->rchild!=NULL)
        {
            top++;
            stack[top]=p->lchild;
            level[top][0]=n+width;
            level[top][1]=0;
        }
    }
}

}

void main()
{
BiTree * bt;
char *gyb,str[MAXSIZE];
int j=1;

printf("\n--------------------------------------");
printf("\n  1将按照输入的二叉树广义表表示字符串    ");
printf("\n      生成对应的二叉树链式结构        ");
printf("\n  2输出二叉树的凹入法表示形式            ");
printf("\n      r——跟  0——左孩子    1——右孩子    ");
printf("\n--------------------------------------");
printf("\n请输入二叉树的广义表形式:\n");
gyb=str;
scanf("%s",&str);
bt=CreateBitreepre(gyb);
printf("此二叉树建立成功!\n");
printf("次二叉树凹入法表示为:\n");
OutBiTree(bt);

}

0

/*
二叉树的操作( 用递归和非递归的方法都要)
任务:
要求能够输入树的各个结点,创建二叉树,并能够输出用不同方法遍历的遍历序列;
分别建立建立二叉树存储结构的的输入函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数;
*/

#include
using namespace std;

typedef char datatype;
typedef struct node
{
datatype data;
struct node *lchild, *rchild;
}bintnode;
typedef bintnode *bintree;
bintree root;

typedef struct stack
{
bintree data[100];
int tag[100];
int top;
}seqstack;
//入栈
void push(seqstack *s, bintree t)
{
s->data[s->top] = t;
s->top++;
}
//出栈
bintree pop(seqstack *s)
{
if (s->top != 0)
{
s->top--;
return (s->data[s->top]);
}
else
return NULL;
}

//create bintree 按照前序遍历创建二叉树
bintree createbintree()
{
char ch;
bintree t;
if ((ch = getchar()) == '#')
t = NULL;
else
{
t = (bintnode*)malloc(sizeof(bintnode)); //t=new bintnode;
t->data = ch;
t->lchild = createbintree();
t->rchild = createbintree();
}
return t;
}

//前序遍历 递归
void preorder(bintree t)
{
if (t)
{
cout << t->data;
preorder(t->lchild);
preorder(t->rchild);
}
}

//中序遍历 递归
void inorder(bintree t)
{
if (t)
{
inorder(t->lchild);
cout << t->data;
inorder(t->rchild);
}
}

//后序遍历 递归
void postorder(bintree t)
{
if (t)
{
postorder(t->lchild);
postorder(t->rchild);
cout << t->data;
}
}

//非递归先序遍历
void preorder1(bintree t)
{
seqstack s;
s.top = 0;
while ((t) || (s.top != 0)) //当前处理子树不为空或栈不为空则循环
{
if (t)
{
cout << t->data;
push(&s, t);
t = t->lchild;
}
else
{
t = pop(&s);
t = t->rchild;
}
}
}

//非递归中序遍历
void inorder1(bintree t)
{
seqstack s;
s.top = 0;
while ((t) || (s.top != 0))
{
if (t)
{
push(&s, t); //如果子树存在时,将左子树进栈
t = t->lchild;
}
else
{
t = pop(&s); //左子树为空时,出栈
cout << t->data;
t = t->rchild; //访问右子树
}
}
}
//非递归后序遍历
void postorder1(bintree t)
{
seqstack s;
s.top = 0;
while ((t) || (s.top != 0))
{
if (t)
{
s.data[s.top] = t; //首先进入左子树访问,根节点和右子树尚未访问,将T保存起来放入栈中
s.tag[s.top] = 0; //每个元素刚进栈时,将tag值设为0
s.top++;
t = t->lchild;
}
else
if (s.tag[s.top - 1] == 1)
{
s.top--;
t = s.data[s.top];
cout << t->data;
t = NULL;
}
else
{
t = s.data[s.top - 1];
s.tag[s.top - 1] = 1;
t = t->rchild;
}
}
}

int main()
{
cout<<"请以前序遍历的方法创建二叉树,以#结束(如A##)"<<endl;
root = createbintree();
cout << "前序遍历(递归):";
preorder(root);
cout << endl;
cout << "前序遍历(非递归):";
preorder1(root);
cout << endl;
cout << "中序遍历(递归):";
inorder(root);
cout << endl;
cout << "中序遍历(非递归):";
inorder1(root);
cout << endl;
cout << "后序遍历(递归):";
postorder(root);
cout << endl;
cout << "前序遍历(非递归):";
postorder1(root);
cout << endl;
return 0;
}

0

我博客刚好写过这篇文章,望采纳

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!