n个结点的有限集合,以一种层次结构关系建立。
基本概念: 1.内部概念:结点的度:一个结点含有子树个数
树的度:最大的结点度
结点层次:根为第一层,其子节点为第二层。。。
树高度、深度:树中结点最大层次
子树:
结点概念
根结点(Root):有且仅有一个的最顶端结点
分支结点/内部节点:结点度不为0的结点
叶节点/终端节点:最下端结点(结点度==0)
结点关系:
父结点:结点的子节点
子结点:某个结点子树的根节点,是该节点的子节点
兄弟结点:
堂兄弟结点:
结点祖先:
子孙结点:
森林:m棵互不相交的树,组成森林
树基础表示: 例程图示所有例程采用如下图示:
坐标从左到右,从下到上排列。
除根结点外,树每个节点有且只有一个父结点。所以将结点结构体定义为“数据+父结点”,把每个结点连续的存储到结构体数组中,父结点域指下标,没有父节点时,值为-1。
#include
#include
using namespace std;
#define MaxN 1024
template <typename T>
class treenode {
public:
T data;
int parent;
treenode() {}
treenode(T Data, int c): data(Data), parent(c) {
}
//没写析构
};
template <typename T>
class tree {
public:
treenode<T> *nodes;
int root ;
int n ;
tree(): root(0), n(0) {
nodes = new treenode<T>[MaxN];
}
tree(int N): root(0), n(N) {
nodes = new treenode<T>[N];
}
//没写析构
};
int main() {
tree<char> Tree(8);
treenode<char> N = treenode<char>('a', -1);
Tree.nodes[0] = N;
treenode<char> N1 = treenode<char>('b', 0);
Tree.nodes[1] = N1;
treenode<char> N2 = treenode<char>('c', 0);
Tree.nodes[2] = N2;
treenode<char> N3 = treenode<char>('d', 1);
Tree.nodes[3] = N3;
treenode<char> N4 = treenode<char>('e', 2);
Tree.nodes[4] = N4;
treenode<char> N5 = treenode<char>('f', 2);
Tree.nodes[5] = N5;
treenode<char> N6 = treenode<char>('g', 3);
Tree.nodes[6] = N6;
treenode<char> N7 = treenode<char>('h', 3);
Tree.nodes[7] = N7;
for (int i = 7; i >= 0; i--) {
int j = i;
cout << Tree.nodes[j].data;
while (Tree.nodes[j].parent >= 0) {
j = Tree.nodes[j].parent;
cout << Tree.nodes[j].data;
}
cout << endl;
}
return 0 ;
};
2.子结点表示
父结点表示缺点:无法知道父结点的子节点有哪些
修改结点结构体为“数据+子结点数量+子节点位置数组”
#include
#include
using namespace std;
template <typename T>
class Node {
public:
T data;
int childnodes_size;
int *childnodes;
Node(T d, int N): data(d), childnodes_size(N) {
}
Node(T d, int N, int *num) {
data = d;
childnodes_size = N;
childnodes = new int[N];
memcpy(childnodes, num, sizeof(childnodes));
}
Node() {
}
//没写析构
};
template <typename T>
class tree {
public:
int Treesize;
Node<T> *Tree;
tree(int Tn) {
Treesize = Tn;
Tree = new Node<T>[Tn];
}
//没写析构
};
int main() {
tree<char> ATree(8);
int arr[2] = {1, 2};
Node<char> p = Node<char>('a', 2, arr);
ATree.Tree[0] = p;
int arr1[1] = {3};
Node<char> p1 = Node<char>('b', 1, arr1);
ATree.Tree[1] = p1;
int arr2[2] = {4, 5};
Node<char> p2 = Node<char>('c', 2, arr2);
ATree.Tree[2] = p2;
int arr3[3] = {6, 7};
Node<char> p3 = Node<char>('d', 3, arr3);
ATree.Tree[3] = p3;
Node<char> p4 = Node<char>('e', 0);
ATree.Tree[4] = p4;
Node<char> p5 = Node<char>('f', 0);
ATree.Tree[5] = p5;
Node<char> p6 = Node<char>('g', 0);
ATree.Tree[6] = p6;
Node<char> p7 = Node<char>('h', 0);
ATree.Tree[7] = p7;
//如何遍历显示,需修改,这里只显示最左边
int i = 0;
while (ATree.Tree[i].childnodes_size > 0) {
cout << ATree.Tree[i].data ;
i = ATree.Tree[i].childnodes[0];
}
cout << ATree.Tree[i].data ;
cout << endl;
return 1;
}
3.左儿子右兄弟
结点结构体保存“数据+第一个孩子结点+第一个右兄弟结点”
#include
using namespace std;
template <typename T>
class Node {
public:
T data;
int child;
int brother;
Node() {
}
Node(T d): data(d) {
}
Node(T d, int l, int r): data(d), child(l), brother(r) {
}
};
template <typename T>
class Tree {
public:
Node<T> *tree;
int tsize;
Tree(int ts): tsize(ts) {
tree = new Node<T>[ts];
}
};
int main() {
Tree<char> aTree = Tree<char>(8);
aTree.tree[0] = Node<char>('a', 1, -1);
aTree.tree[1] = Node<char>('b', 3, 2);
aTree.tree[2] = Node<char>('c', 4, -1);
aTree.tree[3] = Node<char>('d', 6, -1);
aTree.tree[4] = Node<char>('e', -1, 5);
aTree.tree[5] = Node<char>('f', -1, -1);
aTree.tree[6] = Node<char>('g', -1, 7);
aTree.tree[7] = Node<char>('h', -1, -1);
int i = 0;
while (aTree.tree[i].child > 0) {
cout << aTree.tree[i].data;
i = aTree.tree[i].child;
}
cout << aTree.tree[i].data << endl;
return 1;
}
树分类
二叉树
概念
树中不存在度大于2的结点。子树有顺序,分为左子树和右子树。
分类 1.斜树结点只有左子树/只有右子树,类似链表或线性表。
2.满二叉树
所有根结点和内部结点都存在左右子树,非叶结点度为2,叶节点都在同一层。对于深度相同的二叉树,满二叉树具有最多节点数:2^h-1,结点总数为奇数。
3.完全二叉树
二叉树所有节点顺序按满二叉树顺序排列,为完全二叉树。此时叶子结点只能在最后两层,最下层位置在左连续,倒数第二层在右连续。某结点的度为1则该结点没有右子树。相同结点数二叉树,完全二叉树深度最小。
4.二叉排序树/二叉搜索树/二叉查找树(Binary Sort Tree)(没看)
1.若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
2.若它的右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
3.它的左、右子树也分别为二叉排序树
它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。(注:平衡二叉树应该是一棵二叉排序树)
性质性质1
第i层至多2^(i-1)个结点(左右都满的情况);
性质2
深度为h的二叉树至多2^h-1个结点(满二叉树情况);
性质3
对于任意树,如果其叶节点个数为m,度为2结点树为n,m=n+1;
推导:
设:结点数为0(叶节点)数:m,结点数为1数:l,结点数为2数:n,总结点数为sum,总边数为sum-1
对于边数有:
sum-1 = 2*n+l
对于结点数有
sum = m+n+l
联立:
m = n+1
性质4
拥有那个结点的完全二叉树深度为[log(n)]+1,[ ]向下取整,log以2为底。
对于完全二叉树和非完全二叉树:
顺序表按按满二叉树存储编号,下标从1起,对于下标index,其子结点为2index和2index+1。对于结点c_index,其父结点为[c_index/2]。
(chengxudaibu)
对于稀疏二叉树,可采用链表存储。结点结构体保存“数据+左孩子+右孩子”
遍历遍历指从根结点出发,按照某种顺序依次访问二叉树中所有结点,每个节点访问且只访问一次。
分为前序遍历、中序遍历、后序遍历和层序遍历。
例图:
从根节点开始,从左向右遍历,对于例图:
a->b->d->g->h->c->e->f
从左子树最左叶节点开始遍历
g->d->h->b->a->e->c->f
先递归后遍历左子树,再递归后遍历右子树,最后访问根节点
g->h->d->b->e->f->c->a
从第一层开始,从左到右遍历
a->b->c->d->e->f->g->h
例程:
#include
#include
using namespace std;
template <typename T>
class Node {
public:
T data;
Node<T> *lchild;
Node<T> *rchild;
Node() {
}
Node(T d): data(d), lchild(NULL), rchild(NULL) {
}
Node(T d, Node<T> *l, Node<T> *r): data(d), lchild(l), rchild(r) {
}
};
template <typename T>
class BiTree {
public:
Node<T> *root;
BiTree(Node<T> *r): root(r) {
};
~BiTree() {
release(root);
}
void PreOrder() { //前序排列
preorder(root);
cout << endl;
}
void InOrder() { //中序排列
inorder(root);
cout << endl;
}
void PostOrder() { //后序排列
postorder(root);
cout << endl;
}
void LayerOrder() {
queue<Node<T>*> treequeue;
treequeue.push(root) ;
while (!treequeue.empty()) {
for (int i = 0; i < treequeue.size(); i++) {
Node<T> *p = treequeue.front();
treequeue.pop();
if (p != NULL) {
cout << p->data;
treequeue.push(p->lchild);
treequeue.push(p->rchild);
}
}
}
cout << endl;
}
private:
void release(Node<T> *r) {
if (r != NULL) {
release(r->lchild);
release(r->rchild);
delete r;
}
}
void preorder(Node<T> *r) {
if (r != NULL) {
cout << r->data ;
preorder(r->lchild);
preorder(r->rchild);
}
}
void inorder(Node<T> *r) {
if (r != NULL) {
inorder(r->lchild);
cout << r->data;
inorder(r->rchild);
}
}
void postorder(Node<T> *r) {
if (r != NULL) {
postorder(r->lchild);
postorder(r->rchild);
cout << r->data;
}
}
};
int main() {
//gouzaoshu
Node<char> *p8 = new Node<char>('h');
Node<char> *p7 = new Node<char>('g');
Node<char> *p6 = new Node<char>('f');
Node<char> *p5 = new Node<char>('e');
Node<char> *p4 = new Node<char>('d', p7, p8);
Node<char> *p3 = new Node<char>('c', p5, p6);
Node<char> *p2 = new Node<char>('b', p4, NULL);
Node<char> *p1 = new Node<char>('a', p2, p3);
BiTree<char> Atree = BiTree<char>(p1);
cout << "前序排列:" << endl;
Atree.PreOrder();
cout << "中序排列:" << endl;
Atree.InOrder();
cout << "后序排列:" << endl;
Atree.PostOrder();
cout << "层序排列:" << endl;
Atree.LayerOrder();
return 1;
}
常用算法
1.递归
2.遍历
使用栈/队列实现递归
2.DFS/BFS
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)