devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构（十四）——二叉树

作者：知新_RL | 2024-08-03 13:23:28

赞

踩

二叉树的每个结构包括三个成员,分别是指向

数据结构（十四）——二叉树

一、二叉树简介

1、二叉树简介

二叉树是由n（n>=0）个结点组成的有序集合，集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
二叉树的五种形态：
数据结构（十四）——二叉树

2、二叉树的存储结构模型

树的另一种表示法：孩子兄弟表示法
A、每个结点都有一个指向其第一个孩子的指针
B、每个结点都有一个指向其第一个右兄弟的指针
数据结构（十四）——二叉树
孩子兄弟表示法的特性：
A、能够表示任意的树形结构
B、每个结点包含一个数据成员和两个指针成员
C、孩子结点指针和兄弟结点指针构成树杈

3、满二叉树

如果二叉树中所有分支结点的度数都为2，并且叶子结点都在统一层次上，则二叉树为满二叉树。
数据结构（十四）——二叉树

4、完全二叉树

如果一棵具有n个结点的高度为k的二叉树，树的每个结点都与高度为k的满二叉树中编号为1——n的结点一一对应，则二叉树为完全二叉树。
完全二叉树的特性：
A、同样结点数的二叉树，完全二叉树的高度最小
B、完全二叉树的叶子结点仅出现在最下边两层，并且最底层的叶子结点一定出现在左边，倒数第二层的叶子结点一定出现在右边。
C、完全二叉树中度为1的结点只有左孩子。
数据结构（十四）——二叉树

5、二叉树的特性

A、在二叉树的第i层上最多有2^(i-1)个结点（i>=1）。
B、高度为k的二叉树，最多有2^k-1个结点（k>=0）。
C、对任何一棵二叉树，如果其叶结点有n个，度为2的非叶子结点有m个，则
n = m + 1。
D、具有n个结点的完全二叉树的高度为logn + 1
E、对于有n个结点的完全二叉树，按层次对结点进行编号（从上到下，从左到右），对于任意编号为i的结点：
数据结构（十四）——二叉树

二、二叉树的操作

1、二叉树的存储结构实现

数据结构（十四）——二叉树
二叉树结点包含四个固定的成员：结点的数据域、指向父结点的指针域、指向左子结点的指针域、指向右子结点的指针域。结点的数据域、指向父结点的指针域从TreeNode模板类继承而来。
二叉树结点的实现：

  1.     template <typename T>
  2.   class BTreeNode:public TreeNode<T>
  3.   {
  4.   public:
  5.     BTreeNode<T>* m_left;//左子结点
  6.     BTreeNode<T>* m_right;//右子结点
  7.     BTreeNode()
  8.     {
  9.         m_left = NULL;
  10.         m_right = NULL;
  11.     }
  12.  
  13.     //工厂方法，创建堆空间的结点
  14.     static BTreeNode<T>* NewNode()
  15.     {
  16.       BTreeNode<T>* ret = new BTreeNode<T>();
  17.       if(ret != NULL)
  18.       {
  19.           //堆空间的结点标识为true
  20.           ret->m_flag = true;
  21.       }
  22.       return ret;
  23.     }
  24.   };

2、二叉树的结点查找

A、基于数据元素的查找
定义基于数据元素查找的函数
数据结构（十四）——二叉树

  1. virtual BTreeNode<T>* find(BTreeNode<T>* node, const T& value)const
  2.       {
  3.           BTreeNode<T>* ret = NULL;
  4.           //如果根节点node
  5.           if(node != NULL)
  6.           {
  7.               if(node->value == value)
  8.               {
  9.                   ret = node;
  10.               }
  11.               else
  12.               {
  13.                   //查找左子树
  14.                   if(ret == NULL)
  15.                   {
  16.                       ret = find(node->m_left, value);
  17.                   }
  18.                   //如果左子树没有找到，ret返回NULL，查找右子树
  19.                   if(ret == NULL)
  20.                   {
  21.                       ret = find(node->m_right, value);
  22.                   }
  23.               }
  24.           }
  25.           return ret;
  26.       }
  27.  
  28.     BTreeNode<T>* find(const T& value)const
  29.     {
  30.         return find(root(), value);
  31.     }

