树 / iVAN

树

QueueNode.h

template<typename Type> class LinkQueue;

template<typename Type> class QueueNode{
private:
	friend class LinkQueue<Type>;
	QueueNode(const Type item,QueueNode<Type> *next=NULL)
		:m_data(item),m_pnext(next){}
private:
	Type m_data;
	QueueNode<Type> *m_pnext;
};

LinkQueue.h

#include "QueueNode.h"

template<typename Type> class LinkQueue{
public:
	LinkQueue():m_prear(NULL),m_pfront(NULL){}
	~LinkQueue(){
		MakeEmpty();
	}
	void Append(const Type item);
	Type Delete();
	Type GetFront();
	void MakeEmpty();
	bool IsEmpty() const{
		return m_pfront==NULL;
	}
	void Print();

private:
	QueueNode<Type> *m_prear,*m_pfront;
};

template<typename Type> void LinkQueue<Type>::MakeEmpty(){
	QueueNode<Type> *pdel;
	while(m_pfront){
		pdel=m_pfront;
		m_pfront=m_pfront->m_pnext;
		delete pdel;
	}
}

template<typename Type> void LinkQueue<Type>::Append(const Type item){
	if(m_pfront==NULL){
		m_pfront=m_prear=new QueueNode<Type>(item);
	}
	else{
		m_prear=m_prear->m_pnext=new QueueNode<Type>(item);
	}
}

template<typename Type> Type LinkQueue<Type>::Delete(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	QueueNode<Type> *pdel=m_pfront;
	Type temp=m_pfront->m_data;
	m_pfront=m_pfront->m_pnext;
	delete pdel;
	return temp;
}

template<typename Type> Type LinkQueue<Type>::GetFront(){
	if(IsEmpty()){
		cout<<"There is no element!"<<endl;
		exit(1);
	}
	return m_pfront->m_data;
}

template<typename Type> void LinkQueue<Type>::Print(){
	QueueNode<Type> *pmove=m_pfront;
	cout<<"front";
	while(pmove){
		cout<<"--->"<<pmove->m_data;
		pmove=pmove->m_pnext;
	}
	cout<<"--->rear"<<endl<<endl<<endl;
}

TreeNode.h

template<typename Type> class Tree;

template<typename Type> class TreeNode{
public:
	friend class Tree<Type>;

private:
	Type m_data;
	TreeNode<Type> *m_pfirst,*m_pnext;
	TreeNode():m_pfirst(NULL), m_pnext(NULL){}
	TreeNode(Type item, TreeNode<Type> *first = NULL, TreeNode<Type> *next = NULL)
		:m_data(item), m_pfirst(first), m_pnext(next){}
};

Tree.h

#include "TreeNode.h"
#include "LinkQueue.h"

template<typename Type> class Tree{
public:
    Tree():m_proot(NULL), m_pcurrent(NULL){}
public:
    TreeNode<Type> *GetCurrent(){	//Get the current node
        return m_pcurrent;
    }
    void SetCurrent(TreeNode<Type> *current){	//set the current node
        m_pcurrent = current;
    }
    bool Insert(Type item);		//insert an new node to current node
    void Remove(Type item);		//delete the node whose data is equal to item
    void Remove(TreeNode<Type> *current);	//delete the node
    bool Find(Type item);		//find the node whose data is equal to item
    void PrintChild(TreeNode<Type> *current);	//print the child tree
    TreeNode<Type> *Parent(TreeNode<Type> *current);	//get the parent

    void Print();				//print the tree
    void PreOrder(TreeNode<Type> *root);	//ordering the tree by visiting the root first
    void PostOrder(TreeNode<Type> *root);	//ordering the tree by visiting the root last
    void LevelOrder(TreeNode<Type> *root);	//ordering the tree by level
    void PreOrder();
    void PostOrder();
    void LevelOrder();

private:
   TreeNode<Type> *m_proot,*m_pcurrent;
    bool Find(TreeNode<Type> *root, Type item);
    void Remove(TreeNode<Type> *root, Type item);
    TreeNode<Type> *Parent(TreeNode<Type> *root, TreeNode<Type> *current);
    void Print(TreeNode<Type> *start, int n=0);
};

template<typename Type> bool Tree<Type>::Insert(Type item){
    TreeNode<Type> *newnode = new TreeNode<Type>(item);
    if (NULL == newnode){
        cout << "Application Error!" <<endl;
        exit(1);
    }
    if (NULL == m_proot){
        m_proot = newnode;
        m_pcurrent = m_proot;
        return 1;
    }
    if (NULL == m_pcurrent){
        cerr << "insert error!" <<endl;
        return 0;
    }

    if(NULL == m_pcurrent->m_pfirst){
        m_pcurrent->m_pfirst = newnode;
        m_pcurrent = newnode;
        return 1;
    }
    TreeNode<Type> *pmove = m_pcurrent->m_pfirst;
    while(pmove->m_pnext){
        pmove = pmove->m_pnext;
    }
    pmove->m_pnext = newnode;
    m_pcurrent = newnode;
    return 1;

}

