C语言 数据结构之中序二叉树实例详解

C语言数据结构 中序二叉树

前言:

线索二叉树主要是为了解决查找结点的线性前驱与后继不方便的难题。它只增加了两个标志性域,就可以充分利用没有左或右孩子的结点的左右孩子的存储空间来存放该结点的线性前驱结点与线性后继结点。两个标志性域所占用的空间是极少的,所有充分利用了二叉链表中空闲存的储空间。

要实现线索二叉树,就必须定义二叉链表结点数据结构如下(定义请看代码):


left


leftTag


data


rightTag


right

说明:

1.       leftTag=false时,表示left指向该结点的左孩子;

2.       leftTag=true时,表示left指向该结点的线性前驱结点;

3.       rightTag=false时,表示right指向该结点的右孩子;

4.       rightTag=true时,表示right指向该结点的线性后继结点;

以二叉链表结点数据结构所构成的二叉链表作为二叉树的存储结构,叫做线索二叉链表;指向结点的线性前驱或者线性后继结点的指针叫做线索;加上线索的二叉树称为线索二叉树;对二叉树以某种次序遍历将其变为线索二叉树的过程叫做线索化。

中序次序线索化二叉树算法:

  中序次序线索化是指用二叉链表结点数据结构建立二叉树的二叉链表,然后按照中序遍历的方法访问结点时建立线索;(具体看代码)

检索中序二叉树某结点的线性前驱结点的算法:

1.       如果该结点的leftTag=true,那么left就是它的线性前驱;

2.       如果该结点的leftTag=false,那么该结点左子树最右边的尾结点就是它的线性前驱点;

(具体请看代码)

检索中序二叉树某结点的线性后继结点和算法:

1.       如果该结点的right=true,那么right就是它的线性后继结点;

2.       如果该结点的right=false,那么该结点右子树最左边的尾结点就是它的线性后继结点

(具体请看代码)

图:后继线索


图:前驱线索

节点定义:

struct Node
{
  int data;
  bool leftTag;
  bool rightTag;
  Node* left;
  Node* right;
  Node(int _data):data(_data),left(0),right(0),leftTag(false),rightTag(false){}
}; 

类定义:

class BinaryTree
{
private:
  Node* root;
private:
  Node* head;
  Node* pre;
  void makeThread(Node* node);
public:
  void buildThread();
  void traverseBySuccessor();
  void traverseByPredecessor(); 

// helper methods
private:
  static inline bool visit(Node* T)
  {
    if (T)
    {
      printf("data:%c, left:%c, right:%c\n",
        (char)T->data,
        (T->left!=0) ? (char)T->left->data : '#',
        (T->right!=0) ? (char)T->right->data : '#');
      return true;
    }
    else return false;
  }
}; 

方法定义:

void BinaryTree::makeThread(Node* node)
{
  if (node!=NULL)
  {
    makeThread(node->left);
    if (pre!= NULL)
    {
      if (pre->right==NULL) // 如果前驱节点的右子树为空, 那么把前驱节点的右子树用作线索
      {
        pre->rightTag = true;
        pre->right = node;
      }
      else pre->rightTag = false;
    }
    if (node->left==NULL) // 如果当前结点的左子树为空, 那么把当前结点的左子树用作线索
    {
      node->leftTag = true;
      node->left = pre;
    }
    else node->leftTag = false;
    pre = node;
    makeThread(node->right);
  }
} 

void BinaryTree::traverseBySuccessor()
{
  Node* p = head->left; //first find the root node
  // 亲测表明 如果不使用head哑节点 就要设三道卡, 防止p访问到NULL,
  // 分别在主while处, 第二个visit处和下面的p=p->right处
  while (p!=head)
  {
    while (!p->leftTag)
      p = p->left;
    visit(p); 

    while (p->rightTag && p->right!=head)
    {
      p = p->right;
      visit(p);
    }
    p = p->right;
  }
  cout<<endl;
} 

void BinaryTree::traverseByPredecessor()
{
  Node* p = head->left; //first find the root node
  while (p!=head)
  {
    while (!p->rightTag)
      p = p->right;
    visit(p);
    if (p!=NULL)
    {
      while (p->leftTag && p->left!=head)
      {
        p = p->left;
        visit(p);
      }
      p = p->left;
    }
  }
  cout<<endl;
} 

void BinaryTree::buildThread()
{
  pre = NULL;
  head = new Node('@');
  head->left = root;
  head->right = head;
  makeThread(root);
  // 经过了makeThread过程之后, pre必然指向中序遍历最晚的结点.
  // 把pre的右子树指向head, 就构成了一个双向循环链表
  //
  pre->rightTag = 1;
  pre->right = head;
  pre = NULL;
  Node* p = root;
  /*
   * 在建立前驱线索的时候,最左边的结点没有和head结点连接。要在这里补上
   */
  while (p->left!=NULL)
    p = p->left;
  p->left = head;
} 

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • 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语言数据结构二叉树简单应用 在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree),接下来我就在这里给大家介绍一下二叉树在算法中的简单使用: 我们要完成总共有 (1)二叉树的创建 (2)二叉树的先中后序递归遍历 (3)统计叶子结点的总数 (4)求树的高度 (5)反转二叉树 (6)输出每个叶子结点到根节点的路径 (7)输出根结点到每个叶子结点的路径. 定义二叉树结点类型

  • 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语言实现二叉树遍历的迭代算法

    本文实例讲述了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语言程序中对二叉树数据结构的各种遍历方式

    二叉树遍历的基本思想 二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题.非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧.接下来根据下图讲讲树的遍历. 1.先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树.上图的先序遍历结果就是:ABCDEF 2.中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树.上图的中序遍历结果就是:CBDAEF 3.后序遍历:后序遍历是先输出左子树,再输出右子树,最后输

  • 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语言判断一个二叉树是否为另一个的子结构

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

  • 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语言求二叉树结点的最低公共祖先的方法

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

  • 使用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

随机推荐