B、基于结点的查找
定义基于结点查找的函数
数据结构（十四）——二叉树

  1. virtual BTreeNode<T>* find(BTreeNode<T>* node, BTreeNode<T>* obj)const
  2.       {
  3.           BTreeNode<T>* ret = NULL;
  4.           if(node != NULL)
  5.           {
  6.               //根节点node为目标结点
  7.               if(node == obj)
  8.               {
  9.                   ret = node;
  10.               }
  11.               else
  12.               {
  13.                   //查找左子树
  14.                   if(ret == NULL)
  15.                   {
  16.                       ret = find(node->m_left, obj);
  17.                   }
  18.                   //如果左子树没有找到，ret返回NULL，继续查找右子树
  19.                   if(ret == NULL)
  20.                   {
  21.                       ret = find(node->m_right, obj);
  22.                   }
  23.               }
  24.           }
  25.           return ret;
  26.       }
  27.     BTreeNode<T>* find(TreeNode<T>* node)const
  28.     {
  29.         return find(root(), dynamic_cast<BTreeNode<T>*>(node));
  30.     }

3、二叉树的结点插入

根据插入的位置定义二叉树结点的位置枚举类型：

  1.   enum BTNodePos
  2.     {
  3.         Any,
  4.         Left,
  5.         Right
  6.     };

在node结点的pos位置插入newnode结点的功能函数如下：
数据结构（十四）——二叉树

  1. virtual bool insert(BTreeNode<T>* newnode, BTreeNode<T>* node, BTNodePos pos)
  2.       {
  3.           bool ret = true;
  4.           //插入的位置为Any
  5.           if(pos == Any)
  6.           {
  7.               //如果没有左子结点，插入结点作为左子结点
  8.               if(node->m_left == NULL)
  9.               {
  10.                   node->m_left = newnode;
  11.               }
  12.               //如果有左子结点，没有右子结点，插入结点作为右子结点
  13.               else if(node->m_right == NULL)
  14.               {
  15.                   node->m_right = newnode;
  16.               }
  17.               //如果node结点的左右子结点不为空，插入失败
  18.               else
  19.               {
  20.                   ret = false;
  21.               }
  22.           }
  23.           else if(pos == Left)
  24.           {
  25.               //如果指定插入左子结点，如果没有左子结点，插入结点
  26.               if(node->m_left == NULL)
  27.               {
  28.                   node->m_left = newnode;
  29.               }
  30.               else
  31.               {
  32.                   ret = false;
  33.               }
  34.           }
  35.           else if(pos == Right)
  36.           {
  37.               //如果指定插入右子结点，如果没有右子结点，插入结点
  38.               if(node->m_right == NULL)
  39.               {
  40.                   node->m_right = newnode;
  41.               }
  42.               else
  43.               {
  44.                   ret = false;
  45.               }
  46.           }
  47.           else
  48.           {
  49.               ret = false;
  50.           }
  51.           return ret;
  52.       }

A、插入新结点
数据结构（十四）——二叉树

  1.  //插入结点，无位置要求
  2.     bool insert(TreeNode<T>* node)
  3.     {
  4.        return insert(dynamic_cast<BTreeNode<T>*>(node), Any);
  5.     }
  6.     //插入结点，指定插入位置
  7.     virtual bool insert(BTreeNode<T>* node, BTNodePos pos)
  8.     {
  9.         bool ret = true;
  10.         if(node != NULL)
  11.         {
  12.             if(this->m_root == NULL)
  13.             {
  14.                 node->parent = NULL;
  15.                 this->m_root = node;
  16.             }
  17.             else
  18.             {
  19.                BTreeNode<T>* np = find(node->parent);
  20.                if(np != NULL)
  21.                {
  22.                    ret = insert(dynamic_cast<BTreeNode<T>*>(node), np, pos);
  23.                }
  24.                else
  25.                {
  26.                    THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
  27.                }
  28.             }
  29.         }
  30.         else
  31.         {
  32.             THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
  33.         }
  34.         return ret;
  35.     }