template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *current){
    if(NULL == current){
        return;
    }
    TreeNode<Type> *temp = Parent(current);
    if(NULL == temp){
        TreeNode<Type> *pmove = current->m_pfirst;
        if(NULL != pmove->m_pfirst){
            pmove=pmove->m_pfirst;
            while(pmove->m_pnext){
                pmove = pmove->m_pnext;
            }
            pmove->m_pnext = current->m_pfirst->m_pnext;
            current->m_pfirst->m_pnext = NULL;
        }
        else{
            pmove->m_pfirst = pmove->m_pnext;
        }
        m_proot = current->m_pfirst;
    }
    else{
        if(temp->m_pfirst == current){
            TreeNode<Type> *pmove = current->m_pfirst;
            if (pmove){
                while (pmove->m_pnext){
                    pmove = pmove->m_pnext;
                }
                pmove->m_pnext = current->m_pnext;
            }
            else{
                current->m_pfirst = current->m_pnext;
            }

        }
        else{
            TreeNode<Type> *pmove = temp->m_pfirst;
            while(pmove->m_pnext != current){
                pmove = pmove->m_pnext;
            }
            pmove->m_pnext = current->m_pnext;
            while(pmove->m_pnext){
                pmove = pmove->m_pnext;
            }
            pmove->m_pnext = current->m_pfirst;
        }
    }
    delete current;
}

template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *root, Type item){
    if(NULL == root){
        return;
    }
    if(root->m_pfirst){
        TreeNode<Type> *pmove=root->m_pfirst;
        while(pmove){
            Remove(pmove, item);
            pmove = pmove->m_pnext;
        }
    }
    if(root->m_data == item){
        Remove(root);
    }

}
template<typename Type> void Tree<Type>::Remove(Type item){
    return Remove(m_proot, item);
}

template<typename Type> TreeNode<Type>* Tree<Type>::Parent(
    TreeNode<Type> *root, TreeNode<Type> *current){
        if(NULL == root){
            return NULL;
        }
        TreeNode<Type> *pmove=root->m_pfirst,*temp;
        if(NULL != pmove){
            while(pmove){
                if(pmove == current){
                    return root;
                }
                pmove = pmove->m_pnext;
            }
        }
        pmove = root->m_pfirst;
        while(pmove){
            temp = Parent(pmove, current);
            if(temp){
                return temp;
            }
            pmove = pmove->m_pnext;
        }
        return NULL;
}

template<typename Type> TreeNode<Type>* Tree<Type>::Parent(TreeNode<Type> *current){
    return Parent(m_proot,current);
}

template<typename Type> void Tree<Type>::PrintChild(TreeNode<Type> *current){
    TreeNode<Type> *pmove = current->m_pfirst;
    cout<<"first";
    if(NULL != pmove){
        cout<<"--->"<<pmove->m_data;
    }
    while(pmove->m_pnext){
        cout<<"--->"<<pmove->m_data;
        pmove = pmove->m_pnext;
    }
}

template<typename Type> bool Tree<Type>::Find(TreeNode<Type> *root, Type item){
    if (root->m_data == item){
        return 1;
    }
    if (NULL == root){
        return 0;
    }
    TreeNode<Type> *pmove=root->m_pfirst;
    if (NULL == pmove){
        return 0;
    }
    while (pmove){
        if (Find(pmove, item)){
            return 1;
        }
        pmove = pmove->m_pnext;
    }
    return 0;
}

template<typename Type> bool Tree<Type>::Find(Type item){
    return Find(m_proot,item);
}

template<typename Type> void Tree<Type>::Print(TreeNode<Type> *start, int n = 0){
    if (NULL == start){
        for (int i=0; i<n; i++){
            cout << "     ";
        }
        cout << "NULL" << endl;
        return;
    }
    TreeNode<Type> *pmove = start->m_pfirst;
    Print(pmove, n+1);

    for (int i=0; i<n; i++){
        cout << "     ";
    }
    cout << start->m_data << "--->" <<endl;

    if (NULL == pmove){
        return;
    }
    pmove = pmove->m_pnext;
    while (pmove){
        Print(pmove, n+1);
        pmove = pmove->m_pnext;
    }
}

template<typename Type> void Tree<Type>::Print(){
    Print(m_proot);
}

template<typename Type> void Tree<Type>::PreOrder(TreeNode<Type> *root){
    if (NULL == root){
        return;
    }
    cout << root->m_data;
    TreeNode<Type> *pmove = root->m_pfirst;
    while (pmove){
        PreOrder(pmove);
        pmove = pmove->m_pnext;
    }
}

template<typename Type> void Tree<Type>::PostOrder(TreeNode<Type> *root){
    if (NULL == root){
        return;
    }
    TreeNode<Type> *pmove = root->m_pfirst;
    while (pmove){
        PostOrder(pmove);
        pmove = pmove->m_pnext;
    }
    cout << root->m_data;
}

