数据结构 第五章 树和二叉树

2022-11-29 14:45:52 浏览数 (1)

树：n（n≥0）个结点的有限集合。 当n＝0时，称为空树； 任意一棵非空树满足以下条件： ⑴ 有且仅有一个特定的称为根的结点； ⑵ 当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。 结点的度：结点所拥有的子树的个数。 树的度：树中各结点度的最大值。 叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。 孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点； 兄弟：具有同一个双亲的孩子结点互称为兄弟。 路径：如果树的结点序列n1, n2, …, nk有如下关系：结点ni是ni 1的双亲（1<=i<k），则把n1, n2, …, nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。 祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。 结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k 1层。 树的深度：树中所有结点的最大层数，也称高度。 层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。 有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。 森林：m (m≥0)棵互不相交的树的集合。 同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。 前序遍历：树的前序遍历操作定义为： 若树为空，不进行遍历；否则 ⑴ 访问根结点； ⑵ 按照从左到右的顺序前序遍历根结点的每一棵子树。 后序遍历：树的后序遍历操作定义为： 若树为空，则遍历结束；否则 ⑴ 按照从左到右的顺序后序遍历根结点的每一棵子树； ⑵ 访问根结点。 层序遍历：树的层序遍历操作定义为： 从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

树的存储结构

1.双亲表示法： 基本思想： 用一维数组来存储树的各个结点（一般按层序存储）， 数组中的一个元素对应树中的一个结点， 每个结点记录两类信息：结点的数据信息以及该结点的双亲在数组中的下标。 顺序存储：本质上是静态指针 双亲表示法 双亲、孩子表示法 链式存储： 多重链表示法 孩子链表表示法 孩子兄弟表示法 二叉树 二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 斜树 1 .所有结点都只有左子树的二叉树称为左斜树； 2 .所有结点都只有右子树的二叉树称为右斜树； 3.左斜树和右斜树统称为斜树。 满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。 完全二叉树 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。 完全二叉树的特点：

叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部； 完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。 深度为k的完全二叉树在k-1层上一定是满二叉树。

二叉树基本操作

代码语言：javascript复制
#include <iostream>

using namespace std;
template <class T>
struct node
{
    T data;
    node<T> *lchild,*rchild;
};
template <class T>
class bitree{
public:
    bitree(){root=creat();}
    ~bitree(){release(root);}
    void preorder(){preorder(root);}
    void inorder(){inorder(root);}
    void postorder(){postorder(root);}
    void levelorder();
    void qianorder(){qianorder(root);}
    void zhongorder(){zhongorder(root);}
    void PostOrder();
private:
    node<T> *creat();
    node<T> *root;
    void release(node<T> *bt);
    void preorder(node<T> *bt);
    void inorder(node<T> *bt);
    void postorder(node<T> *bt);
    void qianorder(node<T> *bt);
    void zhongorder(node<T> *bt);
};
template <typename T>
struct element
{
  node<T> *ptr;
  int flag;
};

//非递归后序遍历
template <class T>
void bitree<T> :: PostOrder( )
{
	node<T> *bt = root;
	element<T> S[100];                  //顺序栈，最多100个元素
	int top = -1;                       //顺序栈初始化
	while (bt != NULL || top != -1)      //两个条件都不成立才退出循环
	{
		while (bt != NULL)
		{
			top  ;
			S[top].ptr = bt; S[top].flag = 1;      //bt连同标志flag入栈
			bt = bt->lchild;
		}
		while (top != -1 && S[top].flag == 2)
		{
			bt = S[top--].ptr;
			cout << bt->data;
		}
		if (top != -1) {
			S[top].flag = 2;
			bt = S[top].ptr->rchild;
		}
		else
			bt = NULL;
	}
}

