C#《数据结构》二叉树的创建和遍历

2023-05-17 196

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： C#《数据结构》二叉树的创建和遍历

前言

一.认识树：

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。

f15b716ee55cda6065e0a65f1b05ac6d_watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-D6ZqP6ICM5Yqo,size_20,color_FFFFFF,t_70,g_se,x_16.png

一、树的特点

树具有的特点有：

（1）每个结点有零个或多个子结点

（2）没有父节点的结点称为根节点

（3）每一个非根结点有且只有一个父节点

（4）除了根结点外，每个子结点可以分为多个不相交的子树,如左子树结点，右子树结点。

（5）叶子节点的左子树结点和右子树结点均为空;

二、二叉树的创建和遍历

1.定义二叉树结构体

代码如下（示例）：

typedef struct treenode 
{
  elemstyle data;
  struct treenode* Lchild;
  struct treenode* Lright;
}TreeNode;

2.二叉树先序遍历（递归的方法）

代码如下（示例）：

void print_Front(TreeNode* root)
{
  if (root != NULL)
  {
  printf("%5d", root->data);
  print_Front(root->Lchild);
  print_Front(root->Lright);
  }
}

2.二叉树中序遍历（递归的方法）

void print_Mid(TreeNode* root)
{
  if(root!=NULL)
  {
  print_Mid(root->Lchild);
  printf("%5d", root->data);
  print_Mid(root->Lright);
  }
}

3.二叉树后序遍历（递归方法）

void print_back(TreeNode* root)
{
  if (root == NULL)
  {
  return;
  }
  else
  {
  print_back(root->Lchild);
  print_back(root->Lright);
  printf("%5d", root->data);
  }
}

4.二叉树先序遍历（用栈的思想）

void print_FrontByStack(TreeNode* root)
{
  if (root==NULL)
  {
  return;
  }
  TreeNode* stack[maxsize];
  int stackTop = -1;
  TreeNode* pmove=root;
  while (stackTop != -1||pmove)
  {
  //入栈;
  while (pmove)
  {
    stack[++stackTop] = pmove;
    printf("%5d", pmove->data);
    pmove = pmove->Lchild;
  }
  if (stackTop != -1)
  {
    pmove = stack[stackTop--];
    pmove = pmove->Lright;
  }
  }
}
二叉树的中序遍历也用此种方法也可以打出来;
就不过多介绍了;

5.二叉树的后序遍历（非递归方法）

后序遍历有点难，需要进行判断;
void print_BackByStack(TreeNode* root)
{
  if (root==NULL)
  {
  return;
  }
  TreeNode* stack[maxsize];
  int stackTop = -1;
  TreeNode* pmove=root;
  TreeNode* flist=NULL;  //作为判断的依据;
  while (pmove)
  {
  stack[++stackTop] = pmove;
  pmove = pmove->Lchild;
  }
  //开始出栈;
  while (stackTop != -1)
  {
  pmove = stack[stackTop--];
  //右子节点都被访问了;
  if (pmove->Lright == NULL || pmove->Lright ==flist)
  {
    printf("%5d", pmove->data);
    flist = pmove;//标识;
  }
  else
        //右边的子节点没有被访问;
  {
    stack[++stackTop] = pmove;
    pmove = pmove->Lright;
    //如果子节点左节点存在，则继续入栈;
    while (pmove)
    {
    stack[++stackTop] = pmove;
    pmove = pmove->Lchild;
    }
  }
  }
}

6.二叉树层序遍历（队列的思想）

int print_floor(TreeNode* root)
{
  if (root == NULL)
  {
  return false;
  }
  else
  {
  TreeNode* LinkQueue[maxsize];
  int top = 0;
  int rear = 0;
  TreeNode* pmove;
  if (root)
  {
    LinkQueue[rear++] = root;
  }
  //开始打印;
  while (rear != top)
  {
    //开始出队列;
    pmove = LinkQueue[top++];
    printf("%5d", pmove->data);
    //左子树入队;
    if (pmove->Lchild)
      LinkQueue[rear++] = pmove->Lchild;
    if (pmove->Lright)
      LinkQueue[rear++] = pmove->Lright;
  }
  }
}

7.二叉树的结点数（总结点数，叶结点数，树的深度）