template<typename Type> void Tree<Type>::PreOrder(){
    PreOrder(m_proot);
}

template<typename Type> void Tree<Type>::PostOrder(){
    PostOrder(m_proot);
}

template<typename Type> void Tree<Type>::LevelOrder(TreeNode<Type> *root){	//using queue
    LinkQueue<TreeNode<Type> *> queue;
    TreeNode<Type> *pmove, *ptemp;
    if (root != NULL){
        queue.Append(root);
        while (!queue.IsEmpty()){
            ptemp = queue.Delete();
            cout << ptemp->m_data;
            pmove = ptemp->m_pfirst;
            while(pmove){
                queue.Append(pmove);
                pmove = pmove->m_pnext;
            }
        }
    }
}

template<typename Type> void Tree<Type>::LevelOrder(){
    LevelOrder(m_proot);
}

树的相关文章

不用递归实现论坛树型结构的算法

递归|树型结构|算法 <jsp:useBean id="mybbs" scope="session" class="netzero.mydb" /> <%@ page contentType="text/html;charset=gb2312" %> <%@ page import="java.io.*" %> <%@ page import="java.

Photoshop给树下的美女加上唯美的橙黄色

树边,树下的人物图片调色需要处理好高光区域的颜色,可以把边缘区域单独选出来,用模糊滤镜模糊处理,然后把混合模式改为"柔光",这样画面就会梦幻,柔美很多. 原图最终效果

dtree和jquery构建树型结构

对于小型的树型应用来说,dtree是一个不错的选择. 先看一眼dtree给的例子构造静态树首先引入css文件和js文件 <link rel="StyleSheet" href="dtree.css" type="text/css" /> <script type="text/javascript" src="dtree.js"></script> 构造静态树其实很简单

题意:给出某项斐波那契数的前几位,让输出最小的一项前缀为这个串的项数. 先高精度算出前100000项斐波那契的前50位.并把前40位存进字典树预处理一下.字典树节点值存为第几项.然后输入字符串直接查找. #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 50 int fib[3][N+1]; cla

哈夫曼（huffman）树和哈夫曼编码

哈夫曼树哈夫曼树也叫最优二叉树(哈夫曼树) 问题:什么是哈夫曼树? 例:将学生的百分制成绩转换为五分制成绩:≥90 分: A,80-89分: B,70-79分: C,60-69分: D,<60分: E. if (a < 60){ b = 'E'; } else if (a < 70) { b = 'D'; } else if (a<80) { b = 'C'; } else if (a<90){ b = 'B'; } else { b = 'A'; } 判别树:用于描

将多个路径字符串转换成XML文档树

假设有下面的字符串: ? 1 2 3 4 5 6 7 /home/usr/abc/def/文本.txt /home/usr/desktop/音乐.mp3 /etc/init.d/mysql/mysql /etc/profile /tmp/垃圾.tmp /usr/bin/open-jdk7/java ... 给定一个根节点名字root和叶子节点名字leaf,如何将它们转换成一颗像下面这样的XML文档树呢? ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

asp.net递归生成XML树的示例

asp.net|xml|生成xml|示例|递归 asp.net递归生成XML树的示例代码: 以下是引用片段://CDepartmentInfo 类别实体类 //sjid :与大类别关联ID //space:只是一个标记 //strOpinion用来存放类名 string sjid = "0"; string space = "+"; string strOpinion = ""; string paths = @"E:\test&qu

HDU2527 构建哈夫曼树的灵巧运用

上课老师说了知道哈夫曼树叶子不构图求二叉树的权就是在构造哈夫曼树的时候运用构图的方法把每个结点的值加起来就是该数的权证明 W=∑叶子权*该叶子层数除了叶子的结点和就是这个树的权构造一个树就知道了结点的权肯定是下一层结点的和就好像 W=∑叶子权*该叶子层数这个公式运用了乘法分配律一样= = #include <iostream> #include<cstdio> #include<cstring> #include<algorithm

ExtJs2.0学习系列(14)--Ext.TreePanel之第三式(可增删改的树)

继续tree的learn! 今天就来个可增删改的树吧,操作数据库就使用比较方便的Linq,无非就是增删改! LinqData.dbml: html代码: <body> <div id="container" style="float:left; margin-right:10px;"> </div> <iframe name="mainFrame" id="mainFrame" src

纸上谈兵: 树, 二叉树, 二叉搜索树[转]

树的特征和定义树(Tree)是元素的集合.我们先以比较直观的方式介绍树.下面的数据结构是一个树: 树有多个节点(node),用以储存元素.某些节点之间存在一定的关系,用连线表示,连线称为边(edge).边的上端节点称为父节点,下端称为子节点.树像是一个不断分叉的树根. 每个节点可以有多个子节点(children),而该节点是相应子节点的父节点(parent).比如说,3,5是6的子节点,6是3,5的父节点:1,8,7是3的子节点, 3是1,8,7的父节点.树有一个没有父节点的节点,称为根节点(

树