二叉树和二叉树递归遍历实现

之前的数据结构都是线性的,都是一对一的线性结构。其实还有一对多的结构,那就是树。

一.树

树:树是n(n>=0)个结点的有限集
《二叉树和二叉树递归遍历实现》
注:

  • n>0时根结点是唯一的,不会有很多根结点。
  • 子树个数没有限制,但是是互不相交的。

一些概念

  • 结点的度:结点拥有的子树数称为结点的度,树的度是树内各结点的度最大值。

《二叉树和二叉树递归遍历实现》
  比如刚刚这个图,D结点的度为3,B结点的度为1。树的度为3

  • 深度:树中结点最大层次称为树的深度
       上图中树的深度是4
     
    – 结点关系:结点的子树的根称为该结点的孩子(child)。该结点称为孩子的双亲(parent)。同一个双亲的孩子是兄弟。

二.二叉树的存储和遍历

二叉树

  二叉树是n>=0个结点的有限集合,由一个根结点和两棵互不相交的,分别为根结点的左子树和右子树的二叉树组成

二叉树特点

  • 每个结点最多两棵子树,二叉树中不存在度大于2的结点
  • 左右子树是有顺序的,次序不能颠倒。
  • 如果某结点只有一个子树,也要区分左右。

二叉树存储

二叉树的存储结构有很多,现在写的是最常见的存储结构——链式存储。
因为每个结点最多有两个孩子,所以就需要一个数据域和两个指针域,称这样的链表为二叉链表。
《二叉树和二叉树递归遍历实现》
lchild和rchild都是指针域,分别存放左孩子和右孩子地址。
所以存储结构为:

typedef int BElemtype;
typedef struct BTree{ 
	BElemtype data;
	struct BTree *lchild,*rchild;
}BTree,*BiTree;

二叉树遍历

二叉树遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点都被访问一次且仅被访问一次

三.二叉树遍历方法

二叉树有很多种遍历方法

1. 前序遍历
若二叉树为空,则返回,否则访问根结点,然后前序遍历左子树,再前序遍历右子树。
总结来说就是:根->左->右
《二叉树和二叉树递归遍历实现》
例如这个二叉树,前序遍历顺序为 MGDBHJWPNS

2. 中序遍历
若二叉树为空,则返回。否则从根结点开始(并不是先访问根结点),先遍历根结点的左子树,然后是访问根结点,最后遍历右子树。
总的来说:左->根->右
《二叉树和二叉树递归遍历实现》
例如这个二叉树,中序遍历顺序:BDHGJMNPSW

3. 后序遍历
若二叉树为空,则返回。否则从左到右先叶子结点遍历访问左子树,然后右子树,最后根结点。
总的来说:左->右->根
《二叉树和二叉树递归遍历实现》
后序遍历的顺序:BHDJGNSPWM

四.三种遍历的递归方法

1. 前序遍历
先上代码:

Status PreOrderTraverse(BiTree T)
{ 
	if(T == NULL)
		return 0;
	printf("%5d",T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

《二叉树和二叉树递归遍历实现》
这里使用的是递归,当一调用这个函数,判断T不为空,所以输出,打印M。
再接着调用同个函数,传过去的是G的结点地址,G不为空,那么也输出G。
以此类推,当输出了B之后,发现B的左子树为空,那么只能return。发现B的右子树也为空,那么又return。
这样return到D的PreOrderTraverse函数了,因为左子树已经输出了,那就调用它的右子树。以此类推。

2.中序遍历
这个和下面的后序遍历和之前方法一样,其实就是顺序换了一下,因为说到底就是遍历顺序不一样。

Status InOrderTraverse(BiTree T)
{ 
	if(T == NULL)
		return 0;
	InOrderTraverse(T->lchild);
	printf("%5d",T->data);
	InOrderTraverse(T->rchild);
}

3.后序遍历

Status PostOrderTraverse(BiTree T)
{ 
	if(T == NULL)
		return 0;
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	printf("%5d",T->data);
}

还有一个二叉树的初始化

这个是前序的顺序初始化的

Status InitTree(BiTree *BT)
{ 
	BElemtype num;
	scanf("%d",&num);
	if(num == 0)
	   *BT = NULL;
	else{ 
		*BT = (BiTree)malloc(sizeof(BTree));
		(*BT)->data = num;
		InitTree(&(*BT)->lchild);
		InitTree(&(*BT)->rchild);
	}
}

**这里一定要注意:就是输入时不能乱输入。不然会没反应的,还要加空格!!!!**要严格按照顺序,没有的地方就是输0

《二叉树和二叉树递归遍历实现》
比如这个键盘输入应该是:A B 0 D 0 0 C 0 0

还有篇非递归代码,感兴趣可以看看。

二叉树遍历非递归

总的代码

#include<stdio.h>
#include<stdlib.h>
int OVERFLOW = -1;
#define MAXSIZE 50
typedef int Status;
typedef int BElemtype;
typedef int SElemtype;
typedef struct BTree{ 
	BElemtype data;
	struct BTree *lchild,*rchild;
}BTree,*BiTree;

Status InitTree(BiTree *BT)
{ 
	BElemtype num;
	scanf("%d",&num);
	if(num == 0)
	   *BT = NULL;
	else{ 
		*BT = (BiTree)malloc(sizeof(BTree));

		(*BT)->data = num;
		InitTree(&(*BT)->lchild);
		InitTree(&(*BT)->rchild);
	}
}

Status PreOrderTraverse(BiTree T)
{ 
	if(T == NULL)
		return 0;
	printf("%5d",T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

Status InOrderTraverse(BiTree T)
{ 
	if(T == NULL)
		return 0;
	InOrderTraverse(T->lchild);
	printf("%5d",T->data);
	InOrderTraverse(T->rchild);
}

Status PostOrderTraverse(BiTree T)
{ 
	if(T == NULL)
		return 0;
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	printf("%5d",T->data);
}
int main(void)
{ 
	BiTree T;
	InitTree(&T);
	PreOrderTraverse(T);
	return 0;
 } 
    原文作者:五道杠的小屁孩wwk
    原文地址: https://blog.csdn.net/weixin_36101480/article/details/105185079
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