B、插入数据元素
数据结构（十四）——二叉树

  1.  //插入数据，指定插入位置和父结点
  2.     virtual bool insert(const T& value, TreeNode<T>* parent, BTNodePos pos)
  3.     {
  4.         bool ret = true;
  5.         BTreeNode<T>* node = BTreeNode<T>::NewNode();
  6.         if(node != NULL)
  7.         {
  8.             node->parent = parent;
  9.             node->value = value;
  10.             ret = insert(node, pos);
  11.             if(!ret)
  12.             {
  13.                 delete node;
  14.             }
  15.         }
  16.         else
  17.         {
  18.             THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
  19.         }
  20.  
  21.         return ret;
  22.     }
  23.     //插入数据，指定父结点
  24.     bool insert(const T& value, TreeNode<T>* parent)
  25.     {
  26.         return insert(value, parent, Any);
  27.     }

4、二叉树的结点删除

删除功能函数的定义：
数据结构（十四）——二叉树

  1. virtual void remove(BTreeNode<T>* node, BTree<T>* ret)
  2.       {
  3.           ret = new BTree<T>();
  4.           if(ret == NULL)
  5.           {
  6.               THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
  7.           }
  8.           else
  9.           {
  10.               if(node == root())
  11.               {
  12.                   this->m_root = NULL;
  13.               }
  14.               else
  15.               {
  16.                   BTreeNode<T>* parent = dynamic_cast<BTreeNode<T>*>(node->parent);
  17.                   if(parent->m_left == node)
  18.                   {
  19.                       parent->m_left = NULL;
  20.                   }
  21.                   else if(parent->m_right == node)
  22.                   {
  23.                       parent->m_right = NULL;
  24.                   }
  25.                   node->parent = NULL;
  26.               }
  27.               ret->m_root = node;
  28.           }
  29.       }

A、基于数据元素值删除

  1.  //根据数据元素删除结点
  2.     SharedPointer< Tree<T> > remove(const T& value)
  3.     {
  4.         BTree<T>* ret = NULL;
  5.         BTreeNode<T>* node = find(value);
  6.         if(node == NULL)
  7.         {
  8.             THROW_EXCEPTION(InvalidParameterException, "No value...");
  9.         }
  10.         else
  11.         {
  12.             remove(node, ret);
  13.         }
  14.         return ret;
  15.     }

B、基于结点删除

  1.  //根据结点删除结点
  2.     SharedPointer< Tree<T> > remove(TreeNode<T>* node)
  3.     {
  4.         BTree<T>* ret = NULL;
  5.         node = find(node);
  6.         if(node != NULL)
  7.         {
  8.             remove(dynamic_cast<BTreeNode<T>*>(node), ret);
  9.         }
  10.         else
  11.         {
  12.             THROW_EXCEPTION(InvalidParameterException, "No node...");
  13.         }
  14.         return ret;
  15.     }

5、二叉树的清空

将二叉树中所有在堆空间分配的结点销毁。
清除node结点为根节点的二叉树的功能函数：
数据结构（十四）——二叉树

  1. virtual void free(BTreeNode<T>* node)
  2.       {
  3.           if(node != NULL)
  4.           {
  5.               free(node->m_left);
  6.               free(node->m_right);
  7.           }
  8.           //如果结点在堆空间分配
  9.           if(node->flag())
  10.           {
  11.               delete node;
  12.           }
  13.       }
  14.     //清空树
  15.     void clear()
  16.     {
  17.         free(root());
  18.         this->m_root = NULL;
  19.     }

6、二叉树的属性操作

A、树中结点的数量
定义计算某个结点为根结点的树的结点的数量
数据结构（十四）——二叉树

  1.  int count(BTreeNode<T>* node) const
  2.       {
  3.           int ret = 0;
  4.           if(node != NULL)
  5.           {
  6.               ret = count(node->m_left) + count(node->m_right) + 1;
  7.           }
  8.           return ret;
  9.       }
  10.     //树的结点数目访问函数
  11.     int count()const
  12.     {
  13.         return count(root());
  14.     }

B、树的高度
获取node结点为根结点的二叉树的高度的功能函数：
数据结构（十四）——二叉树

  1.  int height(BTreeNode<T>* node) const
  2.       {
  3.           int ret = 0;
  4.           if(node != NULL)
  5.           {
  6.               int l = height(node->m_left);
  7.               int r = height(node->m_right);
  8.               ret = ((l > r)?l:r) + 1;
  9.           }
  10.           return ret;
  11.       }
  12.     //树的高度访问函数
  13.     int height()const
  14.     {
  15.         return height(root());
  16.     }

