树的基本知识点
树的ADT(抽象数据类型)
树的储存结构
二叉树的定义
二叉树的储存结构
遍历二叉树
二叉树的建立
二叉树的ADT
1 2 3 4 5 |
typedef struct BiTNode { ElemType date; //结点的数据域 struct BiTNode *lchild , *rchild; //指向左孩子,右孩子 } BiTNode , *BiTree; |
其中 BiTNode T 等价于 BiTNode *T
二叉树的遍历
有三种遍历方式:(V是访问visist , L是左边left ,R是右边right)(先访问根节点就叫先序,中间访问根节点就叫中序)
VLR(先序):先访问根结点,再先序遍历左子树,再先序遍历右子树(后面有举例)
LVR(中序):先中序遍历左子树,再访问根节点,再中序遍历右子树
LRV(后序):先后序遍历左子树,再后序遍历右子树,再访问根节点
遍历实例举例:
每进去一个新节点都要操作三个步骤:V或L或R
(1)先序遍历
1 2 3 4 5 6 7 8 9 |
void PreOrdeTraverse(BiTree T) { if (T) { //递归结束条件,T*为空 visit(T->date); //访问根节点 PreOrdeTraverse(T->lchild); //先序遍历左子树 PreOrdeTraverse(T->rchild); //先序遍历右子树 } } |
(2)中序遍历
中序遍历的方法与先序遍历一样,只不过顺序有改变,每当来到一个新节点,先看有没有左子树,有左子树,就进去左子树,没有就访问当前结点,之后再去找右子树,没有左右子树或左右子树结点都访问了,就回到上一个结点
1 2 3 4 5 6 7 8 9 |
void InOrdeTraverse(BiTree T) { if (T) { InOrdeTraverse(T->lchild); visit(T->date); InOrdeTraverse(T->rchild); } } |
(3)后序遍历
1 2 3 4 5 6 7 8 9 |
void PosOrdeTraverse(BiTree T) { if (T) { PosOrdeTraverse(T->lchild); PosOrdeTraverse(T->rchild); visit(T->date); } } |
二叉树的建立
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
//先序序列创建一颗二叉树 void CreatBiTree(BiTree *T) { char c; scanf ( "%c" , &c); if (c == '#' ) *T = NULL; else { *T = (BiTNode*) malloc ( sizeof (BiTNode)); //给结点申请一个空间 (*T)->date = c; CreatBiTree(&((*T)->lchild)); //创建左子树 CreatBiTree(&((*T)->rchild)); //创建右子树 } } |
这里说明一下,为什么要传入树的指针的指针
假如我们要用一个函数去改变一个整型变量 n 的值 ,我们知道必须传入这个变量n的指针进去这个函数,要不然函数中n的变化影响不了函数外的n值
这里也是一样,我们要改变左右子树的地址,让他们指向一个新的空间,所以要传入左右子树地址的地址,才能在函数里改变他们的地址
实例:
以先序序列输入一棵树,并用三种遍历方式打印出这棵树,并且找到某个字母所在的层数
我们下面这棵树为例(没有子树记作#)(找到大写字母D的所在层数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<stdio.h> #include<stdlib.h> typedef struct BiTNode { char date; //结点的数据域 struct BiTNode *lchild , *rchild; //指向左孩子和右孩子 }BiTNode , *BiTree ; //先序序列创建一颗二叉树 void CreatBiTree(BiTree *T) { char c; scanf ( "%c" , &c); if (c == '#' ) *T = NULL; else { *T = (BiTNode*) malloc ( sizeof (BiTNode)); //给结点申请一个空间 (*T)->date = c; CreatBiTree(&((*T)->lchild)); //创建左子树 CreatBiTree(&((*T)->rchild)); //创建右子树 } } //访问二叉树结点操作 void visit( char c) { printf ( "%c" ,c); } //先序遍历二叉树 void PreOrdeTraverse(BiTree T) { if (T) { visit(T->date); PreOrdeTraverse(T->lchild); PreOrdeTraverse(T->rchild); } } //中序遍历二叉树 void InOrdeTraverse(BiTree T) { if (T) { InOrdeTraverse(T->lchild); visit(T->date); InOrdeTraverse(T->rchild); } } //后序遍历二叉树 void PosOrdeTraverse(BiTree T) { if (T) { PosOrdeTraverse(T->lchild); PosOrdeTraverse(T->rchild); visit(T->date); } } //查找字母D在第几层 void serch(BiTree T , int leavel) { if (T){ if (T->date == 'D' ) { printf ( "D在第%d层!" ,leavel); } serch(T->lchild , leavel+1); serch(T->rchild , leavel+1); } } int main() { BiTree T; int leavel = 1; printf ( "请输入先序创建的二叉树,以#结束:" ); CreatBiTree(&T); printf ( "正在先序打印二叉树:" ); PreOrdeTraverse(T); putchar ( '\n' ); printf ( "正在中序打印二叉树:" ); InOrdeTraverse(T); putchar ( '\n' ); printf ( "正在后序打印二叉树:" ); PosOrdeTraverse(T); putchar ( '\n' ); serch(T , leavel); } |
运行结果:
如果你对C/C++感兴趣,想要深入学习,这里有一个交流群推荐给你。不论是大牛还是小白,在这里都能获得成长。群内含有素材包,学习书籍电子书资源,还有免费课程哦~
扫描进入群聊,和志同道合的小伙伴一起学习进步吧~