数据结构:二叉树

二叉树是数的一种特殊情况,每个节点只能有左右两个孩子节点,二叉树的好处就是方便表示。

这里主要写了二叉树的先序,中序,后序遍历(这里不会细讲这个是什么东西,不知道的请自行百度)。然后还有计算二叉树的深度,二叉树的节点个数。

下面的代码都是基于上面这个图形进行的遍历。

#include"pch.h"
#include <iostream>
using namespace std;

#define MAXSIZE 100
typedef struct BiTNode
{
	//二叉树的存储结构
	char data;
	struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;

typedef struct
{
	//结构体定义了三个变量
	//一个是栈顶指针,一个是栈底指针
	BiTree *base;
	BiTree *top;
	int stacksize;
}sqstack;

bool TreeInit(BiTree &T);
void InorderTraverse(BiTree T);
void FrontTraverse(BiTree T);
void BackTraverse(BiTree T);
bool InitStack(sqstack &s);
bool Push(sqstack &s, BiTree  e);
bool Pop(sqstack &s, BiTree &e);
void StackInorderTraverse(BiTree T);
void CreateBitree(BiTree &T);
int Depth(BiTree T);
int NodeCount(BiTree T);
int main()
{
	BiTree T = new BiTNode;
	//TreeInit(T);
	CreateBitree(T);
	cout << "中序遍历:";
	InorderTraverse(T);
	cout<<endl << "先序遍历:";
	FrontTraverse(T);
	cout << endl << "后序遍历:";
	BackTraverse(T);
	cout << endl << "非递归中序遍历:";
	StackInorderTraverse(T);
	cout << endl << "树的深度为:" << Depth(T);
	cout << endl << "节点个数为:" << NodeCount(T);
	//system("pause");
	return 0;
}
//计算节点个数
int NodeCount(BiTree T)
{
	if (T == NULL) return 0;//如果是空树则返回空
	else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
	//否则就直接返回左节点+右节点数+1(这个是遍历算法,遍历次数就等于节点个数)
}
//计算二叉树的深度
int Depth(BiTree T)
{
	int m, n;
	if (T == NULL) return 0;//如果是空树,那么记为0
	else
	{
		m = Depth(T->lchild);//遍历计算右子树的深度
		n = Depth(T->rchild);//遍历计算左子树的深度
		if (m > n) return (m + 1);
		else return (n + 1);//判断哪个大就返回哪个(+1就相当于深度+1)
	}
}
//先序遍历建立二叉链表
void CreateBitree(BiTree  &T)
{
	//就是先给根节点赋值,然后在遍历创建左子树,最后再遍历创建右子树
	char ch;
	cin >> ch;
	if (ch == '#') T = NULL;
	else
	{
		T = new  BiTNode;
		T->data = ch;
		CreateBitree(T->lchild);
		CreateBitree(T->rchild);
	}
}

//非递归实现中序遍历
void StackInorderTraverse(BiTree T)
{
	sqstack *s = new	sqstack;
	InitStack(*s);
	BiTree p = T;
	BiTree q = new BiTNode;
	while (p || s->top != s->base)
	{
		if (p)
		{
			//这里利用了两个BiTree指针,其核心思想就是先把最左子树进栈
			//然后在把最左子树出栈并输出值,最后就是把右子树进栈
			Push(*s, p);
			p = p->lchild;
		}
		else
		{
			Pop(*s, q);
			cout << q->data<<" ";
			p = q->rchild;
		}
	}
}
//栈的初始化
bool InitStack(sqstack &s)
{
	//初始化一个空栈,然后让栈顶指针指向栈底
	s.base = new BiTree[MAXSIZE];
	if (!s.base) return false;
	s.top = s.base;
	s.stacksize = MAXSIZE;
	return true;
}
//入栈
bool Push(sqstack &s, BiTree e)
{
	//判断栈是否满了
	if (s.top - s.base == s.stacksize) return false;
	//注意s.top其实不是存储的栈顶元素,它在栈顶元素的上面一个,所以是先赋值后加
	*s.top++ = e;
	return true;
}
//出栈
bool Pop(sqstack &s,BiTree &e)
{
	if (s.top == s.base) return false;
	//出栈就是把栈顶元素先减1然后在赋值
	e = *--s.top;
	return true;
}

bool TreeInit(BiTree &T)
{
	//二叉树的初始化,我们这里直接赋值5个节点
	T->data = 'a';
	T->lchild = new BiTNode;
	T->rchild = new BiTNode;
	T->lchild->lchild = new BiTNode;
	T->lchild->rchild = new BiTNode;
	T->lchild->data = 'b';
	T->rchild->data = 'c';
	T->rchild->lchild = NULL;//这里记得把子节点的左右子树都置为空
	T->rchild->rchild = NULL;
	T->lchild->lchild->data = 'd';
	T->lchild->lchild->lchild = NULL;
	T->lchild->lchild->rchild = NULL;
	T->lchild->rchild->data = 'e';
	T->lchild->rchild->lchild = NULL;
	T->lchild->rchild->rchild = NULL;
	return true;
}

//中序遍历二叉树
void InorderTraverse(BiTree T)
{
	if (T)
	{
		//中序遍历的核心思想就是先遍历左子树,然后在遍历中子树,最后遍历右子树
		//这里利用的递归的思想巧妙的实现了这个效果,我这里也很难解释,
		//如果你对中序遍历很熟悉的话,那么这个其实也很好理解
		InorderTraverse(T->lchild);
		cout << T->data << " ";
		InorderTraverse(T->rchild);
	}
}
//先序遍历
void FrontTraverse(BiTree T)
{
	if (T)
	{
		//先序遍历其实和中序遍历的代码差别不大,就是改变一下顺序即可
		cout << T->data << " ";
		FrontTraverse(T->lchild);
		FrontTraverse(T->rchild);
	}
}
//后序遍历
void BackTraverse(BiTree T)
{
	if (T)
	{
		//后序遍历就是先访问左子树,然后在访问右子树,最后访问根节点
		BackTraverse(T->lchild);
		BackTraverse(T->rchild);
		cout << T->data << " ";
	}
}

实际效果:

点赞
  1. 哈哈哈说道:

    漂亮

哈哈哈进行回复 取消回复

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00