树的详细介绍_IT分享知识网

大家好，欢迎来到IT知识分享网。

树

适合新手查阅的树的知识笔记，代码量丰富极大，供大家参考，不过还是要自己思考噢~

树的基础知识

树的定义：是n个节点的有限集合。n=0时，表示空树；n>0时，为非空树，任意一颗非空树有且仅有一个根节点，其余节点分为互不相交的有限集，每个有限集称作根的子树。
节点的度：节点拥有的子树个数。
树的度：树中节点的最大度。
节点的层次：从根到该节点的层数。
树的深度：所有节点的最大层数。
孩子，双亲：节点的子树的根称作该节点的孩子，反之，该节点为孩子的双亲。
兄弟：双亲相同的节点互称兄弟。
堂兄弟：双亲是兄弟的节点。
祖先，子孙：从该节点到树根经过的所有节点为该节点的祖先。节点子树的所有节点为该节点的子孙
有序树：节点各子树从左到右有序，不能互换位置。
无序树：各子树可互换位置。
森林：好几棵树组成的集合。

树的存储

顺序存储

二叉树可以采用顺序存储结构，按完全二叉树的节点层次编号，依次存放二叉树中的数据元素。完全二叉树很适合顺序存储。

普通二叉树进行顺序存储需要补充为完全二叉树，在对应完全二叉树没有孩子的地方补0(由此可见普通二叉树不适合顺序存储，有可能补充了太多0而浪费大量空间)

树中的节点是一对多的逻辑关系，所以不仅要存储数据元素，还要存储他们之间的逻辑关系。

代码不给出，因为一般不用

双亲表示法：除了存储数据元素，还存储其双亲结点的下标。

孩子表示法：除了存储数据元素，还存储其所有孩子的下标。

双亲孩子表示法：除了存储数据元素，还存储其双亲结点，所有孩子的下标。（其实就是在孩子表示法的基础上增加了双亲域）

链式存储

孩子链表表示法：类似邻接表，表头包含数据元素(data)和指向第一个孩子指针(first)，将所有孩子放入一个单链表。

fiste指针指向的单链表的每个节点记录该节点下标和下一个节点的地址。

typedef int Elemtype; //定义节点类型 //孩子链表表示法 typedef struct pnode { //表头 Elemtype data; Childptr fitst; }; typedef struct childNode { //单链表 int child; Childptr next; }*Childptr;

孩子兄弟表示法：节点除了存储数据元素，还存储两个指针域(lchild,rchild),称为二叉链表。

//二叉链表的节点的结构体定义如下 typedef struct BTnode { Elemtype data; struct BTnode* lchild, * rchild; }BTnode,*Btree;

树，森林，二叉树的转换

根据树的孩子兄弟表示法，任何一棵树都可以转为二叉链表存储形式。任何树和森林都可以被转换为二叉树，其存储方式就简单多了，完美解决了树中孩子数量无法确定且难以分配空间的问题。

树转为二叉树要点：最左边的孩子不要动，剩下的孩子依次右斜

如图：

小问题：下图是二叉树还是树？

答案：可能是树可能是二叉树

同理：森林转换为二叉树

二叉树转换为森林逆过来看

二叉树的性质

二叉树的第i层最多有2^{(i-1)个节点(满二叉树就是每一层都有2}(i-1)个节点)
深度为h的二叉树最多2^h-1个节点
叶子节点数=双分支节点数+1

二叉树的创建

//二叉链表的询问法创建 void createTree(Btree& T) { char check; T = new Bnode; cout << "请输入节点信息" << endl; cin >> T->data; cout << "是否添加" << T->data << "的左孩子(Y/N)" << endl; cin >> check; if (check == 'Y') { createTree(T->lchild); } else { T->lchild = NULL; } cout<< "是否添加" << T->data << "的右孩子(Y/N)" << endl; cin >> check; if (check == 'Y') { createTree(T->rchild); } else { T->rchild = NULL; } }

//补空法创建二叉树 void createTree2(Btree& T) { char ch; cin >> ch;//二叉树补空后，按先序遍历序列输入文字 if (ch == '#') T = NULL;//第一个就为#，是个空树 else { T = new Bnode; T->data = ch; //生成根节点 createTree2(T->lchild); //递归创建左子树 createTree2(T->rchild); } }

二叉树的遍历

递归法遍历二叉树

//遍历二叉树 //先序遍历，中序，后序 void preorder(Btree T) {//根左右 if (T) { cout << T->data << " ";//先序 preorder(T->lchild); //cout << T->data << " ";//中序 preorder(T->rchild); //cout << T->data << " ";//后序 } }

非递归法遍历二叉树

一般树没有中序遍历。

先序非递归遍历