C、树的度
获取node为根结点的二叉树的度的功能函数：
数据结构（十四）——二叉树

  1.  int degree(BTreeNode<T>* node) const
  2.       {
  3.           int ret = 0;
  4.           if(node != NULL)
  5.           {
  6.               //根结点的度数
  7.               ret = (!!node->m_left + !!node->m_right);
  8.               //左子树的度
  9.               if(ret < 2)
  10.               {
  11.                   int l = degree(node->m_left);
  12.                   if(ret < l)
  13.                   {
  14.                       ret = l;
  15.                   }
  16.               }
  17.               //右子树的度数
  18.               if(ret < 2)
  19.               {
  20.                   int r = degree(node->m_left);
  21.                   if(ret < r)
  22.                   {
  23.                       ret = r;
  24.                   }
  25.               }
  26.           }
  27.           return ret;
  28.       }
  29.     //树的度访问函数
  30.     int degree()const
  31.     {
  32.         return degree(root());
  33.     }

7、二叉树的层次遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问依次，且仅被访问一次。
根据游标思想，提供一组遍历的先关函数，按层次访问二叉树中的数据元素。
数据结构（十四）——二叉树
引入一个队列，辅助遍历二叉树。
LinkedQueue<BTreeNode<T>*> m_queue;
层次遍历的过程如下：
数据结构（十四）——二叉树

  1.  //将根结点压入队列
  2.     bool begin()
  3.     {
  4.       bool ret = (root() != NULL);
  5.       if(ret)
  6.       {
  7.           //清空队列
  8.           m_queue.clear();
  9.           //根节点加入队列
  10.           m_queue.add(root());
  11.       }
  12.       return ret;
  13.     }
  14.     //判断队列是否为空
  15.     bool end()
  16.     {
  17.         return (m_queue.length() == 0);
  18.     }
  19.  
  20.     //队头元素弹出，将队头元素的孩子压入队列中
  21.     bool next()
  22.     {
  23.       bool ret = (m_queue.length() > 0);
  24.       if(ret)
  25.       {
  26.           BTreeNode<T>* node = m_queue.front();
  27.           m_queue.remove();//队头元素出队
  28.           //将队头元素的子结点入队
  29.           if(node->m_left != NULL)
  30.           {
  31.               m_queue.add(node->m_left);
  32.           }
  33.           if(node->m_right != NULL)
  34.           {
  35.               m_queue.add(node->m_right);
  36.           }
  37.       }
  38.       return ret;
  39.     }
  40.     //访问队头元素指向的数据元素
  41.     T current()
  42.     {
  43.       if(!end())
  44.       {
  45.           return m_queue.front()->value;
  46.       }
  47.       else
  48.       {
  49.           THROW_EXCEPTION(InvalidOperationException, "No value at current Node...");
  50.       }
  51.     }

8、二叉树的克隆

定义克隆node结点为根结点的二叉树的功能函数：
数据结构（十四）——二叉树

  1. BTreeNode<T>* clone(BTreeNode<T>* node)
  2.       {
  3.           BTreeNode<T> * ret = NULL;
  4.           if(node != NULL)
  5.           {
  6.               ret = BTreeNode<T>::NewNode();
  7.               if(ret != NULL)
  8.               {
  9.                   ret->value = node->value;
  10.                   //左子树
  11.                   ret->m_left = clone(node->m_left);
  12.                   //右子树
  13.                   ret->m_right = clone(node->m_right);
  14.                   //如果左子树不为空，设置左子树的父结点
  15.                   if(ret->m_left != NULL)
  16.                   {
  17.                       ret->m_left->parent = ret;
  18.                   }
  19.                   //如果右子树不为空，设置右子树父结点
  20.                   if(ret->m_right != NULL)
  21.                   {
  22.                       ret->m_right->parent = ret;
  23.                   }
  24.               }
  25.               else
  26.               {
  27.                   THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
  28.               }
  29.           }
  30.           return ret;
  31.       }
  32.     SharedPointer<BTreeNode<T>> clone()const
  33.     {
  34.         BTree<T>* ret = new BTree<T>();
  35.         if(ret != NULL)
  36.         {
  37.             ret->m_root = clone(root());
  38.         }
  39.         else
  40.         {
  41.             THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
  42.         }
  43.         return ret;
  44.     }

