C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

本文实例讲述了C语言二叉树常见操作。分享给大家供大家参考,具体如下:

一、基本概念

每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒。

性质:

1、非空二叉树的第n层上至多有2^(n-1)个元素。

2、深度为h的二叉树至多有2^h-1个结点。

满二叉树:所有终端都在同一层次,且非终端结点的度数为2。

在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1。

完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置。

对于完全二叉树,设一个结点为i则其父节点为i/2,2i为左子节点,2i+1为右子节点。

二、存储结构

顺序存储:

将数据结构存在一块固定的数组中。

#define LENGTH 100
typedef char datatype;
typedef struct node{
  datatype data;
  int lchild,rchild;
  int parent;
}Node;
Node tree[LENGTH];
int length;
int root;

虽然在遍历速度上有一定的优势,但因所占空间比较大,是非主流二叉树。二叉树通常以链式存储。

链式存储:

typedef char datatype;
typedef struct BinNode{
  datatype data;
  struct BinNode* lchild;
  struct BinNode* rchild;
}BinNode;
typedef BinNode* bintree;     //bintree本身是个指向结点的指针

三、二叉树的遍历

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历,中序遍历,后序遍历。

前序遍历:根节点->左子树->右子树

中序遍历:左子树->根节点->右子树

后序遍历:左子树->右子树->根节点

例如:求下面树的三种遍历

前序遍历:abdefgc

中序遍历:debgfac

后序遍历:edgfbca

四、遍历的实现

递归实现(以前序遍历为例,其他的只是输出的位置稍有不同)

void preorder(bintree t){
  if(t){
    printf("%c ",t->data);
    preorder(t->lchild);
    preorder(t->rchild);
  }
}

非递归的实现

因为当遍历过根节点之后还要回来,所以必须将其存起来。考虑到后进先出的特点,选用栈存储。数量确定,以顺序栈存储。

#define SIZE 100
typedef struct seqstack{
  bintree data[SIZE];
  int tag[SIZE];  //为后续遍历准备的
  int top;   //top为数组的下标
}seqstack;
void push(seqstack *s,bintree t){
  if(s->top == SIZE){
    printf("the stack is full\n");
  }else{
    s->top++;
    s->data[s->top]=t;
  }
}
bintree pop(seqstack *s){
  if(s->top == -1){
    return NULL;
  }else{
    s->top--;
    return s->data[s->top+1];
  }
}

1、前序遍历

void preorder_dev(bintree t){
  seqstack s;
  s.top = -1;   //因为top在这里表示了数组中的位置,所以空为-1
  if(!t){
    printf("the tree is empty\n");
  }else{
    while(t || s.stop != -1){
      while(t){  //只要结点不为空就应该入栈保存,与其左右结点无关
         printf("%c ",t->data);
        push(&s,t);
        t= t->lchild;
      }
      t=pop(&s);
      t=t->rchild;
    }
  }
}

2、中序遍历

void midorder(bintree t){
  seqstack s;
  s.top = -1;
  if(!t){
    printf("the tree is empty!\n");
  }else{
    while(t ||s.top != -1){
      while(t){
        push(&s,t);
        t= t->lchild;
      }
      t=pop(&s);
      printf("%c ",t->data);
      t=t->rchild;
    }
  }
}

3、后序遍历

因为后序遍历最后还要要访问根结点一次,所以要访问根结点两次。采取夹标志位的方法解决这个问题。

这段代码非常纠结,对自己有信心的朋友可以尝试独立写一下。反正我是写了很长时间。逻辑不难,我画了一张逻辑图:

代码:

void postorder_dev(bintree t){
  seqstack s;
  s.top = -1;
  if(!t){
    printf("the tree is empty!\n");
  }else{
    while(t || s.top != -1){  //栈空了的同时t也为空。
      while(t){
        push(&s,t);
        s.tag[s.top] = 0;  //设置访问标记,0为第一次访问,1为第二次访问
        t= t->lchild;
      }
      if(s.tag[s.top] == 0){ //第一次访问时,转向同层右结点
        t= s.data[s.top];  //左走到底时t是为空的,必须有这步!
        s.tag[s.top]=1;
        t=t->rchild;
      }else {
        while (s.tag[s.top] == 1){ //找到栈中下一个第一次访问的结点,退出循环时并没有pop所以为其左子结点
          t = pop(&s);
          printf("%c ",t->data);
        }
        t = NULL; //必须将t置空。跳过向左走,直接向右走
      }
    }
  }
}

4、层次遍历:即每一层从左向右输出

元素需要储存有先进先出的特性,所以选用队列存储。

队列的定义:

#define MAX 1000
typedef struct seqqueue{
  bintree data[MAX];
  int front;
  int rear;
}seqqueue;
void enter(seqqueue *q,bintree t){
  if(q->rear == MAX){
    printf("the queue is full!\n");
  }else{
    q->data[q->rear] = t;
    q->rear++;
  }
}
bintree del(seqqueue *q){
  if(q->front == q->rear){
    return NULL;
  }else{
    q->front++;
    return q->data[q->front-1];
  }
}

遍历实现

void level_tree(bintree t){
  seqqueue q;
  bintree temp;
  q.front = q.rear = 0;
  if(!t){
    printf("the tree is empty\n");
    return ;
  }
  enter(&q,t);
  while(q.front != q.rear){
    t=del(&q);
    printf("%c ",t->data);
    if(t->lchild){
      enter(&q,t->lchild);
    }
    if(t->rchild){
      enter(&q,t->rchild);
    }
  }
}

5、利用前序遍历的结果生成二叉树

