二叉树的创建与存储，以及遍历

树的界说

• 树是n个节点的集合，在任何一棵非空树中有且仅有一个被称为根的结点，当n>1时，其余结点可以被分为m个互不相交的子集，其中每个子集又是一棵树，称其为根的子树
  

树的基本术语 

• 结点：一个数据元素以及若干指向其子树的分支
  
• 结点的度：结点所拥有的子树的棵树
  
• 树的度：树中各个结点度的最大值
  
• 叶子：度为0的结点称为叶子结点，又称为终端结点
  
• 分支结点：度不为0的结点，又称为非终端结点
  
• 结点的孩子：结点的子树的根称为该结点的孩子，该结点称为孩子结点的双亲
  
• 根：没有双亲的结点
  
• 结点的层次：从根开始界说，根为第一层，根的孩子所在的层为第二层，根的孩子的孩子所在的层为第三层，以此类推
  
• 树的深度：树的叶子结点所在的最大层次
  
• 兄弟结点：双亲一样的结点
  
• 堂兄弟：双亲位于同一层的结点
  
• 结点祖先：从根到该结点所经过的分支上的所有结点均称为该结点的祖先
  
• 子孙：某个结点的子树上的所有结点都称为该节点的子孙
  
• 有序树：若将树中各结点的各子树当作从左至右是有顺序的不能任意交换位置，则称该树为有序树，否则为无序树
  
• 丛林：m（m>=0)棵互不相交的树的集合，以是任意一棵树都可以当作是由根和其子树丛林所构成的
  

二叉树的界说

• 二叉树是n个节点的集合 ,在任何一棵非空二叉树中有且仅有一个被叫做根的节点，若n>1，则其余节点被分成两个互不相交的子集，其中每一个子集又是一棵二叉树，分别称为左子树和右子树，以是二叉树的界说是递归的可以用递归算法来创建一棵二叉树。
  
• 满二叉树：除了叶子结点以外其余结点的度全为2的二叉树
  
• 完全二叉树：在满二叉树的末了一层上从右至左一连去除若干个叶子结点便得到了一棵完全二叉树。
  

二叉树的特点

• 二叉树中各结点的度小于等于2
  
• 二叉树是有序树
  
• 二叉树的每一层至多有pow(2,n-1)个结点
  
• 深度为k的二叉树至多有pow(2,k)-1个结点
  
•  若二叉树中叶子结点即度为0的结点的个数为n0，度为2的结点的个数为n2，则n0=n2+1
  
• 对于一棵有n个节点的完全二叉树其深度为([log2(n)]+1)
  
• 将完全二叉树从左至右从上至下按层次编号1，2.....则对任意节点i，满意若i=1，则该结点为根节点无双亲，若i>1则i的双亲为[i/2]；若2i>n则结点i无左孩子反之结点i的左孩子为2i，若(2i+1 )大于n，则结点i无右孩子反之结点i的右孩子为(2i+1)
  

二叉树的存储结构

• 二叉树的顺序存储表现 
  

对于完全二叉树而言，我们用一组地点一连的存储单元即一维数组依次从上至下从左至右的存储该完全二叉树 中的节点元素，对于普通的二叉树我们将其结点与其对应的完全二叉树相对照，存储在一维数组中，例如：

二叉树的顺序存储的特点

• 结点间的关系蕴含在其存储位置中
  
• 浪费空间，适用于存储满二叉树或者完全二叉树 
  

分析：鉴于顺序存储的二叉树比力简单，读者可以自己尝试界说二叉树的结点，然后将结点存储在一维数组中即可。
 

•  二叉树的链式存储表现
  

二叉树的结点可以用结构体类型来表现，界说不同的结点结构，可以构成不同的链式存储结构。
二叉链表：存储该二叉树的链表的结点的指针域有两个，分别指向该节点的左右孩子结点
三叉链表： 存储该二叉树的链表的结点的指针域有三个，分别指向左孩子结点，双亲结点，以及右孩子结点

• 二叉树的三种遍历方法
  

• 先序遍历：先访问根节点，再访问左子树和右子树，对左子树和右子树的访问也遵照根左右的原则
  
• 中序遍历：先访问左子树，再访问根节点，末了访问右子树，对左子树和右子树的访问也遵照左根右的原则
  
• 后序遍历：先访问左子树，再访问右子树，末了访问根节点，对左子树和右子树的访问也遵照左右根的顺序 
  

由以上界说可知对二叉树的三种遍历方法都是递归的以是设计遍历方法时需要用到递归 

下面演示用二叉链表来表现如图所示的二叉树，以及接纳三种遍历方法遍历该二叉树的过程，在程序代码中给出了完备的注释：

 

• 第一步界说二叉树的结点，用结构体类型来界说节点结构
  1. typedef struct BitNode
  2. {
  3.         char value;                                              //数据域，用于存放该节点的值
  4.         struct BitNode* lchild, * rchild;                              //二叉链表的节点中有两个指针与分别指向该节点的左右孩子节点
  5.        
  7. }BitNode,*Bitree;       //为定义的结构体类型起别名为BitNode,以及为该结构体类型的指针起别名为Bitree,此时执行语句"BitNode a"相当于执行语句"struct BitNode a",执行语句"Bitree a"相当于执行语句"BitNode *a"

  复制代码
