数据结构05-树(Tree)


一、什么是树?


是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树。如图:

happysneaker.com

需要掌握的概念:

happysneaker.com

这里所学所用的都是二叉树。

happysneaker.com



二、二叉树的数组实现

三个文件:Tree.h、Tree.cpp、demo.cpp


Tree.h

#ifndef TREE_H
#define TREE_H

class Tree {

public:
	Tree(int size,int *pRoot);		//	创建树
	~Tree();		// 销毁树
	int *SearchNode(int nodeIndex);		// 根据索引寻找结点
	bool AddNode(int nodeIndex,int direction,int *pNode);		// 添加结点
	bool DeleteNode(int nodeIndex,int *pNode);		// 删除结点
	void TreeTraverse();		// 遍历结点

private:
	int *m_pTree;
	int m_iSize;
};

#endif



Tree.cpp

#include"stdafx.h"
#include<iostream>
#include"Tree.h"

using namespace std;

Tree::Tree(int size, int *pRoot) {
	m_iSize = size;
	m_pTree = new int[size];
	for (int i = 0; i < size;i++) {
		m_pTree[i] = 0;
	}
	m_pTree[0] = *pRoot;
}

Tree::~Tree() {
	delete[]m_pTree;
	m_pTree = NULL;
}

int *Tree::SearchNode(int nodeIndex) {
	if (nodeIndex < 0 || nodeIndex >= m_iSize) {
		return NULL;
	}
	if (m_pTree[nodeIndex] == 0) {
		return NULL;
	}
	return &m_pTree[nodeIndex];
}

bool Tree::AddNode(int nodeIndex, int direction, int *pNode) {
	if (nodeIndex < 0 || nodeIndex >= m_iSize) {
		return false;
	}
	if (m_pTree[nodeIndex] == 0) {
		return false;
	}

	if (direction == 0) {
		if (nodeIndex * 2 + 1 >= m_iSize) {
			return false;
		}
		if (m_pTree[nodeIndex * 2 + 1] != 0) {
			return false;
		}
		m_pTree[nodeIndex * 2 + 1] = *pNode;
	}

	if (direction == 1){
		if (nodeIndex * 2 + 2 >= m_iSize) {
			return false;
		}
		if (m_pTree[nodeIndex * 2 + 2] != 0) {
			return false;
		}
		m_pTree[nodeIndex * 2 + 2] = *pNode;
	}
	return true;
}

bool Tree::DeleteNode(int nodeIndex, int *pNode) {
	if (nodeIndex < 0 || nodeIndex >= m_iSize) {
		return false;
	}
	if (m_pTree[nodeIndex] == 0) {
		return false;
	}

	*pNode = m_pTree[nodeIndex];
	m_pTree[nodeIndex] = 0;
	return true;
}

void Tree::TreeTraverse() {
	for (int i = 0; i < m_iSize; i++) {
		cout << m_pTree[i] << " ";
	}
}



demo.cpp

#include"stdafx.h"
#include<stdlib.h>
#include<iostream>
using namespace std;

#include "Tree.h"

/*	二叉树(数组表示) */


int main()
{
	int root = 3;
	Tree *pTree = new Tree(10,&root);
	int node1 = 5;
	int node2 = 8;

	pTree->AddNode(0,0,&node1);
	pTree->AddNode(0,1,&node2);

	int node3 = 2;
	int node4 = 6;

	pTree->AddNode(1, 0, &node3);
	pTree->AddNode(1, 1, &node4);

	int node5 = 9;
	int node6 = 7;

	pTree->AddNode(2,0,&node5);
	pTree->AddNode(2,1,&node6);

	int node = 0;
	pTree->DeleteNode(6,&node);
	cout << "node=" << node << endl;

	pTree->TreeTraverse();

	int *p = pTree->SearchNode(2);

	cout << endl << "node=" << *p << endl;

	delete pTree;

	system("pause");
    return 0;
}


happysneaker.com

运行结果


java版本:http://数据结构 - 二叉树 - 面试中常见的二叉树算法题 - CSDN博客 https://blog.csdn.net/u012428012/article/details/79089915


三、二叉树的链表实现

由于我编译出错,请参考视频:https://www.imooc.com/video/12138

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论