数据结构学习记录（六）树

树&＃xff1a;有且只有一个称为根的节点&＃xff0c;有若干个互不相交的子树&＃xff0c;这些子树本身也是一颗树。
通俗理解&＃xff1a;树由节点与边组成&＃xff0c;每一个节点只有一个父节点&＃xff0c;但可以有多个子节点&＃xff0c;但有一个节点例外&＃xff0c;该节点没有父节点&＃xff0c;此节点为根节点。
专业术语&＃xff1a;
1、深度&＃xff1a;从根节点到最底层节点的层数叫深度&＃xff0c;根节点是第一层。
2、叶子节点&＃xff1a;没有子节点的节点。
3、非终端节点&＃xff1a;实际就是非叶子节点。
4、度&＃xff1a;子节点的个数。

树可以分为一般树、二叉树、森林。
一般树&＃xff1a;任意一个节点的子节点的个数都不受限制。
森林&＃xff1a;n个互不相交的树的集合。
二叉树&＃xff1a;任意一个节点的子节点个数最多两个&＃xff0c;且子节点的位置不可更改。

二叉树的分类

二叉树又可以分为一般二叉树、满二叉树、完全二叉树。
满二叉树&＃xff1a;在不增加树的层数的前提下&＃xff0c;无法再增加一个节点的二叉树就是满二叉树。
完全二叉树&＃xff1a;如果只是删除了满二叉树最底层最右边的连续若干个节点&＃xff0c;这样形成的二叉树就是完全二叉树。

二叉树的存储

连续存储&＃xff08;完全二叉树&＃xff09;&＃xff1a;
优点&＃xff1a;查找某个节点的父节点和子节点&＃xff08;判断有没有子节点&＃xff09;的速度很快。
缺点&＃xff1a;耗用内存空间过大。
链式存储&＃xff1a;见下文程序

一般树的存储

双亲表示法

优点&＃xff1a;求父节点方便。

孩子表示法

优点&＃xff1a;求子节点方便。

双亲孩子表示法

优点&＃xff1a;求父节点和子节点都比较方便。

二叉树表示法

二叉树表示法就是把一个普通树转化成二叉树来储存。
具体方法&＃xff1a;设法保证任意一个节点的左指针指向它的第一个孩子&＃xff0c;右指针指向它的兄弟&＃xff0c;只要满足此条件&＃xff0c;就可以把一个普通树转化成二叉树。
注意&＃xff1a;一个普通树转化成的二叉树一定没有右子树。

森林的存储

先把森林转化成二叉树&＃xff0c;再存储。

树的遍历

先序遍历

先访问根节点&＃xff0c;再先序访问左子树&＃xff0c;再先序访问右子树。

中序遍历

先中序遍历左子树&＃xff0c;再访问根节点&＃xff0c;再中序遍历左子树。

后序遍历

先中序遍历左子树&＃xff0c;再中序遍历右子树&＃xff0c;最后访问根节点。

已知两种遍历序列求原始二叉树

通过先序和中序或者中序和后序可以还原出原始的二叉树。但是通过先序和后序是无法还原出原始二叉树的。

已知先序和中序&＃xff0c;求后序

已知中序和后序&＃xff0c;求先序

下面程序创建的二叉树是如下形式的&＃xff1a;

#include
#include struct BTNode
{char data;struct BTNode *pLchild;struct BTNode *pRchild;
};struct BTNode *CreateBTree(void);
void PreTraverseBTree(struct BTNode *);
void InTraverseBTree(struct BTNode *);
void PostTraverseBTree(struct BTNode *);int main(void)
{struct BTNode *A &＃61; CreateBTree();PreTraverseBTree(A); //先序遍历printf("\n");InTraverseBTree(A); //中序遍历printf("\n");PostTraverseBTree(A); //后序遍历printf("\n");
}//先序遍历
void PreTraverseBTree(struct BTNode *pT)
{if(NULL !&＃61; pT){printf("%c", pT->data);if(NULL !&＃61; pT->pLchild)PreTraverseBTree(pT->pLchild); //pT->pLchild可以代表整个左子树if(NULL !&＃61; pT->pRchild)PreTraverseBTree(pT->pRchild);}
}//中序遍历
void InTraverseBTree(struct BTNode *pT)
{if(NULL !&＃61; pT){if(NULL !&＃61; pT->pLchild)InTraverseBTree(pT->pLchild);printf("%c", pT->data);if(NULL !&＃61; pT->pRchild)InTraverseBTree(pT->pRchild);}
}//后序遍历
void PostTraverseBTree(struct BTNode *pT)
{if(NULL !&＃61; pT){if(NULL !&＃61; pT->pLchild)PostTraverseBTree(pT->pLchild);if(NULL !&＃61; pT->pRchild)PostTraverseBTree(pT->pRchild);printf("%c", pT->data);}
}//创建一个树
struct BTNode *CreateBTree(void)
{struct BTNode *pA &＃61; (struct BTNode*)malloc(sizeof(struct BTNode));struct BTNode *pB &＃61; (struct BTNode*)malloc(sizeof(struct BTNode));struct BTNode *pC &＃61; (struct BTNode*)malloc(sizeof(struct BTNode));struct BTNode *pD &＃61; (struct BTNode*)malloc(sizeof(struct BTNode));struct BTNode *pE &＃61; (struct BTNode*)malloc(sizeof(struct BTNode));pA->data &＃61; &＃39;A&＃39;;pB->data &＃61; &＃39;B&＃39;;pC->data &＃61; &＃39;C&＃39;;pD->data &＃61; &＃39;D&＃39;;pE->data &＃61; &＃39;E&＃39;;pA->pLchild &＃61; pB;pA->pRchild &＃61; pC;pB->pLchild &＃61; pB->pRchild &＃61; NULL;pC->pLchild &＃61; pD;pC->pRchild &＃61; NULL;pD->pLchild &＃61; NULL;pD->pRchild &＃61; pE;pE->pLchild &＃61; pE->pRchild &＃61; NULL;return pA;
}

参考资料

[1]数据结构–郝斌link.