9、二叉树的比较

判断两棵二叉树中的数据元素是否对应相等
定义二叉树相等比较的功能函数：
数据结构（十四）——二叉树

  1. bool equal(BTreeNode<T>* l, BTreeNode<T>* r)const
  2.       {
  3.           bool ret = true;
  4.           //二叉树自比较
  5.           if(l == r)
  6.           {
  7.               ret = true;
  8.           }
  9.           //两棵二叉树都不为空
  10.           else if(l != NULL &&  r != NULL)
  11.           {
  12.              ret = (l->value == r->value) && (equal(l->m_left, r->m_left)) && (l->m_right, r->m_right);
  13.           }
  14.           //有一棵二叉树为空，一棵二叉树不为空
  15.           else
  16.           {
  17.               ret = false;
  18.           }
  19.           return ret;
  20.       }
  21.  
  22.     bool operator ==(const BTree<T>& tree)const
  23.     {
  24.         return equal(root(), tree.root());
  25.     }
  26.  
  27.     bool operator !=(const BTree<T>& tree)const
  28.     {
  29.         return !(*this == tree);//使用==比较
  30.     }

10、二叉树的相加

将当前二叉树与参数btree二叉树中对应的数据元素相加，返回一棵在堆空间创建的新的二叉树。
二叉树相加实例如下：
数据结构（十四）——二叉树
定义将两棵二叉树相加的功能函数：
数据结构（十四）——二叉树

  1.  BTreeNode<T>* add(BTreeNode<T>* l, BTreeNode<T>* r)const
  2.       {
  3.           BTreeNode<T>* ret = NULL;
  4.           //二叉树l为空
  5.           if(l == NULL && r != NULL)
  6.           {
  7.             ret = clone(r);
  8.           }
  9.           //二叉树r为空
  10.           else if(l != NULL && r == NULL)
  11.           {
  12.             ret = clone(l);
  13.           }
  14.           //二叉树l和二叉树r不为空
  15.           else if(l != NULL && r != NULL)
  16.           {
  17.               ret = BTreeNode<T>::NewNode();
  18.               if(ret != NULL)
  19.               {
  20.                   //根节点数据元素相加
  21.                   ret->value = l->value + r->value;
  22.                   //左子树相加
  23.                   ret->m_left = add(l->m_left, r->m_left);
  24.                   //右子树相加
  25.                   ret->m_right = add(l->m_right, r->m_right);
  26.                   //左子树不为空，设置左子树的父结点为当前结点
  27.                   if(ret->m_left != NULL)
  28.                   {
  29.                       ret->m_left->parent = ret;
  30.                   }
  31.                   //右子树不为空，设置右子树的父结点为当前结点
  32.                   if(ret->m_right != NULL)
  33.                   {
  34.                       ret->m_right->parent = ret;
  35.                   }
  36.               }
  37.               else
  38.               {
  39.                   THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
  40.               }
  41.           }
  42.           return ret;
  43.       }
  44.         SharedPointer<BTree<T>> add(const BTree<T>& other)const
  45.     {
  46.         BTree<T>* ret = new BTree<T>();
  47.         if(ret != NULL)
  48.         {
  49.             ret->m_root = add(root(), other.root());
  50.         }
  51.         else
  52.         {
  53.             THROW_EXCEPTION(NoEnoughMemoryException, "No enough memoty...");
  54.         }
  55.         return ret;
  56.     }

三、二叉树的典型遍历方式

二叉树有先序、中序、后序三种遍历方式，三种遍历方法的不同主要是取决于根节点的遍历顺序。

1、前序遍历

如果二叉树为空，则无操作，直接返回。
如果二叉树非空，则执行以下操作：
A、访问根结点；
B、先序遍历左子树；
C、先序遍历右子树。
先序遍历实现代码：
数据结构（十四）——二叉树

  1. void preOrderTraversal(BTreeNode<T>* node, LinkedQueue<BTreeNode<T>*>& queue)
  2. {
  3.       if(node != NULL)
  4.       {
  5.           queue.add(node);
  6.           preOrderTraversal(node->m_left, queue);
  7.           preOrderTraversal(node->m_right, queue);
  8.       }
  9.  }

