二叉树
(有关二叉树的基本定义与存储结构已在这里简要说明--->https://blog.csdn.net/qq_38193883/article/details/98869738)
下面是二叉树的基本操作：
- 定义存储结构：
typedef char Elemtype;
//定义
typedef struct Tnode{
Elemtype data;
struct Tnode *lchild,*rchild;
}Tnode,*Tree;
- 创建二叉树：
CreateTree(Tree &root){
//伪代码，不可直接用
if(ch=='空指针'){
root=NULL;
}
else{
root->data=ch;
CreateTree(root->lchild);//递归遍历创建左子树
CreateTree(root->rchild);//递归遍历创建右子树
}
}
- 二叉树的遍历：
a. 递归遍历：
void DLR(Tree root){
if(!root){
return;
}
printf("%c ",root->data);//先（中）（后）序就放最前（中间）（后）面
DLR(root->lchild);
DLR(root->rchild);
}
b.非递归（堆栈）遍历
/* 非递归中序遍历（堆栈:为了偷懒直接用库函数了，没人有意见吧，很明显。没有！）
1.遇到一个节点，就把他限压入栈，然后遍历它的左子树
2.当左子树遍历结束后 ，从栈顶弹出并访问打印数据
3.然后遍历右子树
*/
void LDRstack(Tree root){
Tree T;
stack<Tree> S;
while(T || !S.empty()) {
//以下while循环相当于递归中的 LDR(root->lchild);
while(T){
S.push(T);
T->lchild;//一直遍历左孩子并入栈
}
if(!S.empty())
{// 若栈不空
T=S.top();
S.pop();//出栈
//中就中在这
printf("%c ",T->data);
//再用同样的方式去处理右子树
T=T->rchild;
}
}
}
/* 层次遍历（这里星星要用采用队列）
1. 起初：根结点入队
2.从队列中取出一个元素
3.访问该节点，该节点带左右孩子入队
4. 重复 2.->3.->2.->3.->....->直到队列为空
*/
void Leveltravel(Tree root){
queue<Tree> Q; Tree T;
if(root==NULL){
return ;
}
Q.push(T);
while(!Q.empty()){
T=Q.front();
Q.pop();
printf("%c ",T->data);
if(T->lchild){
Q.push(T->lchild);
}
if(T->rchild){
Q.push(T->rchild);
}
}
}
- 基于遍历的新功能：
- 统计叶子节点的个数
- 查找数据为‘X’的节点
- 复制二叉树
测试实例（AC）：（i含魅力注释i）
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<queue>// 队列
#include<stack>//栈
using namespace std;
typedef char Elemtype;
//定义
typedef struct Tnode{
Elemtype data;
struct Tnode *lchild,*rchild;
}Tnode,*Tree;
//设置全局变量
int count=0;//计数器（统计叶子）
int index=0;//字符数组下标
//测试案例： char str[]="ABDH###E##CF##G##";（由于创建方法采用先序，所以输入时用先序序列）
char str[100];
//创建一棵二叉树
int CreateTree(Tree &root){
char ch;
ch=str[index++];
if(ch=='#'){
root=NULL;
}
else{
root=(Tree)malloc(sizeof(Tnode));
if(!root){
return -1;
}
root->data=ch;
CreateTree(root->lchild);
CreateTree(root->rchild);
}
return 0;
}
//用递归进行的遍历算法（3种：先序遍历，中序遍历，后序遍历）
void DLR(Tree root){
if(!root){
return;
}
printf("%c ",root->data);//先序就放最前面
DLR(root->lchild);
DLR(root->rchild);
}
void LDR(Tree root){
if(!root){
return ;
}
LDR(root->lchild);
printf("%c ",root->data);//中序就放中间
LDR(root->rchild);
}
void LRD(Tree root){
if(!root){
return;
}
LRD(root->lchild);
printf("%c ",root->data);//后序就放后面
LRD(root->rchild);
}
//在遍历算法基础上拓展的功能：
/*1. 查询二叉树中某个值为n的结点*/
Tree Survey(Tree root,Elemtype n,Tree p){
if(root){
if(root->data==n){
p=root;
return p;
}
else{
if(Survey(root->lchild,n,p)){
return Survey(root->lchild,n,p);
}
else{
return Survey(root->rchild,n,p);
}
}
}
else{
return NULL;
}
}
/*2.统计二叉树中叶子结点的个数(两种方法)
a. 使用全局变量Count计数
b. 利用函数返回值，Count = Leftcount + Rightcount
*/
int Count1(Tree root){
if(!root){
return 0;
}
if((!root->lchild)&&(!root->rchild)){
count++;
}
Count1(root->lchild);
Count1(root->rchild);
}
int Count2(Tree root){
if(!root){
return 0;
}
if((!root->lchild)&&(!root->rchild)){
return 1;
}
int l=Count2(root->lchild);
int r=Count2(root->rchild);
return l+r;
}
//3. 求二叉树的深度(后序遍历):求得左、右子树深度的最大值，然后加 1
int Heigh(Tree root){
int hl,hr;
if(!root) return 0;
else{
hl=Heigh(root->lchild);
hr=Heigh(root->rchild);
return hl>hr?hl+1:hr+1;
}
}
//4. 复制二叉树(后序遍历)
Tree Copy(Tree root)//复制二叉树t
{ Tree newtree;
if (root==NULL) newtree=NULL;
else{
newtree=(Tree)malloc(sizeof(Tnode));
newtree->data=root->data;
newtree->lchild=Copy(root->lchild);
newtree->rchild=Copy(root->rchild);
}
return newtree;
}//结束Copy
int main(){
Tree T=NULL,p;
printf("请输入你要创建的二叉 '柠檬树' 序列：\n");
scanf("%s",str);
CreateTree(T);
printf("先序遍历周星星的柠檬树：\n");
DLR(T);
printf("\n中序遍历周星星的柠檬树：\n");
LDR(T);
printf("\n后序遍历周星星的柠檬树：\n");
LRD(T);
p=Survey(T,'B',p);
printf("\n%c\n",p->data);
Count1(T);
printf("叶子节点共有%d个\n",count);
printf("叶子节点共有%d个\n",Count2(T));
printf("————此柠檬树共有%d层————\n",Heigh(T));
return 0;
}
-
运行结果：
-
正经致谢：(左图是享受二叉树的过程，别问我什么感受，看右图（酸爽）)