树 c++

树 c++,第1张

树 基础 定义:

n个结点的有限集合,以一种层次结构关系建立。

基本概念: 1.内部概念:

结点的度:一个结点含有子树个数
树的度:最大的结点度
结点层次:根为第一层,其子节点为第二层。。。

2.对于树中树:

树高度、深度:树中结点最大层次
子树:

3.对于结点:

结点概念
根结点(Root):有且仅有一个的最顶端结点
分支结点/内部节点:结点度不为0的结点
叶节点/终端节点:最下端结点(结点度==0)
结点关系:
父结点:结点的子节点
子结点:某个结点子树的根节点,是该节点的子节点
兄弟结点:
堂兄弟结点:
结点祖先:
子孙结点:

4.其他:

森林:m棵互不相交的树,组成森林

树基础表示: 例程图示

所有例程采用如下图示:

坐标从左到右,从下到上排列。

1.父结点表示

除根结点外,树每个节点有且只有一个父结点。所以将结点结构体定义为“数据+父结点”,把每个结点连续的存储到结构体数组中,父结点域指下标,没有父节点时,值为-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.它的左、右子树也分别为二叉排序树

5.平衡二叉树(Balanced Binary Tree, AVL树)(没看)

它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过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.顺序表(程序待补)

对于完全二叉树和非完全二叉树:
顺序表按按满二叉树存储编号,下标从1起,对于下标index,其子结点为2index和2index+1。对于结点c_index,其父结点为[c_index/2]。
(chengxudaibu)

2.链表

对于稀疏二叉树,可采用链表存储。结点结构体保存“数据+左孩子+右孩子”

遍历

遍历指从根结点出发,按照某种顺序依次访问二叉树中所有结点,每个节点访问且只访问一次。
分为前序遍历、中序遍历、后序遍历和层序遍历。
例图:

1.前序遍历

从根节点开始,从左向右遍历,对于例图:
a->b->d->g->h->c->e->f

2.中序遍历

从左子树最左叶节点开始遍历
g->d->h->b->a->e->c->f

3.后序遍历

先递归后遍历左子树,再递归后遍历右子树,最后访问根节点
g->h->d->b->e->f->c->a

4.层序遍历(广度优先搜索,待补)

从第一层开始,从左到右遍历
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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1499173.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-25
下一篇 2022-06-25

发表评论

登录后才能评论

评论列表(0条)

保存