//非递归中序遍历
template <class T>
void bitree<T>::zhongorder(node<T> *bt)
{
    node<T> *a[100];
    int top=-1;
    while(bt!=NULL||top!=-1)
    {
        while(bt!=NULL)
        {
            a[  top]=bt;
            bt=bt->lchild;
        }
        while(top!=-1)
        {
            bt=a[top--];
            cout<<bt->data;
            bt=bt->rchild;
        }
    }
}
//非递归前序遍历
template <class T>
void bitree<T>::qianorder(node<T> *bt)
{
    node<T> *a[100];
    int top=-1;
    while(bt!=NULL||top!=-1)
    {
        while(bt!=NULL)
        {
            cout<<bt->data;
            a[  top]=bt;
            bt=bt->lchild;
        }
        while(top!=-1)
        {
            bt=a[top--];
            bt=bt->rchild;
        }
    }
}
template <class T>
node<T> *bitree<T>::creat()
{
    node<T> *bt;
    char ch;
    cin>>ch;
    if(ch!='#')
    {
        bt=new node<T>;
        bt->data=ch;
        bt->lchild=creat();
        bt->rchild=creat();
    }else bt=NULL;
    return bt;
}
//析构
template <class T>
void bitree<T>::release(node<T> *bt)
{
    if(bt!=NULL)
    {
        release(bt->lchild);
        release(bt->rchild);
        delete bt;
    }
    else return;
}
//前序遍历
template <class T>
void bitree<T>::preorder(node<T> *bt)
{
    if(bt!=NULL)
    {
        cout<<bt->data;
        preorder(bt->lchild);
        preorder(bt->rchild);
    }
    else
        return;
}
//中序遍历
template <class T>
void bitree<T>::inorder(node<T> *bt)
{
    if(bt!=NULL)
    {
        inorder(bt->lchild);
        cout<<bt->data;
        inorder(bt->rchild);
    }
    else return;
}
//后序遍历
template <class T>
void bitree<T>::postorder(node<T> *bt)
{
    if(bt!=NULL)
    {
        postorder(bt->lchild);
        postorder(bt->rchild);
        cout<<bt->data;
    }
    else return;
}
template <class T>
void bitree<T>::levelorder()
{
    node<T> *q[100],*p=NULL;
    int front1=-1,rear=-1;
    if(root==NULL)return;
    q[  rear]=root;
    while(front1!=rear)
    {
        p=q[  front1];
        cout<<p->data<<" ";
        if(p->lchild!=NULL)q[  rear]=p->lchild;
        if(p->rchild!=NULL)q[  rear]=p->rchild;
    }
}
int main()
{
    char ch;
    do
    {
        bitree<char> t;
        t.preorder();
        cout<<endl;
        t.inorder();
        cout<<endl;
        t.postorder();
        cout<<endl;
        t.levelorder();
        cout<<endl;
        cin>>ch;
        t.qianorder();
        t.zhongorder();
        t.PostOrder();
    }while(ch=='Y');
    return 0;
}

树中结点数目

代码语言：javascript复制
template<class T>
int BiTree<T>::count(BiNode<T>* root){
	int number=0;

	if (root==NULL)
		number=0;
	else
		number=count(root->lchild) count(root->rchild) 1;
	return number;
}

叶子结点数目

代码语言：javascript复制
template<class T>
int BiTree<T>::leafcount(BiNode<T>* root){
	int number=0;

	if (root==NULL)
		number=0;
	else if(root->lchild==NULL && root->rchild==NULL)
		number=1;
	else
	    number=leafcount(root->lchild) leafcount(root->rchild);
	return number;
}

树的高度

代码语言：javascript复制
template<typename T> 
 int BiTree<T>::cal_height(BiTreeNode<T> * root){
	int lheight=0,rheight=0;
	if (root==0)  	 return 0；
	lheight=cal_height(root->lchild);
	rheight=cal_height(root->rchild);
	if (lheight>rheight)	return lheight 1;
	else 		return rheight 1;
}

三叉链表 在二叉链表的基础上增加了一个指向双亲的指针域。

代码语言：javascript复制
结点数据类型声明：
template<class T>
struct Node
{
	T data;
	Node<T> * lchild, *rchild,*parent;
};

按前序扩展遍历序列输入输入节点的值 如果输入节点之为“#”,则建立一棵空的子树 否则，根结点申请空间，将输入值写入数据域中，同时将三个指针赋空值 以相同方法的创建根节点的左子树，并设置子树的根的parent 以相同的方法创建根节点的右子树，并设置子树的根的parent 递归方法

代码语言：javascript复制
template <class T>
BiNode<T> * BiTree<T>::Creat(BiNode<T> * &root ,BiNode<T> *parent){
	T ch;
	cout<<"请输入创建一棵二叉树的结点数据"<<endl;
	cin>>ch;
    if (ch=="#") root = NULL;
    else{ 
	     root = new BiNode<T>;       //生成一个结点
          root->data=ch;
	     root->parent=parent;
         Creat(root->lchild,root );    //递归建立左子树
         Creat(root->rchild,root);    //递归建立右子树
    } 
    return root;
}
template<class T>
BiTree<T>::BiTree( int i)
{
	number=0;
	Creat(root,NULL);

}

树和二叉树之间的对应关系

1.兄弟间加线 2.保留双亲与第一孩子连线,删去与其他孩子的连线. 3.顺时针转动,使之层次分明.

森林转换为二叉树

⑴ 将森林中的每棵树转换成二叉树； ⑵ 从第二棵二叉树开始， 依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子， 当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

二叉树转换为树或森林

⑴ 加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来； ⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线； ⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。 哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。

哈夫曼树的特点：

权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点. 哈夫曼算法基本思想： ⑴ 初始化：由给定的n个权值{w1，w2，…，wn}构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合F＝{T1，T2，…，Tn}； ⑵ 选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和； ⑶ 删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中； ⑷ 重复⑵、⑶两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。

代码语言：javascript复制
void HuffmanTree(element huffTree[ ], int w[ ], int n ) {
    for (i=0; i<2*n-1; i  ) {
       huffTree [i].parent= -1;
       huffTree [i].lchild= -1;
       huffTree [i].rchild= -1;   
    }
    for (i=0; i<n; i  ) 
       huffTree [i].weight=w[i];
    for (k=n; k<2*n-1; k  ) {
        Select(huffTree, &i1, &i2); 
        huffTree[k].weight=huffTree[i1].weight huffTree[i2].weight;
        huffTree[i1].parent=k;     
        huffTree[i2].parent=k; 
        huffTree[k].lchild=i1;    
        huffTree[k].rchild=i2;
    }
}

线索二叉树

二叉树的遍历运算是将二叉树中结点按一定规律线性化的过程。 当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在遍历序列中的前驱和后继信息。 要得到这些信息可采用以下两种方法： 第一种方法是将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时间； 第二种方法是充分利用二叉链表中的空链域， 将遍历过程中结点的前驱、 后继信息保存下来。 线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索； 线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化； 线索二叉树：加上线索的二叉树称为线索二叉树。

代码语言：javascript复制
//线索链表结点结构
enum flag {Child, Thread}; 
template  <class T>
struct ThrNode
{
     T data;
     ThrNode<T>  *lchild, *rchild;
     flag ltag, rtag;
};
//中序线索链表类的声明
template <class T>
class InThrBiTree{    
   public:
        InThrBiTree();     
         ~ InThrBiTree( );    
        ThrNode *Next(ThrNode<T> *p); 
        void InOrder(ThrNode<T> *root); 
   private:
        ThrNode<T> *root;  
        ThrNode<T> *  Creat(); 
        void ThrBiTree(ThrNode<T> *root);
};
//建立带有标记为的二叉链树
template <class T>ThrNode<T>* InThrBiTree<T>::Creat( ){
    ThrNode<T> *root;
    T ch;
    cout<<"请输入创建一棵二叉树的结点数据"<<endl;
    cin>>ch;
    if (ch=="#") root = NULL;
    else{	
         root=new ThrNode<T>;    
         root->data = ch;
         root->ltag = Child; root->rtag = Child;
         root->lchild = Creat( );
         root->rchild = Creat( ); 
    } 
	return root;
}
//线索化
template <class T>  void ThrBiTree<T>::ThrBiTree (ThrNode<T>*root) {
      if (root==NULL) return;         //递归结束条件
   
      ThrBiTree(root->lchild); 	
if (!root->lchild){             //对root的左指针进行处理
        root->ltag = Thread;   
        root->lchild = pre;        //设置pre的前驱线索
   }
    if (!root->rchild) root->rtag = Thread; 

  if(pre != NULL){
       if (pre->rtag==Thread)  pre->rchild = root; 
  }
   pre = root;
   ThrBiTree(root->rchild);
}
//线索二叉树的建立
ThrNode<T>* pre = NULL
template <class T>
InThrBiTree<T>::InThrBiTree( )
{ 
	//ThrNode<T>* pre = NULL;
	this->root = Creat( );    
	ThrBiTree(root);
}
//中序遍历中序线索树
template <class T> 
void InThrBiTree<T>::InOrder(ThrNode<T> *root){
    ThrNode<T>* p = root;
    if (root==NULL)  return; 
    while (p->ltag==Child)   {       p = p->lchild;    }
    cout<<p->data<<" ";
    while (p->rchild!=NULL) {
        p = Next(p);
        cout<<p->data<<" ";
    }
    cout<<endl;
}
编程算法 二叉树 存储

0 人点赞