先序遍历二叉树示例：
数据结构（十四）——二叉树

2、中序遍历

如果二叉树为空，则无操作，直接返回。
如果二叉树非空，则执行以下操作：
A、中序遍历左子树；
B、访问根结点；
C、中序遍历右子树。
中序遍历实现代码：
数据结构（十四）——二叉树

  1. void inOrderTraversal(BTreeNode<T>* node, LinkedQueue<BTreeNode<T>*>& queue)
  2. {
  3.   if(node != NULL)
  4.   {
  5.       inOrderTraversal(node->m_left, queue);
  6.       queue.add(node);
  7.       inOrderTraversal(node->m_right, queue);
  8.   }
  9. }

中序遍历二叉树示例：
数据结构（十四）——二叉树

3、后序遍历

如果二叉树为空，则无操作，直接返回。
如果二叉树非空，则执行以下操作：
A、后序遍历左子树；
B、后序遍历右子树；
C、访问根结点。
后序遍历实现代码：
数据结构（十四）——二叉树

  1. void postOrderTraversal(BTreeNode<T>* node, LinkedQueue<BTreeNode<T>*>& queue)
  2. {
  3.   if(node != NULL)
  4.   {
  5.       postOrderTraversal(node->m_left, queue);
  6.       postOrderTraversal(node->m_right, queue);
  7.       queue.add(node);
  8.   }
  9. }

后序遍历二叉树示例：
数据结构（十四）——二叉树

4、遍历算法的封装

定义遍历方式的枚举类型：

  1.   enum BTTraversal
  2.     {
  3.         PreOder,
  4.         InOder,
  5.         PostOder
  6.     };

根据参数order选择遍历的方式，返回数组保存了二叉树遍历结点

  1.  SharedPointer<Array<T>> traversal(BTTraversal order)
  2.     {
  3.         DynamicArray<T>* ret = NULL;
  4.         LinkedQueue<BTreeNode<T>*> queue;//保存遍历二叉树的结点
  5.         switch (order)
  6.         {
  7.             case PreOder:
  8.                 preOrderTraversal(root(), queue);
  9.                 break;
  10.             case InOder:
  11.                 inOrderTraversal(root(), queue);
  12.                 break;
  13.             case PostOder:
  14.                 postOrderTraversal(root(), queue);
  15.                 break;
  16.             default:
  17.                 THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
  18.                 break;
  19.         }
  20.         ret = new DynamicArray<T>(queue.length());
  21.         if(ret != NULL)
  22.         {
  23.             for(int i = 0; i < ret->length(); i++, queue.remove())
  24.             {
  25.                 ret->set(i, queue.front()->value);
  26.             }
  27.         }
  28.         else
  29.         {
  30.             THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory...");
  31.         }
  32.  
  33.         return ret;
  34.     }

四、线索化二叉树

1、线索化二叉树简介

线索化二叉树是将二叉树转换为双向链表的过程（将非线性的二叉树转换为线性的链表）。
二叉树的线索化能够反映某种二叉树的遍历次序（结点的先后访问次序）。
线索化二叉树的过程：
数据结构（十四）——二叉树
二叉树线索化的实现：
数据结构（十四）——二叉树
通过某种遍历方式遍历二叉树，根据遍历次序将二叉树结点依次存储到辅助队列中，最后将辅助队列中保存的结点依次出队并连接（连接时，原二叉树结点的m_left指针作为双向链表结点的m_prev指针，指向结点的前驱；原二叉树结点的m_right结点作为双向链表结点的m_next指针，指向结点的后继），成为双向链表。

  1.     void traversal(BTTraversal order, LinkedQueue<BTreeNode<T>*>& queue)
  2.     {
  3.         switch (order)
  4.         {
  5.         case PreOrder:
  6.             preOrderTraversal(root(), queue);
  7.             break;
  8.         case InOrder:
  9.             inOrderTraversal(root(), queue);
  10.             break;
  11.         case PostOrder:
  12.             postOrderTraversal(root(), queue);
  13.             break;
  14.         case LevelOrder:
  15.             levelOrderTraversal(root(), queue);
  16.             break;
  17.         default:
  18.             THROW_EXCEPTION(InvalidParameterException, "Parameter invalid...");
  19.             break;
  20.         }
  21.     }

