XIAOSUO 记录个人学习的足迹

一、顺序存储结构表示二叉树

　　所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。
　　依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系。
　　　　　　
　　对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。
　　　　
二、二叉链表结构表示二叉树

　　二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链表来指示着元素的逻辑关系。
　　　　
　　链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。下图为一棵二叉树的二叉链表示。
　　　　
三、三叉链表结构表示二叉树
　　在三叉链表存储中，每个结点由四个域组成 。parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点。下图为一棵二叉树的三叉链表示。
　　　　
四、二叉树的实现**

　　尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还要节省空间。因此二叉链表是最常用的二叉树存储方法。下面将介绍二叉链表存储方法的二叉树实现。

　　首先我们来看下结点结构的代码：

public class Node<T>
{
	private T data; //数据域 
	private Node<T> lChild; //左孩子 
	private Node<T> rChild; //右孩子 
	//构造函数
	public Node(T val, Node<T> lp, Node<T> rp)
	{
		data = val;
		lChild = lp;
		rChild = rp;
	}
	//构造函数
	public Node(Node<T> lp, Node<T> rp)
	{
		data = default(T);
		lChild = lp;
		rChild = rp;
	}
	//构造函数
	public Node(T val)
	{
		data = val;
		lChild = null;
		rChild = null;
	}

	//构造函数
	public Node()
	{
		data = default(T);
		lChild = null;
		rChild = null;
	}
	//数据属性 
	public T Data
	{
		get
		{
			return data;
		}
		set
		{
			value = data;
		}
	}
	//左孩子属性 
	public Node<T> LChild
	{
		get
		{
			return lChild;
		}
		set
		{
			lChild = value;
		}
	}
	//右孩子属性 
	public Node<T> RChild
	{
		get
		{
			return rChild;
		}
		set
		{
			rChild = value;
		}
	}
}

下面只介绍不带头结点的二叉树的二叉链表的类LinkBiTree。LinkBiTree类只有一个成员字段head表示头引用。以下是LinkBiTree类的实现

public class LinkBiTree<T>
{
	private Node<T> head; //头引用 
	//头引用属性 
	public Node<T> Head
	{
		get
		{
			return head;
		}
		set
		{
			head = value;
		}
	}
	//构造函数 
	public LinkBiTree()
	{
		head = null;
	}
	//构造函数 
	public LinkBiTree(T val)
	{
		Node<T> p = new Node<T>(val);
		head = p;
	}
	//构造函数 
	public LinkBiTree(T val, Node<T> lp, Node<T> rp)
	{
		Node<T> p = new Node<T>(val, lp, rp);
		head = p;
	}
	//判断是否是空二叉树 
	public bool IsEmpty()
	{
		if (head == null)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	//获取根结点 
	public Node<T> Root()
	{
		return head;
	}

	//获取结点的左孩子结点 
	public Node<T> GetLChild(Node<T> p)
	{
		return p.LChild;
	}
	//获取结点的右孩子结点 
	public Node<T> GetRChild(Node<T> p)
	{
		return p.RChild;
	}
	//将结点p的左子树插入值为val的新结点， 
	//原来的左子树成为新结点的左子树 
	public void InsertL(T val, Node<T> p)
	{
		Node<T> tmp = new Node<T>(val);
		tmp.LChild = p.LChild;
		p.LChild = tmp;
	}
	//将结点p的右子树插入值为val的新结点， 
	//原来的右子树成为新结点的右子树 
	public void InsertR(T val, Node<T> p)
	{
		Node<T> tmp = new Node<T>(val);
		tmp.RChild = p.RChild;
		p.RChild = tmp;
	}
	//若p非空，删除p的左子树 
	public Node<T> DeleteL(Node<T> p)
	{
		if ((p == null) || (p.LChild == null))
		{
			return null;
		}
		Node<T> tmp = p.LChild;
		p.LChild = null;
		return tmp;
	}
	//若p非空，删除p的右子树 
	public Node<T> DeleteR(Node<T> p)
	{
		if ((p == null) || (p.RChild == null))
		{
			return null;
		}
		Node<T> tmp = p.RChild;
		p.RChild = null;
		return tmp;
	}
	//编写算法,在二叉树中查找值为value的结点 
	public Node<T> Search(Node<T> root, T value)
	{
		Node<T> p = root;

		if (p == null)
		{
			return null;
		}

		if (!p.Data.Equals(value))
		{
			return p;
		}

		if (p.LChild != null)
		{
			return Search(p.LChild, value);
		}

		if (p.RChild != null)
		{
			return Search(p.RChild, value);
		}

		return null;
	}
	//判断是否是叶子结点 
	public bool IsLeaf(Node<T> p)
	{
		if ((p != null) && (p.LChild == null) && (p.RChild == null))
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}