当前位置:新注册送38元体验金 > 新注册送38元体验金编程 > 数据结构整理(二) 树,数据结构整理

数据结构整理(二) 树,数据结构整理

文章作者:新注册送38元体验金编程 上传时间:2019-08-22

数据结构整理(二) 树,数据结构整理

一、前言

  项目源码及其他声明等参见数据结构(一)线性结构篇。

二、相关概念

  树作为一种应用广泛的一对多非线性数据结构,不仅有数据间的指向关系,还有层级关系,示例见图一。因树的结构比较复杂,为了简化操作及存储,我们一般将树转换为二叉树处理,因此本文主要讨论二叉树。

  1. 二叉树
      二叉树是每个节点最多拥有两个子节点的树结构,若移除根节点则其余节点会被分成两个互不相交的子树,分别称为左子树和右子树。二叉树是有序树,左右子树有严格的次序,若颠倒则成为一棵不一样的二叉树。
  2. 满二叉树   满二叉树,顾名思义除叶子节点外所有节点都拥有两个孩子,且叶子节点在同一层的二叉树,示例见图二。
  3. 完全二叉树   完全二叉树,移除最后一层节点后是满二叉树,且最后一层的节点都连续集中在最左面,示例见图三。 1 /// <summary> 2 /// 先序遍历(DLR) 3 /// </summary> 4 /// <![CDATA[首先访问跟节点,然后遍历左子树,最后右子树]]> 5 static void PreOrder(Node<char> root) 6 { 7 if (root == null) 8 { 9 return; 10 } 11 12 Print(root); 13 PreOrder(root.LChild); 14 PreOrder(root.RChild); 15 } 16 17 /// <summary> 18 /// 中序遍历(LDR) 19 /// </summary> 20 /// <![CDATA[先遍历左子树,然后根节点,最后遍历右子树]]> 21 static void InOrder(Node<char> root) 22 { 23 if (root == null) 24 { 25 return; 26 } 27 28 InOrder(root.LChild); 29 Print(root); 30 InOrder(root.RChild); 31 } 32 33 /// <summary> 34 /// 后序遍历(LRD) 35 /// </summary> 36 /// <![CDATA[先遍历左子树,然后遍历右子树,最后遍历根节点]]> 37 static void PostOrder(Node<char> root) 38 { 39 if (root == null) 40 { 41 return; 42 } 43 44 PostOrder(root.LChild); 45 PostOrder(root.RChild); 46 Print(root); 47 } 48 49 /// <summary> 50 /// 层序遍历 51 /// </summary> 52 /// <![CDATA[从上向下从左到右]]> 53 static void LevelOrder(Node<char> root) 54 { 55 if (root == null) 56 { 57 return; 58 } 59 CSeqQueue<Node<char>> sq = new CSeqQueue<Node<char>>(50); 60 sq.In(root); 61 while (!sq.IsEmpty()) 62 { 63 Node<char> tmp = sq.Out(); 64 Print(tmp); 65 66 if (tmp.LChild != null) 67 { 68 sq.In(tmp.LChild); 69 } 70 71 if (tmp.RChild != null) 72 { 73 sq.In(tmp.RChild); 74 } 75 } 76 }

     

    ) 树,数据结构整理 一、前言 项目源码及其他声明等参见数据结构(一)线性结构篇。 二、相关概念 树作为一种应用广泛...

本文由新注册送38元体验金发布于新注册送38元体验金编程,转载请注明出处:数据结构整理(二) 树,数据结构整理

关键词: