注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天涯倦客的博客

祝福你朋友永远快乐!

 
 
 

日志

 
 

数据结构C#版笔记--树与二叉树  

2011-01-20 15:20:40|  分类: C# |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

                图1

上图描述的数据结构就是“树”,其中最上面那个圈圈A称之为根节点(root),其它圈圈称为节点(node),当然root可以认为是node的特例。

跟之前学习过的线性结构不同,它是一对多的非线性结构,具有二个基本特点

1、根节点(root)没有前驱节点,除root之外的所有节点有且只有一个前驱节点
2、树中的所有节点都可以有0个或多个后继节点。

所以下面这些歪瓜咧枣,不能算是树:

                图2

下是是一些烦人但是很重要的术语
  1、结点(Node):表示树中的数据元素,由数据项和数据元素之间的关系组成。在图1中,共有10个结点。
  2、结点的度(Degree of Node):结点所拥有的子树的个数,在图1中,结点A的度为3。
  3、树的度(Degree of Tree):树中各结点度的最大值。在图1中,树的度为3。
  4、叶子结点(Leaf Node):度为0的结点,也叫终端结点。在图1中,结点E、F、G、H、I、J都是叶子结点。
  5、分支结点(Branch Node):度不为0的结点,也叫非终端结点或内部结点。在图1中,结点A、B、C、D是分支结点。
  6、孩子(Child):结点子树的根。在图1中,结点B、C、D是结点A的孩子。
  7、双亲(Parent):结点的上层结点叫该结点的双亲。在图1中,结点B、C、D的双亲是结点A。
  8、祖先(Ancestor):从根到该结点所经分支上的所有结点。在图1中,结点E的祖先是A和B。
  9、子孙(Descendant):以某结点为根的子树中的任一结点。在图1中,除A之外的所有结点都是A的子孙。
10、兄弟(Brother):同一双亲的孩子。在图1中,结点B、C、D互为兄弟。
11、结点的层次(Level of Node):从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1,其余结点的层次等于其双亲结点的层次加1。
12、堂兄弟(Sibling):同一层的双亲不同的结点。在图1中,G和H互为堂兄弟。
13、树的深度(Depth of Tree):树中结点的最大层次数。在图1中,树的深度为3。
14、无序树(Unordered Tree):树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。
15、有序树(Ordered Tree):树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树,因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。
16、森林(Forest):m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大,但在数据结构中树和森林的概念差别很小。从定义可知,一棵树有根结点和m个子树构成,若把树的根结点删除,则树变成了包含m棵树的森林。当然,根据定义,一棵树也可以称为森林。

 

二叉树

通俗点讲,就是每个节点最多只能分二叉的树(标准的废话,呵),图示如下:

                图3

注:二叉树是有序树,即每个节点下的左右子节点摆放是有顺序的,所以上图中的(a)跟(b)被认为是二棵不同的二叉树!

二叉树有二种经典的特例:完全二叉树(Complete Binary Tree) 与 满二叉树(Full Binary Tree)

                图4 

如上图,所谓满二叉树就是:每个节点都有二个分支,且所有叶节点都处于同一个层次。(很明显,对于一个深度Degree为K的满二叉树,其节点总数为)

所谓完全二叉树就是:叶结点只可能出现在层次最大的两层上,并且某个结点的"左分支"下"子节点"的最大层次与"右分支"下"子节点"的最大层次相等或大1。(再讲得更通俗点:除最后一层外,其它各层都是满的,且最后一层如果出现未满的情况,叶节点只能在左边,即只能空出右节点的位置)

 

二叉树的数学特性:

1、 一棵非空二叉树的第 i 层上最多有个结点(i≥1)。

      比如:以上图满二叉树(a)为例,第一层只有节点a,即2的0次方=1,第二层有B,C二个节点,即2的(2-1)次方为2...

2、若规定空树的深度为0,则深度为k的二叉树最多有个结点(k≥0)。

      这个其实上面在介绍满二叉树的时候,已经说过深度为k的满二叉树,有个节点,这个就是二叉树的节点数极限了.

3、具有n个结点的完全二叉树的深度k为

  比如上图中(a)树的总节点数为15,则深度K = lg(15) + 1 = 3 + 1 = 4

4、对于一棵非空二叉树,如果度为0的结点数目为,度为2的结点数目为,则有

  比如上图中(a)树中度为0的节点为H,I,J,K,L,M共6个(即叶节点),其它节点A,B,C,D,E,F,G都是度为2的结节有7个,有 7 = 6 + 1

5、对于具有n个结点的完全二叉树,如果按照从上到下和从左到右的顺序对所有结点从1开始编号,则对于序号为 i 的结点,有:

                图5
(1)如果 i>1,则序号为i的结点的双亲结点的序号为i/2(“/”表示整除);如果i=1,则该结点是根结点,无双亲结点。

    如上图,随便选一个节点,比如D(序号为4),则D的父节点序号为4/2 = 2,即节点B
(2)如果2i≤n,则该结点的左孩子结点的序号为2i;若2i>n,则该结点无左孩子。

    如上图,随便找个节点5(即E点),则2*5<=10,则E节点的左子节点序号为2*5 = 10即J点
(3)如果2i+1≤n,则该结点的右孩子结点的序号为2i+1;若2i+1>n,则该结点无右孩子。

    如上图,随便找个节点4(即D点),则2*4 + 1<=10,则D点的右子节点序列为2*4 +1 = 9,即I点

 

二叉树的存储结构

1、顺序存储

对于完全二叉树,比如图5的这种,可以表示为

由刚才的数学特性5得知,只要知道了一个节点的序号i,就能确定该节点的父节点,以及左右子节点的序号(如果有左右子节点的话),所以这样就可以将非线性的树型结构,变成一一对应的线性结构.

 

但是非完全二叉树,特性5就不成立了,但我们可以给非完全二叉树添加一些空节点,补成一棵完全二叉树

 

上图中的^代表空节点(NULL)

这样就能使用顺序存储了,但是缺点很明显:浪费了存储空间。

 

2、二叉链表存储

把每个节点Node添加三个基本属性 lChild(左子节点),rChild(右子节点),以及data(节点值),如果左子节点或右子节点为空,则用Null表示(图形中用^表示)

如上图,根据是否有头节点引用,可分为"不带头结点的二叉链表"和"带头结点的二叉链表"

 

3、三叉链表存储

二叉链表存储方式,如果要从某节点向上找父节点或根结点,会很麻烦,所以为了改进,可以给每个Node再增加一个parent父节点属性,就变成下面这种结构

下面来看看代码的实现:(下面只演示了不带头结点的二叉链表实现)

节点类Node.cs(二叉链表的结点)

01 namespace 树与二叉树
02 {
03     public class Node<T>
04     {
05         private T data;
06         private Node<T> lChild;//左子节点
07         private Node<T> rChild;//右子节点
08  
09         public Node(T data, Node<T> ln, Node<T> rn)
10         {
11             this.data = data;
12             this.lChild = ln;
13             this.rChild = rn;
14         }
15  
16         public Node(Node<T> ln, Node<T> rn)
17         {
18             this.data = default(T);
19             this.lChild = ln;
20             this.rChild = rn;
21         }
22  
23         public Node(T data)
24         {
25             this.data = data;
26             lChild = null;
27             rChild = null;
28         }
29  
30         public Node()
31         {
32             data = default(T);
33             lChild = null;
34             rChild = null;
35         }
36  
37         public T Data
38         {
39             get { return this.data; }
40             set { this.data = value; }
41         }
42  
43         public Node<T> LChild
44         {
45             get { return this.lChild; }
46             set { this.lChild = value; }
47         }
48  
49         public Node<T> RChild
50         {
51             get { return this.rChild; }
52             set { this.rChild = value; }
53         }
54     }
55 }

树BiTree.cs

