欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

详细了解C语言二叉树的建立与遍历

程序员文章站 2022-03-24 08:20:46
目录这里给一个样例树:代码:#include #include #include /* 二叉树的二...

这里给一个样例树:

详细了解C语言二叉树的建立与遍历

代码:

#include <stdio.h> 
#include <string.h>
#include <stdlib.h>
/*    二叉树的二叉链表结点结构定义     */
typedef struct bitnode
{
    char data;
    struct bitnode *lchild,*rchild;
}bitnode,*bitree;
bitree t=null;
/*    先序遍历建立一个二叉树    */
void create (bitree *t)       //    二级指针改变地址的地址
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *t=null;
    else
    {
        *t=(bitree)malloc(sizeof(bitnode));
        if(!*t)
            return ;
        else
        {
            (*t)->data=ch;
            create(&(*t)->lchild);
            create(&(*t)->rchild);
        }
    }
}
/*    二叉树的前序递归遍历算法    */
void preordertraverse(bitree t)
{
    if(t==null)
        return ;
    printf("%c ",t->data);
    preordertraverse(t->lchild);
    preordertraverse(t->rchild);
}
/*    二叉树的中序递归遍历算法    */
void inordertraverse(bitree t)
{
    if(t==null)
        return ;
    inordertraverse(t->lchild);
    printf("%c ",t->data);
    inordertraverse(t->rchild);
}
/*    二叉树的后序递归遍历算法    */
void postordertraverse(bitree t)
{
    if(t==null)
        return ;
    postordertraverse(t->lchild);
    postordertraverse(t->rchild);
    printf("%c ",t->data);
}
int main()
{
    printf("请按先序遍历的结果输入树,例如:abdh#k###e##cfi###g#j##\n");
    create(&t);
    printf("先序遍历的结果为:\n");
    preordertraverse(t);
    printf("\n");
    printf("中序遍历的结果为:\n");
    inordertraverse(t);
    printf("\n");
    printf("后序遍历的结果为:\n");
    postordertraverse(t);
    printf("\n");
    return 0;
}

输出结果如下

详细了解C语言二叉树的建立与遍历

ps:下面是一个用c++里面的取引用代替了二级指针

#include<bits/stdc++.h>
using namespace std;
/*    二叉树的二叉链表结点结构定义     */
typedef struct bitnode
{
    char data;
    struct bitnode *lchild,*rchild;
}bitnode,*bitree;
bitree t=null;
/*    先序遍历建立一个二叉树    */
void create (bitree &t)        //    c++取引用
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        t=null;
    else
    {
        t=(bitree)malloc(sizeof(bitnode));
        if(!t)
            return ;
        else
        {
            t->data=ch;
            create(t->lchild);
            create(t->rchild);
        }
    }
}
/*    二叉树的前序递归遍历算法    */
void preordertraverse(bitree t)
{
    if(t==null)
        return ;
    printf("%c ",t->data);
    preordertraverse(t->lchild);
    preordertraverse(t->rchild);
}
/*    二叉树的中序递归遍历算法    */
void inordertraverse(bitree t)
{
    if(t==null)
        return ;
    inordertraverse(t->lchild);
    printf("%c ",t->data);
    inordertraverse(t->rchild);
}
/*    二叉树的后序递归遍历算法    */
void postordertraverse(bitree t)
{
    if(t==null)
        return ;
    postordertraverse(t->lchild);
    postordertraverse(t->rchild);
    printf("%c ",t->data);
}
int main()
{
    printf("请按先序遍历的结果输入树,例如:abdh#k###e##cfi###g#j##\n");
    create(t);
    printf("先序遍历的结果为:\n");
    preordertraverse(t);
    printf("\n");
    printf("中序遍历的结果为:\n");
    inordertraverse(t);
    printf("\n");
    printf("后序遍历的结果为:\n");
    postordertraverse(t);
    printf("\n");
    return 0;
}

ps:遍历的plus版,想要的自取。

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int cmax=1e2+5;
typedef struct bitnode 
{
	char data;
	struct bitnode *lchild ,*rchild;
}bitnode,*bitree;
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);
	}
	return ; 
}
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;
	s.push(t);
	while(!s.empty())
	{
		p=new bitnode;
		while((p=s.top())&&p)
		    s.push(p->lchild);
		s.pop();
		if(!s.empty())
		{
			p=s.top();
			s.pop();
			cout<<p->data<<"  ";
			s.push(p->rchild); 
		 } 
	 } 
}
//    先序非递归遍历
void preorder_nonrecursive(bitree t)
{
	stack<bitree> s;
	bitree p;
	s.push(t);
	while(!s.empty())
	{
		while((p=s.top())&&p)
		{
			cout<<p->data<<"  ";
			s.push(p->lchild); 
		 } 
		s.pop();
		if(!s.empty())
		{
			p=s.top();
			s.pop();
			s.push(p->rchild);
		 } 
	}
 } 
 int visit(bitree t)
 {
 	if(t)
 	{
 		printf("%c ",t->data);
 		return 1;
	 }
	else
	return 0;
 }
 //    非递归层次遍历
 void  levertraverse(bitree t)
 {
 	queue <bitree> q;
 	bitree p;
 	p=t;
 	if(visit(p)==1)
 	    q.push(p);
 	while(!q.empty())
 	{
 		p=q.front();
 		q.pop();
 		if(visit(p->lchild)==1)
 		    q.push(p->lchild);
 		if(visit(p->rchild)==1)
 		    q.push(p->rchild);
	 }
 }
//主函数
int main()
{
	bitree t;
	char j;
	int flag=1;
	printf("本程序实现二叉树的操作。\n");
    printf("叶子结点以#表示。\n");
    printf("可以进行建立二叉树,递归先序、中序、后序遍历,非递归先序、中序遍历及非递归层序遍历等操作。\n");
    printf("请建立二叉树。\n");
    printf("建树将以三个空格后回车结束。\n");
    printf("例如:1 2 3 4 5 6       (回车)\n\n");
	createbitree(t);           //初始化队列
    getchar();
    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");
    while(flag)
    {
        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");
        }
    }
}

详细了解C语言二叉树的建立与遍历

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注的更多内容!