树和二叉树
本帖最后由 Julia999 于 2019-10-16 16:20 编辑树——非线性的数据结构
树的定义：
树（Tree）是n（n>=0）个节点的有限集，其中空树：n=0；
（1）有且仅有一个称之为根的节点
（2）有若干个互不相交的子树，这些子树本身也是一棵树
通俗的定义：
（1）树和结点和边组成
（2）每个结点只有一个父结点，但是可以有多个子节点，但有一个结点例外，该结点没有父结点，此结点称为根结点
个人觉得，树的定义其实很好理解，形象的比喻：我感觉树长得就像一颗葡萄（反而不像树，因为我们日常见到的树，，emm，不是数据结构这样倒立的树）
树的专业术语：
（1）结点（这个，很好理解，不解释了吧)
（2）结点的度：结点拥有子树的数（说白了，也就是一个结点下面连了多少个结点就叫做结点的度）
（3）树的度：各结点的度的最大值
注意：要区分结点的度和树的度：
结点的度是相对与某一个结点而言的，但是树的度是相对于整个树而言的。
（4）叶子：度为0的结点称为叶子或终端结点（说白了，也就是孤零零没有孩子（断子绝孙）的那个结点（孤苦伶仃呀~））
（5）非终端结点（分支结点）：度不为0的结点（说白了，不是叶子的结点就是非终端结点（上有老下有小的结点~）。）其中，除了根结点之外，非终端结点又可以称为内部结点
注意：根结点既可以是叶子结点，也可以是非终端结点。（如果只有一个结点的情况）
（6）双亲和孩子：（很形象，不解释了吧）
（7）兄弟：同一个双亲的孩子称为兄弟（为啥不称做姐妹我就不知道了，但是要称为兄弟，首先你爸妈得是一样的吧~）
（8）祖先：从根结点到该结点所经分支上的所有结点
（9）子孙：以某结点为根的子树中的任一结点都称为该结点的子孙（与上面的祖先相对应）
（10）层次：结点的层次从根开始定义，根为第一层，根的孩子为第二层。
（11）堂兄弟：双亲在同一层的结点称为堂兄弟。（大白话：也就是跟你在同一层，但是爸妈不一样的那些结点都是你的堂兄弟，跟现实生活中的堂兄弟定义相似）
（12）树的深度：树中结点的最大层次称之为树的深度或高度（从根结点到最底层结点的层数）
（13）有序树和无序树：如果将树中结点的各子树看成从左到右是有次序的（即不能交换），那么就称该树为有序树，否则为无序树.（在有序树中，最左边的子树的根称为第一个孩子，最右边称为最后一个孩子）
（14）森林：很多树在一起形成森林
树的分类：
一般树：任意一个结点的子结点个数不受限制
二叉树：任意一个结点的子结点的个数不超过2个，子结点的位置不可更改
二叉树的分类：
一般二叉树：
满二叉树：一个结点都不能再多了（不增加树的层次的情况下）
完全二叉树：如果只是删除了满二叉树最底层最右边的连续若干结点的二叉树，这样的树就叫做完全二叉树
满二叉树是完全二叉树的一个特例
森林：n个互不相交的树的集合
树的存储：
二叉树的存储：
连续存储[完全二叉树]
为什么一个二叉树用数组的形式存储的时候一定要转换称完全二叉树呢？
如果我们只存放有效的点，那么我们就不知道我们这棵树是怎么造出来的。
那么，我们将会存放了很多垃圾（没有用的结点）结点，会导致内存的浪费，那么为什么我们还要这样存呢？
完全二叉树的优点：
（1）知道了结点的个数，我们就可以知道这棵树的层数
（2）我们可以知道一个结点有没有父结点，有没有子结点（可以找到父结点和子结点）
我们有三种方法，将我们的非线性结构的树转化成线性来存储：先序，中序，后序
链式存储：
也是要将森林转换成二叉树来进行存储
一般树的存储
双亲表示法：求父结点方便
孩子表示法：求子结点方便
双亲孩子表示法：求父节点和子节点都很方便
二叉树表示法：
把一个普通树转换成二叉树来存储
具体转换方法：
设法保证任意一个结点的左指针域指向它的第一个孩子，右指针域指向它的下一个兄弟结点，只要能满足此条件，就能把一个普通树转换成二叉树
通过画图我们发现，一个普通的树转换成二叉树一定没有右子树。
森林的存储
二叉树的定义：
二叉树是由n个结点组成的集合，空树：n=0，非空树：
（1）有且仅有一个称之为根结点
（2）除根结点以外的其余结点分为两个互不相交的子集，分别称为左子树和右子树，并且这两个子树本身又是二叉树
看上面感觉跟树的定义很像，那么他们之间有什么区别呢？
（1）二叉树每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点）
（2）二叉树的子树有左右之分，也就是说其次序不能任意颠倒
二叉树的五种基本形态：
（1）空二叉树
（2）仅有根结点的二叉树
（3）右子树为空的二叉树
（4）左子树为空的二叉树
（5）左右子树都不为空的二叉树
二叉树操作：
（1）遍历
先序遍历【先访问根结点】先访问根结点，再先序访问左子树，再先序右子树
中序遍历【中间访问根结点】：先中序遍历左子树，再中序遍历根结点，再中序遍历右子树
后序遍历【最后访问根结点】：后序遍历左子树，后序遍历右子树，再遍历根
已知两种遍历序列求原始二叉树：
通过先序和中序，或者中序和后序，我们可以还原出原始的二叉树，但是通过先序和后序，是无法还原出原始的二叉树的！
换种说法：只有通过先序和中序或者中序和后序才可以唯一确定一个二叉树
应用：
树是数据库中数据组织的一种形式
操作系统子父进程的关系本身就是一棵树
面向对象语言的继承关系本身就是一棵树
赫夫曼树
二叉树的遍历基本实现：
#include<iostream>
using namespace std;
struct BTNode
{
char data;
struct BTNode *pLChild;//左指针域
struct BTNode *pRChild;//右指针域
};
//手动创造结点
//创造二叉树
struct BTNode* CreatBTree()
{
struct BTNode *pA = new BTNode;
struct BTNode *pB = new BTNode;
struct BTNode *pC = new BTNode;
struct BTNode *pD = new BTNode;
struct BTNode *pE = new BTNode;
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';
pA->pLChild = pB;
pB->pLChild = NULL;
pB->pRChild = NULL;
pA->pRChild = pC;
pC->pLChild = pD;
pC->pRChild = NULL;
pD->pLChild = NULL;
pD->pRChild = pE;
pE->pLChild = NULL;
pE->pRChild = NULL;
return pA;
}
//先序遍历
void Predisplay(struct BTNode *BTree)
{
if (BTree != NULL)
{
cout << BTree->data << endl;
if (NULL != BTree->pLChild)//如果左子树为空，那么就不进行访问了
{
Predisplay(BTree->pLChild);
}
if (NULL != BTree->pRChild)//如果右子树为空，那么就不进行访问了
{
Predisplay(BTree->pRChild);
}
}
/*
伪算法：
先访问根结点
再先序遍历左子树
再先序遍历右子树
*/
}
//中序遍历
void Indisplay(struct BTNode *BTree)
{
if (BTree != NULL)
{
if (NULL != BTree->pLChild)//如果左子树为空，那么就不进行访问了
{
Indisplay(BTree->pLChild);
}
cout << BTree->data << endl;
if (NULL != BTree->pRChild)//如果右子树为空，那么就不进行访问了
{
Indisplay(BTree->pRChild);
}
}
/*
伪算法：
先中序遍历左子树
再访问根
再先序遍历右子树
*/
}
//后序遍历
void Postdisplay(struct BTNode *BTree)
{
if (BTree != NULL)
{
if (NULL != BTree->pLChild)//如果左子树为空，那么就不进行访问了
{
Postdisplay(BTree->pLChild);
}
if (NULL != BTree->pRChild)//如果右子树为空，那么就不进行访问了
{
Postdisplay(BTree->pRChild);
}
cout << BTree->data << endl;
}
/*
伪算法：
先后序遍历左子树
再后序遍历右子树
再访问根
*/
}
int main()
{
struct BTNode *BTree = CreatBTree();
cout << "先序遍历：" << endl;
Predisplay(BTree);
cout << "中序遍历：" << endl;
Indisplay(BTree);
cout << "后序遍历：" << endl;
Postdisplay(BTree);
system("pause");
return 0;
}
求叶子结点数目：
#include<iostream>
using namespace std;
struct BTNode
{
char data;
struct BTNode *pLChild;//左指针域
struct BTNode *pRChild;//右指针域
};
//手动创造结点
//创造二叉树
struct BTNode* CreatBTree()
{
struct BTNode *pA = new BTNode;
struct BTNode *pB = new BTNode;
struct BTNode *pC = new BTNode;
struct BTNode *pD = new BTNode;
struct BTNode *pE = new BTNode;
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';
pA->pLChild = pB;
pB->pLChild = NULL;
pB->pRChild = NULL;
pA->pRChild = pC;
pC->pLChild = pD;
pC->pRChild = NULL;
pD->pLChild = NULL;
pD->pRChild = pE;
pE->pLChild = NULL;
pE->pRChild = NULL;
return pA;
}
//计算叶子结点的数目（递归求解）
int num = 0;
void calculateLeafNum(struct BTNode *BTree)
{
if (BTree == 0)
{
return;
}
if (BTree->pLChild == NULL && BTree->pRChild == NULL)
{
num++;
}
//求左子树的叶子结点的数目；
calculateLeafNum(BTree->pLChild);
//求右子树叶子结点的数目；
calculateLeafNum(BTree->pRChild);
}
int main()
{
struct BTNode *BTree = CreatBTree();
calculateLeafNum(BTree);
cout << "叶子结点的数目是：" << num << endl;
system("pause");
return 0;
}
求二叉树的高度：
#include<iostream>
using namespace std;
struct BTNode
{
char data;
struct BTNode *pLChild;//左指针域
struct BTNode *pRChild;//右指针域
};
//手动创造结点
//创造二叉树
struct BTNode* CreatBTree()
{
struct BTNode *pA = new BTNode;
struct BTNode *pB = new BTNode;
struct BTNode *pC = new BTNode;
struct BTNode *pD = new BTNode;
struct BTNode *pE = new BTNode;
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';
pA->pLChild = pB;
pB->pLChild = NULL;
pB->pRChild = NULL;
pA->pRChild = pC;
pC->pLChild = pD;
pC->pRChild = NULL;
pD->pLChild = NULL;
pD->pRChild = pE;
pE->pLChild = NULL;
pE->pRChild = NULL;
return pA;
}
int calculateDepth(struct BTNode *BTree)
{
int depth = 0;
if (BTree == NULL)
{
return 0;
}
//计算左子树的高度
int Ldepth = calculateDepth(BTree->pLChild);
//计算右子树的高度
int Rdepth = calculateDepth(BTree->pRChild);
depth = Ldepth > Rdepth ? Ldepth + 1 : Rdepth + 1;//左子树和右子树中最大的加1
return depth;
}
int main()
{
int depth = 0;
struct BTNode *BTree = CreatBTree();
depth = calculateDepth(BTree);
cout << "树的高度是：" << depth << endl;
system("pause");
return 0;
}
二叉树的拷贝和释放：
#include<iostream>
using namespace std;
struct BTNode
{
char data;
struct BTNode *pLChild;//左指针域
struct BTNode *pRChild;//右指针域
};
//手动创造结点
//创造二叉树
struct BTNode* CreatBTree()
{
struct BTNode *pA = new BTNode;
struct BTNode *pB = new BTNode;
struct BTNode *pC = new BTNode;
struct BTNode *pD = new BTNode;
struct BTNode *pE = new BTNode;
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';
pA->pLChild = pB;
pB->pLChild = NULL;
pB->pRChild = NULL;
pA->pRChild = pC;
pC->pLChild = pD;
pC->pRChild = NULL;
pD->pLChild = NULL;
pD->pRChild = pE;
pE->pLChild = NULL;
pE->pRChild = NULL;
return pA;
}
//遍历二叉树，这里使用先序遍历
void preDisplay(struct BTNode *BTree)
{
if (BTree == NULL)
{
return;
}
cout << BTree->data << endl;
//遍历左子树
preDisplay(BTree->pLChild);
//遍历右子树
preDisplay(BTree->pRChild);
}
//拷贝二叉树（递归拷贝）
struct BTNode* copyBTNode(struct BTNode *BTree)
{
if (BTree == NULL)
{
return NULL;
}
//拷贝左子树
struct BTNode *Lchild=copyBTNode(BTree->pLChild);
//拷贝右子树
struct BTNode *Rchild=copyBTNode(BTree->pRChild);
//创建结点,拷贝当前结点
struct BTNode *newNode = new struct BTNode;
newNode->data = BTree->data;
newNode->pLChild = Lchild;
newNode->pRChild = Rchild;
return newNode;
}
//二叉树的释放
void freeSpaceBTree(struct BTNode *BTree)
{
if (BTree == NULL)
{
return;
}
//释放左子树
freeSpaceBTree(BTree->pLChild);
//释放右子树
freeSpaceBTree(BTree->pRChild);
//释放当前结点
free(BTree);
}
int main()
{
struct BTNode *BTree = CreatBTree();
struct BTNode *copyBTree = copyBTNode(BTree);
cout << "原始二叉树为：" << endl;
preDisplay(BTree);
cout << "拷贝后的二叉树为：" << endl;
preDisplay(copyBTree);
freeSpaceBTree(copyBTree);
system("pause");
return 0;
}
#号法创建树：
#include<iostream>
using namespace std;
struct BTNode
{
char data;
struct BTNode *pLChild;//左指针域
struct BTNode *pRChild;//右指针域
};
struct BTNode* creatBTree()
{
fflush(stdin);//清除缓冲区
char ch;
cin >> ch;
struct BTNode *node;
if (ch == '#')//如果输入为#号，直接置空
{
node = NULL;
}
else//否则
{
node = new struct BTNode;
node->data = ch;
node->pLChild = creatBTree();
node->pRChild = creatBTree();
}
return node;
}
void preDisplay(struct BTNode *BTree)
{
if (BTree == NULL)
{
return;
}
cout << BTree->data << endl;
preDisplay(BTree->pLChild);
preDisplay(BTree->pRChild);
}
int main()
{
struct BTNode *BTree = creatBTree();
preDisplay(BTree);
system("pause");
return 0;
}
看到你说葡萄，我认为 更像是 树桩和他的根系 bingshidie 发表于 2019-10-16 16:00
看到你说葡萄，我认为 更像是 树桩和他的根系
有道理
页:
[1]