2、层次遍历算法

增加层次遍历方式LevelOrder到遍历方式枚举类型中。

  1. enum BTTraversal
  2. {
  3.     PreOrder,//先序遍历
  4.     InOrder,//中序遍历
  5.     PostOrder,//后序遍历
  6.     LevelOrder//层次遍历
  7. };

层次遍历算法：
A、将根结点入队
B、访问队头元素指向的二叉树结点
C、将队头元素出队，队头元素的孩子入队
D、判断队列是否为空，如果非空，继续B；如果为空，结束。
数据结构（十四）——二叉树
层次遍历二叉树的实例如下：
数据结构（十四）——二叉树

  1. //层次遍历
  2.     void levelOrderTraversal(BTreeNode<T>* node, LinkedQueue<BTreeNode<T>*>& queue)
  3.     {
  4.         if(node != NULL)
  5.         {
  6.             //辅助队列
  7.             LinkedQueue<BTreeNode<T>*> temp;
  8.             //根结点压入队列
  9.             temp.add(node);
  10.             while(temp.length() > 0)
  11.             {
  12.                 BTreeNode<T>* n = temp.front();
  13.                 //如果左孩子不为空，将左孩子结点入队
  14.                 if(n->m_left != NULL)
  15.                 {
  16.                     temp.add(n->m_left);
  17.                 }
  18.                 //如果右孩子不为空，将右孩子结点入队
  19.                 if(n->m_right != NULL)
  20.                 {
  21.                     temp.add(n->m_right);
  22.                 }
  23.                 //将队列的队头元素出队
  24.                 temp.remove();
  25.                 //将队列的队头元素入队输出队列
  26.                 queue.add(n);
  27.             }
  28.         }
  29.     }

3、队列中结点的连接

将队列中的所有结点连接成为一个线性的双向链表
数据结构（十四）——二叉树

  1. void connect(LinkedQueue<BTreeNode<T>*>& queue)
  2.     {
  3.         BTreeNode<T>* ret = NULL;
  4.         if(queue.length() > 0)
  5.         {
  6.             //返回队列的队头元素指向的结点作为双向链表的首结点
  7.             ret = queue.front();
  8.             //双向链表的首结点的前驱设置为空
  9.             ret->m_left = NULL;
  10.             //创建一个游标结点，指向队列队头
  11.             BTreeNode<T>* slider = queue.front();
  12.             //将队头元素出队
  13.             queue.remove();
  14.             while(queue.length() > 0)
  15.             {
  16.                 //当前游标结点的后继指向队头元素
  17.                 slider->m_right = queue.front();
  18.                 //当前队头元素的前驱指向当前游标结点
  19.                 queue.front()->m_left = slider;
  20.                 //将当前游标结点移动到队头元素
  21.                 slider = queue.front();
  22.                 //将当前队头元素出队，继续处理新的队头元素
  23.                 queue.remove();
  24.             }
  25.             //双向链表的尾结点的后继为空
  26.             slider->m_right = NULL;
  27.         }
  28.     }

4、线索化二叉树的实现

线索化二叉树函数接口的设计：
BTreeNode<T>* thread(BTTraversal order)
A、根据参数order选择线索化的方式（先序、中序、后序、层次）
B、返回值是线索化二叉树后指向链表首结点的指针
C、线索化二叉树后，原有的二叉树被破坏，二叉树的所有结点根据遍历次序组建为一个线性的双向链表，对应的二叉树应为空。
线索化二叉树的流程：
数据结构（十四）——二叉树

  1.  BTreeNode<T>* thread(BTTraversal order)
  2.     {
  3.         BTreeNode<T>* ret = NULL;
  4.         LinkedQueue<BTreeNode<T>*>* queue;
  5.         //遍历二叉树，并按遍历次序将结点保存到队列
  6.         traversal(order, queue);
  7.         //连接队列中的结点成为双向链表
  8.         ret = connect(queue);
  9.         //将二叉树的根节点置空
  10.         this->m_root = NULL;
  11.         //将游标遍历的辅助队列清空
  12.         m_queue.clear();
  13.         //返回双向链表的首结点
  14.         return ret;
  15.     }

转载于:https://blog.51cto.com/9291927/2083190

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/923190
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号