•  第二步创建该二叉树
  
  1. Bitree CreateTree(Bitree head)
  2. {
  3.         char value;
  4.         Bitree p;
  5.         //p = head = NULL;           //相当于每次调用该函数都会把头指针设置为空指针；这显然是错误的
  7.         printf("请输入节点的值\n");
  8.         scanf("%c", &value);
  9.         getchar();
  11.         if (value == '#')
  12.                 return NULL;                         //创建二叉树，当输入#号时表示不再继续输入返回空指针给上一级调用对象，即将上一级节点没有左孩子或者没有右孩子，理解这一点很重要，函数的返回值是所定义的结构体类型的指针
  13.         else
  14.         {
  16.                 p = (Bitree)malloc(sizeof(BitNode));
  17.                 p->value = value;
  18.                 if (!head)
  19.                         head = p;          //创建头指针;
  21.                 printf("请输入%c的左子树的根节点\n", value);
  22.                 p->lchild = CreateTree(head);           //递归创建左子树；
  23.                 printf("请输入%c的右子树的根节点\n", value);
  24.                 p->rchild = CreateTree(head);           //递归创建右子树；
  26.                 return p;              //函数出口返回的是指向创建的二叉树的第一个结点的指针；
  28.         }
  29. }

  复制代码
  
  
• 先序遍历该二叉树
  
  1. void FirstOrderTraverse(Bitree p)
  2. {
  3.         if (p == NULL)
  4.                 return;
  5.         printf("%c\t", p->value);
  6.         FirstOrderTraverse(p->lchild);
  7.         FirstOrderTraverse(p->rchild);
  10. }

  复制代码
  
  
• 中序遍历该二叉树
  
  1. void MiddleOrderTraverse(Bitree p)
  2. {
  3.         if (p == NULL)
  4.                 return;
  5.         MiddleOrderTraverse(p->lchild);
  6.         printf("%c\t", p->value);
  7.         MiddleOrderTraverse(p->rchild);
  10. }

  复制代码
  
  
• 后序遍历该二叉树
  
  1. void PostOrderTraverse(Bitree p)                        //后序遍历二叉树即最后访问根节点
  2. {
  3.         if (p == NULL)
  4.                 return;
  6.         PostOrderTraverse(p->lchild);                         //此递归函数都没有递归结束条件，怎么从递归中出来呢？递归结束条件怎么能不写
  7.         PostOrderTraverse(p->rchild);
  8.         printf("%c\t", p->value);
  9. }

  复制代码
  
  

程序完备代码以及运行效果截图：
代码：

1. //二叉树的界说与储存，用二叉链表存储二叉树#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>            //该头文件包含了malloc函数的声明；//界说二叉树的节点结构，接纳二叉链表存储该二叉树typedef struct BitNode{        char value;                                              //数据域，用于存放该节点的值        struct BitNode* lchild, * rchild;                              //二叉链表的节点中有两个指针与分别指向该节点的左右孩子节点}BitNode, * Bitree;//为界说的结构体类型起别名为BitNode,//以及为该结构体类型的指针起别名为Bitree,此时实验语句"BitNode a"相称于实验语句"struct BitNode a",实验语句"Bitree a"相称于实验语句"BitNode *a"//创建一棵不带头节点的二叉树的函数Bitree CreateTree(Bitree head);//后序遍历一棵树 void FirstOrderTraverse(Bitree p);void MiddleOrderTraverse(Bitree p);void PostOrderTraverse(Bitree p);int main(){        Bitree head = NULL,p;        head = CreateTree(head);        if (head)                printf("树创建乐成\n");        else                printf("树创建失败\n\n\n");        printf("先序遍历该树的效果\n");        FirstOrderTraverse(head);        printf("\n");        printf("中序遍历该树的效果\n");        MiddleOrderTraverse(head);        printf("\n");        printf("后序遍历该树的效果\n");        PostOrderTraverse(head);        printf("\n");        return 0;}//函数实现，按照中序遍历的头脑创建该二叉树，即先创建根节点再创建根节点的左子树和右子树，根据此头脑创建二叉树可以用到递归算法Bitree CreateTree(Bitree head)
2. {
3.         char value;
4.         Bitree p;
5.         //p = head = NULL;           //相当于每次调用该函数都会把头指针设置为空指针；这显然是错误的
7.         printf("请输入节点的值\n");
8.         scanf("%c", &value);
9.         getchar();
11.         if (value == '#')
12.                 return NULL;                         //创建二叉树，当输入#号时表示不再继续输入返回空指针给上一级调用对象，即将上一级节点没有左孩子或者没有右孩子，理解这一点很重要，函数的返回值是所定义的结构体类型的指针
13.         else
14.         {
16.                 p = (Bitree)malloc(sizeof(BitNode));
17.                 p->value = value;
18.                 if (!head)
19.                         head = p;          //创建头指针;
21.                 printf("请输入%c的左子树的根节点\n", value);
22.                 p->lchild = CreateTree(head);           //递归创建左子树；
23.                 printf("请输入%c的右子树的根节点\n", value);
24.                 p->rchild = CreateTree(head);           //递归创建右子树；
26.                 return p;              //函数出口返回的是指向创建的二叉树的第一个结点的指针；
28.         }
29. }void FirstOrderTraverse(Bitree p)
30. {
31.         if (p == NULL)
32.                 return;
33.         printf("%c\t", p->value);
34.         FirstOrderTraverse(p->lchild);
35.         FirstOrderTraverse(p->rchild);
38. }void MiddleOrderTraverse(Bitree p)
39. {
40.         if (p == NULL)
41.                 return;
42.         MiddleOrderTraverse(p->lchild);
43.         printf("%c\t", p->value);
44.         MiddleOrderTraverse(p->rchild);
47. }
48. void PostOrderTraverse(Bitree p)                        //后序遍历二叉树即最后访问根节点
49. {
50.         if (p == NULL)
51.                 return;
53.         PostOrderTraverse(p->lchild);                         //此递归函数都没有递归结束条件，怎么从递归中出来呢？递归结束条件怎么能不写
54.         PostOrderTraverse(p->rchild);
55.         printf("%c\t", p->value);
56. }

复制代码

运行效果截图

 
 
 
 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。