当前位置 博文首页 > ice_elephant的博客：数据结构算法之二叉查找树
树状图是一种数据结构，它是由 n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： 每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除 了根结点外，每个子结点可以分为多个不相交的子树；
二叉树的前序遍历 通过递归的方法实现，
typedef struct _Bnode{
ElemType date;//注释ElemType我们在前面声明为int类型，
_Bnode *lchild,*rchild;
}Bnode,Btree;
树就是这么一个结构形式，一棵根树，一棵左子树，然后一棵右子树
前序遍历(递归方式):
void printFront(Btree *root){
if(!root) return ;
printf("-%d-",root->date);
printFront(root->lchild);
printFront(root->rchild);
}
//中序递归函数
void printFront(Btree *root){
if(!root) return ;
printFront(root->lchild);
printf("-%d-",root->date);
printFront(root->rchild);
}
//后序递归函数
void printFront(Btree *root){
if(!root) return ;
printFront(root->lchild);
printFront(root->rchild);
printf("-%d-",root->date);
}
/* 前序递归函数刨析
为什么叫前序遍历呢，从这个函数的实现上来看就是把printf这个打印的函数，放在 printFront(root->lchild)和printFront(root->rchild)的前面，这么放带来的影响就是，每次只要递归函数进来就直接打印进来的递归函数，它的遍历顺序就是"根左右"
#pragma once
#include<stdio.h>
#define MAX_SIZE 1024
#define isLess(a,b) (a<b)
#define isEqual(a,b) (a==b)
typedef int ElemType;
typedef struct _Bnode{
ElemType date;
_Bnode *lchild,*rchild;
}Bnode,Btree;
//数据结构算法之二叉树，二叉树就是分成两叉的树
//
typedef Bnode Elemdate;
typedef struct _Stack{
Elemdate *base;
Elemdate *top;
}Stack;
//栈的初始化
bool initStack(Stack &stack){
stack.base = new Elemdate[MAX_SIZE];
if(!stack.base){
printf("栈初始化失败!\n");
return false;
}
stack.top = stack.base;
return true;
}
//获取栈顶元素
Elemdate* getTop(Stack &stack){
return stack.top-1;
}
//入栈
bool PushStack(Stack &stack,Elemdate date){
if(stack.top-stack.base==MAX_SIZE){
printf("栈空间已满，入栈失败!\n");
return false;
}
*(stack.top++) = date;
return true;
}
//出栈
bool PopStack(Stack &stack,Elemdate &date){
if(stack.base==stack.top){
printf("无元素可出栈!\n");
return false;
}
date = *(--stack.top);
return true;
}
//判断栈是否为空
bool isEmpty(Stack&stack){
if(stack.base==stack.top){
return true;
}
return false;
}
//判断栈是否已满
bool isFully(Stack &stack){
if(stack.top-stack.base==MAX_SIZE){
return true;
}
return false;
}
//销毁栈
void destoyedStack(Stack &stack){
if(!&stack) return;
delete [MAX_SIZE] stack.base;
stack.base = stack.top = NULL;
}
//获取以元素个数
int getElemdateCount(Stack &stack){
return (stack.top-stack.base);
}
#pragma once
#include<stdio.h>
#define MAX_SIZE 1024
#define isLess(a,b) (a<b)
#define isEqual(a,b) (a==b)
typedef int ElemType;
typedef struct _Bnode{
ElemType date;
_Bnode *lchild,*rchild;
}Bnode,Btree;
//数据结构算法之二叉树，二叉树就是分成两叉的树
//
typedef Bnode Elemdate;
typedef struct _Stack{
Elemdate *base;
Elemdate *top;
}Stack;
//栈的初始化
bool initStack(Stack &stack){
stack.base = new Elemdate[MAX_SIZE];
if(!stack.base){
printf("栈初始化失败!\n");
return false;
}
stack.top = stack.base;
return true;
}
//获取栈顶元素
Elemdate* getTop(Stack &stack){
return stack.top-1;
}
//入栈
bool PushStack(Stack &stack,Elemdate date){
if(stack.top-stack.base==MAX_SIZE){
printf("栈空间已满，入栈失败!\n");
return false;
}
*(stack.top++) = date;
return true;
}
//出栈
bool PopStack(Stack &stack,Elemdate &date){
if(stack.base==stack.top){
printf("无元素可出栈!\n");
return false;
}
date = *(--stack.top);
return true;
}
//判断栈是否为空
bool isEmpty(Stack&stack){
if(stack.base==stack.top){
return true;
}
return false;
}
//判断栈是否已满
bool isFully(Stack &stack){
if(stack.top-stack.base==MAX_SIZE){
return true;
}
return false;
}
//销毁栈
void destoyedStack(Stack &stack){
if(!&stack) return;
delete [MAX_SIZE] stack.base;
stack.base = stack.top = NULL;
}
//获取以元素个数
int getElemdateCount(Stack &stack){
return (stack.top-stack.base);
}