001 namespace 树与二叉树
002 {
003     public class BiTree<T>
004     {
005         private Node<T> root;
006  
007         /// <summary>
008         /// 根节点(属性)
009         /// </summary>
010         public Node<T> Root
011         {
012             get { return root; }
013             set { root = value; }
014         }
015  
016         /// <summary>
017         /// 构造函数
018         /// </summary>
019         public BiTree()
020         {
021             root = null;
022         }
023  
024         /// <summary>
025         /// 构造函数
026         /// </summary>
027         /// <param name="data"></param>
028         public BiTree(T data)
029         {
030             Node<T> p = new Node<T>(data);
031             root = p;
032         }
033  
034         /// <summary>
035         /// 构造函数
036         /// </summary>
037         /// <param name="data"></param>
038         /// <param name="ln"></param>
039         /// <param name="rn"></param>
040         public BiTree(T data, Node<T> ln, Node<T> rn)
041         {
042             Node<T> p = new Node<T>(data, ln, rn);
043             root = p;
044         }
045  
046         /// <summary>
047         /// 判断树是否为空
048         /// </summary>
049         /// <returns></returns>
050         public bool IsEmpty()
051         {
052             if (root == null)
053             {
054                 return true;
055             }
056             else
057             {
058                 return false;
059             }
060         }
061  
062         /// <summary>
063         /// 获取节点p的左子节点
064         /// </summary>
065         /// <param name="p"></param>
066         /// <returns></returns>
067         public Node<T> GetLChild(Node<T> p)
068         {
069             return p.LChild;
070         }
071  
072         /// <summary>
073         /// 获取节点p的右子节点
074         /// </summary>
075         /// <param name="p"></param>
076         /// <returns></returns>
077         public Node<T> GetRChild(Node<T> p)
078         {
079             return p.RChild;
080         }
081  
082         /// <summary>
083         /// 节点p下插入左子节点data
084         /// </summary>
085         /// <param name="data"></param>
086         /// <param name="p"></param>
087         public void InsertL(T data, Node<T> p)
088         {
089             Node<T> tmp = new Node<T>(data);
090             tmp.LChild = p.LChild;
091             p.LChild = tmp;
092         }
093  
094         /// <summary>
095         /// 节点p下插入右子节点data
096         /// </summary>
097         /// <param name="data"></param>
098         /// <param name="p"></param>
099         public void InsertR(T data, Node<T> p)
100         {
101             Node<T> tmp = new Node<T>(data);
102             tmp.RChild = p.RChild;
103             p.RChild = tmp;
104         }
105  
106         /// <summary>
107         /// 删除节点p的左子节点
108         /// </summary>
109         /// <param name="p"></param>
110         /// <returns></returns>
111         public Node<T> DeleteL(Node<T> p)
112         {
113             if ((p == null) || (p.LChild == null))
114             {
115                 return null;
116             }
117             Node<T> tmp = p.LChild;
118             p.LChild = null;
119             return tmp;
120         }
121  
122         /// <summary>
123         /// 删除节点p的右子节点
124         /// </summary>
125         /// <param name="p"></param>
126         /// <returns></returns>
127         public Node<T> DeleteR(Node<T> p)
128         {
129             if ((p == null) || (p.RChild == null))
130             {
131                 return null;
132             }
133             Node<T> tmp = p.RChild;
134             p.RChild = null;
135  
136             return tmp;
137         }
138  
139         /// <summary>
140         /// 判断节点p是否为叶节点
141         /// </summary>
142         /// <param name="p"></param>
143         /// <returns></returns>
144         public bool IsLeaf(Node<T> p)
145         {
146             if ((p != null) && (p.LChild == null) && (p.RChild == null))
147             {
148                 return true;
149             }
150             else
151             {
152                 return false;
153             }
154         }
155     }
156 }

其中向节点B下插入左子节点的算法示意图如下:

 

二叉树的遍历:

对于二叉树而言,有四种经典的遍历方式

1、前序遍历(也称先序遍历)-->即按 node-->lChild-->rChild的顺序来递归遍历(也就是“先自身”-->然后“左子节点”-->最后“右子节点”)

2、中序遍历-->即按 lChild-->node-->rChild(先“左子节点”,然后“自身节点”,最后“右子节点”)的顺序来递归遍历

3、后序遍历-->即按 lChild-->rChild-->node(先“左子节点”,然后“右子节点”,最后“自身节点”)的顺序来递归遍历

4、层顺遍历--这个不解释,字面意思理解就行

ok,最后来一段代码验证+测试一把:

