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

2024-10-01 16:47:05

这里给一个样例树：

代码：

#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;
}

输出结果如下

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语言二叉树的三种遍历方式的实现及原理

二叉树遍历分为三种:前序.中序.后序,其中序遍历最为重要.为啥叫这个名字?是根据根节点的顺序命名的. 比如上图正常的一个满节点,A:根节点.B:左节点.C:右节点,前序顺序是ABC(根节点排最先,然后同级先左后右):中序顺序是BAC(先左后根最后右):后序顺序是BCA(先左后右最后根). 比如上图二叉树遍历结果前序遍历:ABCDEFGHK 中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA 分析中序遍历如下图,中序比较重要(java很多树排序是基于中序,后面讲解分析) 下面介绍一下,二
C语言非递归后序遍历二叉树

本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码,供大家参考,具体内容如下法一:实现思路:一个栈先按根->右子树->左子树的顺序访问二叉树.访问时不输出.另一个栈存入前一个栈只进栈的结点. 最后输出后一个栈的结点数据. #include<stdio.h> #include<stdlib.h> typedef struct TreeNode{ char element; struct TreeNode *left,*right; }Tree,*BTree;
C语言数据结构之线索二叉树及其遍历

C语言数据结构之线索二叉树及其遍历遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,￥不能直接得到节点在遍历中的前驱和后继￥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继
C语言数据结构之二叉树的非递归后序遍历算法

C语言数据结构之二叉树的非递归后序遍历算法前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,
C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉
详细了解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 Cre
C语言二叉树的非递归遍历实例分析

本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus
详细介绍Go语言之数组与切片

目录一.数组 1.数组的定义 2.数组赋值 3.定义并初始化 4.数组的大小是类型的一部分 5.数组是值类型 6.数组长度 len() 数组长度在定义阶段已经固定 7.数组循环 8.多维数组 9.数组定义并指定位置初始化二.切片基础 1.切片的定义 2.使用切片 3.修改切片,会影响数组 4.修改数组也会影响切片 5.切片只切数组的一部分 6.当多个切片共用相同的底层数组时,每个切片所做的更改将反应在数组中 7.切片的长度和容量 8.切片追加值一.数组数组是同一类型元素的集合,可以放多个
C语言二叉树的链式存储实例

二叉树的链式存储实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl
C语言实现线索二叉树的定义与遍历示例

本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN
Java实现二叉树的建立、计算高度与递归输出操作示例

本文实例讲述了Java实现二叉树的建立.计算高度与递归输出操作.分享给大家供大家参考,具体如下: 1. 建立递归输出计算高度前中后三种非递归输出 public class Tree_Link { private int save = 0; private int now = 0; Scanner sc = new Scanner(System.in); /* * 构造函数 */ Tree_Link(){ } /* * 链表建立 */ public Tree Link_Build(Tree
C语言二叉树与堆的概念与实现

目录引言-树的故事树的基本性质和描述树的基本特点树的关键字解析树的表示方法二叉树的概念结构特殊二叉树二叉树的性质二叉树的存储结构二叉树与堆堆的实现堆排序堆的功能实现 TOPK问题二叉树的结构以及实现二叉树的遍历总结引言-树的故事在自然界中有很多树它们是这样的但是在我们的眼中他是这样的显而易见树的特点就是一对多 ,我们利用这个一对多的特点,可以让我们更好的解决编程中的问题,在树中 ,最基础的二叉树是我们的重点研究对象. 在看一眼神奇的堆排序的动态图做

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

目录

这里给一个样例树：

总结

相关推荐

随机推荐