什么是树？——数是节点有限集合

　　

孩子：在上图中BCD都是A的孩子，EF是B的孩子，GH是D的孩子
双亲：A是BCD的双亲，B是EF的双亲，D是GH的双亲，注意这里双亲是指一个节点而非两个。
度：节点的度等于节点的孩子数。A的度为3，B的度为2，D的度为2，CEFGH度都是0。
叶子：终端节点就是叶子。CEFGH
根：非终端节点。ABD
有序树：举例来说：如果EF不可以换顺序，则为有序树。
无序树：相对于有序树。
祖先：当前节点，一直向上所路过的所有节点直到根都是该节点祖先。
子孙：当前节点，向下的所有节点，都是该节点的子孙。
深度：节点深度为该节点所在层数；树的深度为该树的最大深度。
森林：多颗独立的树在一起就成了森林。
二叉树：所有节点的度都小于等于2。
二叉树的遍历：前序遍历，中序遍历，后序遍历。

　　

记忆口诀：根左右、左根右、左右根。
树的应用：压缩软件、人机对战。

二叉树的实现：

1.数组实现
2.链表实现
第一种数组实现的方式较为简单

/*****************************************/
/* 二叉树（数组表示） 

    关于数据与树之间的算法转换 

    int tree[n] 3 5 8 2 6 9 7             

                    3(0)

            5(1)              8(2)

      2(3)      6(4)     9(5)         7(6)


    结论：
        父亲节点下标*2+1 为该节点左孩子的下标 
        父亲节点下标*2+2 为该节点右孩子的下标   
*/ 

当节点不存在时有些不好表达，如果用0来代表无此节点，当存放的数据就是0时便会影响树的操作。
第二种链表实现

/********************************************
    节点要素： 索引   数据  左孩子指针   右孩子指针  父节点指针 
        tree[n] 3 5 8 2 6 9 7   


                    3(0)

            5(1)              8(2)

      2(3)      6(4)     9(5)         7(6)

      下标来表示遍历顺序： 
      前序：0 1 3 4 2 5 6
      中序：3 1 4 0 5 2 6
      后序：3 4 1 5 6 2 0  
*/

tree.h文件：

#ifndef TREE_H
#define TREE_H
#include"Node.h"

class Tree
{
public:
    Tree();                                                 //创建树   
    ~Tree();                                               //销毁树 
    Node *SearchNode(int nodeIndex);                            //根据索引寻找节点 
    bool AddNode(int nodeIndex,int direction,Node *pNode);  //添加节点 
    bool DeleteNode(int nodeIndex,Node *pNode);             //删除节点 
    void PreorderTraverse();                                //前序遍历
    void InorderTraverse();                                 //中序遍历 
    void PostorderTraverse();                               //后序遍历                          
private:
    Node *m_pRoot;  
};
#endif

Node.h文件：

#ifndef NODE_H
#define NODE_H

class Node
{
public :
    Node();
    Node *SearchNode(int nodeIndex); //寻找索引号所在节点，若存在返回该节点，否则返回NULL 
    void DeleteNode();               //删除节点 
    void PreorderTraverse();         //前序遍历 
    void InorderTraverse();          //中序遍历             
    void PostorderTraverse();        //后序遍历 
    int index;                       //索引号 
    int data;                        //数据 
    Node *pLChild;                   //左孩子指针 
    Node *pRChild;                   //右孩子指针 
    Node *pParent;                   //双亲指针  

};

#endif

Node.cpp文件：

#include"Node.h"
#include"stdlib.h"
#include
  
   
using namespace std; 
Node::Node()                                        //节点构造函数 
{                                                   //初始创建根节点 
    index=0;                                        // 索引初始化为0 
    data=3;                                         // 数据初始为3 
    pLChild=NULL;
    pRChild=NULL;
    pParent=NULL;
}
Node *Node::SearchNode(int nodeIndex)               
{
    if(this->index == nodeIndex)                    //找到返回 
        return this;

    Node *temp;                                     //暂存使用 
    if(this->pLChild != NULL)                       //左孩子存在 
    {   
        if(this->pLChild->index == nodeIndex) 
            return  this->pLChild;  
        else                                        //如果没找到 
        {
        temp=this->pLChild->SearchNode(nodeIndex);  //递归调用 
        if(temp != NULL)
            return temp;                            //找到则返回，否则继续向下 
        }       
    }   

    if(this->pRChild != NULL)                       //右孩子存在 
    {   
        if(this->pRChild->index == nodeIndex)
            return  this->pRChild;                  
        else                                        //未找到 
        {
        temp=this->pRChild->SearchNode(nodeIndex);  //递归调用 
            return temp;                            //直接return 出去 不需要继续找 
        }   
    }       
}

void Node::DeleteNode()                             
{
    if(this->pLChild !=NULL)                        //左孩子存在 
        this->pLChild->DeleteNode();                //递归调用 
    if(this->pRChild !=NULL)
        this->pRChild->DeleteNode();                //递归调用 
    if(this->pParent !=NULL)                        //判断自己是双亲的左孩子or右孩子 
    {
        if(this->pParent->pLChild == this)
            this->pParent->pLChild=NULL;            
        if(this->pParent->pRChild == this)
            this->pParent->pRChild=NULL;            //判断出来使双亲该孩子指为NULL 
    }       
    delete this;                                    //自己的子孙杀完，双亲对自己指向空，可以自杀了 
}
void Node::PreorderTraverse()                       //前序遍历，递归调用 
{
    cout<
   
    index<<" "<
    
     data << endl;//打印根 if(this->pLChild !=NULL) //左 this->pLChild->PreorderTraverse(); //递归 if(this->pRChild != NULL) //右 this->pRChild->PreorderTraverse(); //递归 } /**中序遍历和后序遍历同理，只需要更改程序执行顺序**/ void Node::InorderTraverse() { if(this->pLChild !=NULL) this->pLChild->Inorder