都是利用递归的方法，就介绍一下树的深度的代码：
int deep_TreeNode(TreeNode* root)
{
  if (root == NULL)
  {
  return 0;
  }
  else
  {
  int d1 = deep_TreeNode(root->Lchild) + 1;
  int d2 = deep_TreeNode(root->Lright) + 1;
  return d1 > d2 ? d1 : d2;
  }
}

源代码：

//创建二叉树；
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define true 2
#define false -2
#define maxsize  1000
typedef int elemstyle;
typedef struct treenode 
{
  elemstyle data;
  struct treenode* Lchild;
  struct treenode* Lright;
}TreeNode;
//二叉树的初始化;
TreeNode* InitNode(elemstyle data)
{
  TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
  root->data = data;
  root->Lchild = NULL;
  root->Lright = NULL;
  return root;
}
//二叉树的联系;
TreeNode* creatTreeNode(TreeNode *Fnode, TreeNode *left, TreeNode *right)
{
  Fnode->Lchild = left;
  Fnode->Lright = right;
}
//先序遍历，递归法;
void print_Front(TreeNode* root)
{
  if (root != NULL)
  {
  printf("%5d", root->data);
  print_Front(root->Lchild);
  print_Front(root->Lright);
  }
}
//用非递归的方法先序遍历,利用栈的思想;
void print_FrontByStack(TreeNode* root)
{
  if (root==NULL)
  {
  return;
  }
  TreeNode* stack[maxsize];
  int stackTop = -1;
  TreeNode* pmove=root;
  while (stackTop != -1||pmove)
  {
  //入栈;
  while (pmove)
  {
    stack[++stackTop] = pmove;
    printf("%5d", pmove->data);
    pmove = pmove->Lchild;
  }
  if (stackTop != -1)
  {
    pmove = stack[stackTop--];
    pmove = pmove->Lright;
  }
  }
}
//中序遍历，递归法;
void print_Mid(TreeNode* root)
{
  if(root!=NULL)
  {
  print_Mid(root->Lchild);
  printf("%5d", root->data);
  print_Mid(root->Lright);
  }
}
//中序遍历，非递归;
void print_MidByStack(TreeNode* root)
{
  if (root == NULL)
  {
  return;
  }
  TreeNode* stack[maxsize];
  TreeNode* pmove = root;
  int stackTop = -1;
  while (stackTop != -1||pmove)
  {
  //入栈;
  while (pmove)
  {
    stack[++stackTop] = pmove;
    pmove = pmove->Lchild;
  }
  if (stackTop != -1)
  {
    pmove = stack[stackTop--];
    printf("%5d", pmove->data);
    pmove = pmove->Lright;
  }
  }
}
//后序遍历;
void print_back(TreeNode* root)
{
  if (root == NULL)
  {
  return;
  }
  else
  {
  print_back(root->Lchild);
  print_back(root->Lright);
  printf("%5d", root->data);
  }
}
//非递归方法打印后序遍历;
void print_BackByStack(TreeNode* root)
{
  if (root==NULL)
  {
  return;
  }
  TreeNode* stack[maxsize];
  int stackTop = -1;
  TreeNode* pmove=root;
  TreeNode* flist=NULL;  //作为判断的依据;
  while (pmove)
  {
  stack[++stackTop] = pmove;
  pmove = pmove->Lchild;
  }
  //开始出栈;
  while (stackTop != -1)
  {
  pmove = stack[stackTop--];
  //右子节点都被访问了;
  if (pmove->Lright == NULL || pmove->Lright ==flist)
  {
    printf("%5d", pmove->data);
    flist = pmove;//标识;
  }
  else
        //右边的子节点没有被访问;
  {
    stack[++stackTop] = pmove;
    pmove = pmove->Lright;
    //如果子节点左节点存在，则继续入栈;
    while (pmove)
    {
    stack[++stackTop] = pmove;
    pmove = pmove->Lchild;
    }
  }
  }
}
//层序遍历，利用队列;
int print_floor(TreeNode* root)
{
  if (root == NULL)
  {
  return false;
  }
  else
  {
  TreeNode* LinkQueue[maxsize];
  int top = 0;
  int rear = 0;
  TreeNode* pmove;
  if (root)
  {
    LinkQueue[rear++] = root;
  }
  //开始打印;
  while (rear != top)
  {
    //开始出队列;
    pmove = LinkQueue[top++];
    printf("%5d", pmove->data);
    //左子树入队;
    if (pmove->Lchild)
      LinkQueue[rear++] = pmove->Lchild;
    if (pmove->Lright)
      LinkQueue[rear++] = pmove->Lright;
  }
  }
}
//树的深度;
int deep_TreeNode(TreeNode* root)
{
  if (root == NULL)
  {
  return 0;
  }
  else
  {
  int d1 = deep_TreeNode(root->Lchild) + 1;
  int d2 = deep_TreeNode(root->Lright) + 1;
  return d1 > d2 ? d1 : d2;
  }
}
//树的结点的个数;
int allTreenode(TreeNode* root)
{
  if (root == NULL)
  {
  return 0;
  }
  else
  {
  return allTreenode(root->Lright) + allTreenode(root->Lchild) + 1;
  }
}
//树的叶子结点;
int greeTreeNode(TreeNode* root)
{
  if (root == NULL)
  {
  return 0;
  }
    if (root->Lchild == NULL && root->Lright == NULL)
  {
  return 1;
  }
  else
  {
  return greeTreeNode(root->Lchild) + greeTreeNode(root->Lright);
  }
}
//交叉子节点;
void chageTreeNode(TreeNode* root)
{
  if (root == NULL)
  {
  return;
  }
  else
  {
  TreeNode* str;
  str = root->Lchild;
  root->Lchild = root->Lright;
  root->Lright = str;
  chageTreeNode(root->Lchild);
  chageTreeNode(root->Lright);
  }
}
int main(void)
{
  TreeNode *first = InitNode(1);
  TreeNode *second = InitNode(2);
  TreeNode *third = InitNode(3);
  TreeNode *four = InitNode(4);
  TreeNode *five = InitNode(5);
  TreeNode *six = InitNode(6);
  TreeNode *seven = InitNode(7);
  TreeNode *eight = InitNode(8);
  TreeNode *nine = InitNode(9);
  TreeNode *ten = InitNode(10);
  creatTreeNode(first, second, third);
  creatTreeNode(second, four,five);
  creatTreeNode(third, six, seven);
  creatTreeNode(four, eight, nine);
  creatTreeNode(five, ten, NULL);
  //先序打印，递归;
  printf("用递归方法先序打印的二叉树：\n");
  print_Front(first);
  printf("\n");
  printf("先序遍历，非递归:\n");
  print_FrontByStack(first);
  putchar('\n');
  //中序打印，用递归方法;
  printf("用递归的方法中序打印的二叉树：\n");
  print_Mid(first);
  putchar('\n');
  printf("用非递归的方法打印的二叉树：\n");
  print_MidByStack(first);
  putchar('\n');
  //后序打印;
  printf("用递归的方法后序打印的二叉树:\n");
  print_back(first);
  putchar('\n');
  print_BackByStack(first);
  putchar('\n');
  printf("二叉树层序遍历法:\n");
  print_floor(first);
  putchar('\n');
  printf("树的深度：\n");
  int k1=deep_TreeNode(first);
  printf("%d\n", k1);
  printf("树的所有结点数为：\n");
  int k2 = allTreenode(first);
  printf("%d\n", k2);
  printf("树的叶节点数为：\n");
  int k3 = greeTreeNode(first);
  printf("%d\n", k3);
  printf("子节点交换位置:\n");
  chageTreeNode(first);
  print_floor(first);
  return 0;
}

二叉树是一种很重要的数据结构，其利用的递归思想在以后也有很大的帮助。掌握递归思想有很大好处。

C#《数据结构》二叉树的创建和遍历

前言

一、树的特点

二、二叉树的创建和遍历

1.定义二叉树结构体

2.二叉树先序遍历（递归的方法）

2.二叉树中序遍历（递归的方法）

3.二叉树后序遍历（递归方法）

4.二叉树先序遍历（用栈的思想）

5.二叉树的后序遍历（非递归方法）

6.二叉树层序遍历（队列的思想）

7.二叉树的结点数（总结点数，叶结点数，树的深度）

源代码：

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C#《数据结构》二叉树的创建和遍历

前言

一、树的特点

二、二叉树的创建和遍历

1.定义二叉树结构体

2.二叉树先序遍历（递归的方法）

2.二叉树中序遍历（递归的方法）

3.二叉树后序遍历（递归方法）

4.二叉树先序遍历（用栈的思想）

5.二叉树的后序遍历（非递归方法）

6.二叉树层序遍历（队列的思想）

7.二叉树的结点数（总结点数，叶结点数，树的深度）

源代码：

热门文章

最新文章

相关课程

相关电子书