001 using System;
002 using System.Collections;
003 using System.Collections.Generic;
004  
005 namespace 树与二叉树
006 {
007     class Program
008     {
009         static void Main(string[] args)
010         {
011             #region //构造树
012             BiTree<string> tree = new BiTree<string>("A");
013             Node<string> root = tree.Root;
014             tree.InsertL("B", root);
015             tree.InsertR("C", root);
016  
017             Node<string> b = root.LChild;
018             Node<string> c = root.RChild;
019  
020             tree.InsertL("D", b);
021             tree.InsertR("E", b);
022  
023             tree.InsertL("F", c);
024             tree.InsertR("G", c);
025  
026             Node<string> d = b.LChild;
027             Node<string> e = b.RChild;
028  
029             tree.InsertL("H", d);
030             tree.InsertR("I", d);
031             tree.InsertL("J", e);
032             #endregion
033  
034  
035  
036             Console.WriteLine("前序遍历开始>>>\n");
037             //前序遍历
038             PreOrder(root);
039  
040             Console.WriteLine("\n------------------------\n");
041  
042  
043             Console.WriteLine("中序遍历开始>>>\n");
044             //中序遍历
045             InOrder(root);
046  
047             Console.WriteLine("\n------------------------\n");
048             Console.WriteLine("后序遍历开始>>>\n");
049             //后序遍历
050             PostOrder(root);
051  
052  
053             Console.WriteLine("\n------------------------\n");
054             Console.WriteLine("层序遍历开始>>>\n");
055             //后序遍历
056             LevelOrder(root);
057  
058             Console.Read();
059         }
060  
061         /// <summary>
062         /// 前序遍历(即 root-->left-->right )
063         /// </summary>
064         /// <param name="root"></param>
065         static void PreOrder(Node<string> root)
066         {
067             if (root != null)
068             {
069                 //先处理root
070                 Console.Write("{0} ", root.Data);
071  
072                 //再处理root的左子节点
073                 PreOrder(root.LChild);
074  
075                 //再处理root的右子节点
076                 PreOrder(root.RChild);
077             }        
078  
079              
080         }
081  
082         /// <summary>
083         /// 中序遍历(left-->root-->right)
084         /// </summary>
085         /// <param name="root"></param>
086         static void InOrder(Node<string> root)
087         {
088             if (root == null)
089             {
090                 return;
091             }
092  
093             //先左子节点
094             InOrder(root.LChild);
095  
096             //再根节点
097             Console.Write("{0} ", root.Data);
098  
099             //再右子节点
100             InOrder(root.RChild);
101         }
102  
103         /// <summary>
104         /// 后序遍历
105         /// </summary>
106         /// <param name="root"></param>
107         static void PostOrder(Node<string> root)
108         {
109             if (root == null)
110             {
111                 return;
112             }
113  
114             PostOrder(root.LChild);
115             PostOrder(root.RChild);
116             Console.Write("{0} ", root.Data);
117         }
118  
119         /// <summary>
120         /// 层顺遍历
121         /// </summary>
122         /// <param name="root"></param>
123         static void LevelOrder(Node<string> root)
124         {
125             if (root != null)
126             {
127                 Queue<Node<string>> q = new Queue<Node<string>>();
128                  
129                 q.Enqueue(root);
130  
131                 while (q.Count>0)
132                 {
133                     Node<string> tmp = q.Dequeue();
134  
135                     //先处理根节点
136                     Console.Write("{0} ", tmp.Data);
137  
138                     if (tmp.LChild != null)
139                     {
140                         //左子节点入队
141                         q.Enqueue(tmp.LChild);
142                     }
143  
144                     if (tmp.RChild != null)
145                     {
146                         //右子节点入队
147                         q.Enqueue(tmp.RChild);
148                     }
149                 }
150             }
151         }
152     }
153 }

运行结果:

前序遍历开始>>>

A B D H I E J C F G
------------------------

中序遍历开始>>>

H D I B J E A F C G
------------------------

后序遍历开始>>>

H I D J E B F G C A
------------------------

层序遍历开始>>>

A B C D E F G H I J

作者:菩提树下的杨过
出处:http://yjmyzz.cnblogs.com
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
  评论这张
 
阅读(977)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017