//递归调用,不存点,想的时候只关注于一个点,因为还会回来的,不要跟踪程序运行,否则容易多加循环
void createtree(bintree *t){
  datatype c;
  if((c=getchar()) == '#')
    *t = NULL;
  else{
    *t = (bintree)malloc(sizeof(BinNode));
    (*t)->data = c;
    createtree(&(*t)->lchild);
    createtree(&(*t)->rchild);
  }
}

6、二叉树的查找

bintree search_tree(bintree t,datatype x){
  if(!t){
    return NULL;
  }
  if(t->data == x){
    return t;
  }else{
    if(!search_tree(t->lchild,x)){
      return search_tree(t->rchild,x);
    }
    return t;
  }
}

7、统计结点个数

int count_tree(bintree t){
  if(t){
    return (count_tree(t->lchild)+count_tree(t->rchild)+1);
  }
  return 0;
}

8、比较两个树是否相同

int is_equal(bintree t1,bintree t2){
  if(!t1 && !t2){   //都为空就相等
    return 1;
  }
  if(t1 && t2 && t1->data == t2->data){   //有一个为空或数据不同就不判断了
    if(is_equal(t1->lchild,t2->lchild))
      if(is_equal(t1->rchild,t2->rchild)){
        return 1;
      }
  }
  return 0;
}

9、求二叉树的深度

int hight_tree(bintree t){
  int h,left,right;
  if(!t){
    return 0;
  }
  left = hight_tree(t->lchild);
  right = hight_tree(t->rchild);
  h = (left>right?left:right)+1;
  return h;
}

希望本文所述对大家C语言程序设计有所帮助。

您可能感兴趣的文章:

  • c语言版本二叉树基本操作示例(先序 递归 非递归)
  • 使用C语言构建基本的二叉树数据结构
  • C语言实现二叉树遍历的迭代算法
  • C语言中计算二叉树的宽度的两种方式
  • 用C语言判断一个二叉树是否为另一个的子结构
  • C语言 二叉树的链式存储实例
  • C语言二叉树的非递归遍历实例分析
  • 使用C语言求二叉树结点的最低公共祖先的方法
  • C语言实现线索二叉树的定义与遍历示例
  • C语言数据结构之线索二叉树及其遍历
  • C语言实现二叉树的搜索及相关算法示例
(0)

相关推荐

  • 使用C语言构建基本的二叉树数据结构

    二叉树结构常用的一些初始化代码 #include #include typedef struct Node{ int data; Node *leftchild; Node *rightchild; }Node; /* 初始化一棵二叉树排序树. */ void InitBinaryTree(Node**root,int elem) { *root=(Node*)malloc(sizeof(Node)); if(!(*root)) { printf("Memory allocation for r

  • 使用C语言求二叉树结点的最低公共祖先的方法

    算法分析 我们直接来分析O(n)的算法. 比如求节点F和节点H的最低公共祖先,先求出从根节点A到F的路径,再求出A到H的路径,那么最后一个相同的节点就是最低公共祖先.A->B->D->F和A->B->E->H,最后相同的节点事B,所以最低公共祖先是B节点.求根节点到指定节点的算法先前已经更新过了,复杂度是O(n),所以总的时间复杂度是O(n). 条件细化: (1)树如果是二叉树,而且是二叉排序树.              这中条件下可以使用二叉排序树的搜索功能找到最低

  • C语言实现线索二叉树的定义与遍历示例

    本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN

  • C语言实现二叉树遍历的迭代算法

    本文实例讲述了C语言实现二叉树遍历的迭代算法,是数据结构算法中非常经典的一类算法.分享给大家供大家参考. 具体实现方法如下: 二叉树中序遍历的迭代算法: #include <iostream> #include <stack> using namespace std; struct Node { Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {} int item; Node* le

  • c语言版本二叉树基本操作示例(先序 递归 非递归)

    复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

  • C语言实现二叉树的搜索及相关算法示例

    本文实例讲述了C语言实现二叉树的搜索及相关算法.分享给大家供大家参考,具体如下: 二叉树(二叉查找树)是这样一类的树,父节点的左边孩子的key都小于它,右边孩子的key都大于它. 二叉树在查找和存储中通常能保持logn的查找.插入.删除,以及前驱.后继,最大值,最小值复杂度,并且不占用额外的空间. 这里演示二叉树的搜索及相关算法: #include<stack> #include<queue> using namespace std; class tree_node{ public

  • 用C语言判断一个二叉树是否为另一个的子结构

    1.问题描述: 如何判断一个二叉树是否是另一个的子结构?      比如: 2       /   \      9    8     / \    /    2  3  5   / 6 有个子结构是    9   / \ 2  3 2.分析问题:     有关二叉树的算法问题,一般都可以通过递归来解决.那么写成一个正确的递归程序,首先一定要分析正确递归结束的条件. 拿这道题来讲,什么时候递归结束. <1>第二个二叉树root2为空时,说明root2是第一棵二叉树的root1的子结构,返回tr

  • C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,¥不能直接得到节点在遍历中的前驱和后继¥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

  • C语言中计算二叉树的宽度的两种方式

    C语言中计算二叉树的宽度的两种方式 二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧. 采用递归方式 下面是代码内容: int GetMaxWidth(BinaryTree pointer){ int width[10];//加入这棵树的最大高度不超过10 int maxWidth=0; int floor=1; if(pointer){ if(floor==1){//如果访问的是根节点的话,第一层节点++; width[floor]++; flo

  • C语言二叉树的非递归遍历实例分析

    本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

  • C语言 二叉树的链式存储实例

    二叉树的链式存储 实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl

随机推荐