#include<iostream> #include<stack> using namespace std; typedef int Elemtype; #define MAXSIZE 100 //二叉链表的节点的结构体定义如下 typedef struct Bnode { Elemtype data; struct Bnode* lchild, * rchild; }Bnode,*Btree; //先序非递归遍历 void preOrderNonRecurision(Btree t) { if (t != NULL) { stack<Btree>s; //创建栈 s.push(t); //根节点进入栈 while (!s.empty()) //栈为空时候，退出循环 { Btree p = s.top(); //取栈顶 s.pop(); //栈顶元素出栈 cout << p->data << endl; if (p->rchild != NULL) //先序遍历先遍历左节点后右节点 s.push(p->rchild); //据栈的特点，后进先出，故右孩子先入栈，左孩子才先出栈 if (p->lchild != NULL) s.push(p->lchild); } } }

后序遍历的非递归

//后序遍历的非递归 //与先序遍历很像，注释不再赘述 void postOrderNonRecurision(Btree t) { if (t != NULL) { stack<Btree>s1; stack<Btree>s2; //，故需要使用两个栈 s1.push(t); while (!s1.empty()) { Btree p = s1.top(); s1.pop(); s2.push(p); //每次s1出栈的元素，s2入栈，s2出栈的时候就是逆序了 if (p->lchild != NULL) //逆后序是：根右左，故先入栈左子树 s1.push(p->lchild); if (p->rchild != NULL) s1.push(p->rchild); } //根据s2出栈来写出后序遍历 while (!s2.empty()) { Btree p = s2.top(); cout << p->data << endl; s2.pop(); } } }

线索二叉树

以二叉链表作为储存结构，只能找到节点的左右孩子，不能直接得到节点的直接前驱和直接后继，这种信息只能在遍历的动态过程才能得到。解决方法：在每个节点增加两个指针域(线索)，分别指示节点在任意一次遍历时得到的前驱和后继。(还有一个好处，就是使得结构的存储密度大大降低)。而得到节点直接前驱和后继的信息只能在遍历的过程才能得到，因此线索化的过程就是在遍历的过程中修改空指针的过程。

使二叉树变为线索二叉树的过程称为线索化。

采用中序遍历的顺序构建线索二叉树，每个节点的前驱节点是左子树的最右下方节点，后继结点是右子树的最左下方节点。

#include<iostream> using namespace std; typedef int Elemtype; //二叉链表的节点的结构体定义如下 typedef struct Bnode { Elemtype data; struct Bnode* lchild, * rchild; int lTag, rTag; //为1时，指向线索，为0时，指向孩子 }Bnode,*Btree; //p遍历节点，pre指向当前节点的前驱节点 void inThread(Btree p, Btree pre) { if (p != NULL) { //左子树线索化 inThread(p->lchild, pre); //根 把中序遍历对节点的访问变成线索化 if (p->lchild == NULL) {//是叶子节点，最左下的节点 p->lchild = pre; //由上面的解释，最左下的节点有直接前驱 p->lTag = 1; } if (pre != NULL && pre->rchild == NULL)//最右下的节点 { pre->rchild = p; //最右下的节点有直接后继 pre->rTag = 1; } pre = p;//进入下一个递归口之前，pre指向p，保证pre指向p的前驱33 //右子树线索化 inThread(p->rchild, pre); } }

哈夫曼树

树的带权路径长度(WPL):树中所有叶子节点的带权路径长度之和。

权值越大的节点，距离根节点越近。
树中没有单分支节点(除了叶子节点之外，所有节点都有左右孩子)
树的带权路径长度最短(哈夫曼编码后的长度，比定长编码的长度要短)

构建哈夫曼树、

将所有叶子节点放在一个集合里，每个叶子节点代表一颗只有一个节点的树。每个节点都附带自己的权值，采用贪心策略，首先取出最小权值的两个节点，作为一个根节点的左右子树，根节点的权值为两子树之和，在选取剩下的没有双亲且权值最小两棵树作为左右子树，组合成二叉树，如图。

)

哈夫曼编码

每个分支中左分支表示0，右分支表示1(如图)，从根节点到叶子节点路过的分支即为该节点的编码。

哈夫曼编码也叫做前缀编码(长度不等，且一个字符的编码都不是另一个字符编码的前缀，没有多义性)。

一颗有n个叶子节点的哈夫曼树有2n-1个节点，可以存储在大小为2n-1的一维数组中。

的树。每个节点都附带自己的权值，采用贪心策略，首先取出最小权值的两个节点，作为一个根节点的左右子树，根节点的权值为两子树之和，在选取剩下的没有双亲且权值最小两棵树作为左右子树，组合成二叉树，如图。

[外链图片转存中…(img-GEz3MLKZ-40)].PNG)