二叉树（数组形式）

分手后的思念是犯贱 2022-02-19 18:59 229阅读 0赞

### 二叉树顺序存储结构 ###

#### 相关性质： ####

1.  二叉树的第i层上面最多有2i-1个结点
2.  深度为k的二叉树最多有2k\-1个结点
3.  终端结点（度为0）为n，度为2的结点数为m，则n=m+1
4.  具有n个结点的二叉树的深度为(int)(log2n)+1

#### 二叉树遍历 ####

前序遍历，中序遍历，后序遍历

#### 代码 ####

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();  //遍历
    public:
    	int *m_pTree;  //存储数据
    	int m_iSize;   //数组长度
    };
    
    
    #endif // !TREE_H_

Tree.cpp

#include "Tree.h"
    #include <iostream>
    using namespace std;
    Tree::Tree(int size,int *pRoot)
    {
    	m_iSize = size;
    	m_pTree = new int[size];
    	for (int i = 0; i < m_iSize; 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)
    {//direction0为左孩子，1为右孩子
    	if (nodeIndex < 0 || nodeIndex >= m_iSize)  //索引不合法
    	{
    		return NULL;
    	}
    	if (m_pTree[nodeIndex] == 0) //节点不存在
    	{
    		return NULL;
    	}
    	//左孩子 父节点下标*2+1  
    	//右孩子 父节点下标*2+2
    	if (direction == 0)
    	{
    		if (nodeIndex * 2 + 1 >= m_iSize)  //索引不合法
    		{
    			return NULL;
    		}
    		if (m_pTree[nodeIndex * 2 + 1] != 0) //节点已存在
    		{
    			return NULL;
    		}
    		m_pTree[nodeIndex * 2 + 1] = *pNode;
    	}
    	if (direction == 1)
    	{
    		if (nodeIndex * 2 + 2 >= m_iSize)  //索引不合法
    		{
    			return NULL;
    		}
    		if (m_pTree[nodeIndex * 2 + 2] != 0) //节点已存在
    		{
    			return NULL;
    		}
    		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 <iostream>
    #include <stdlib.h>
    #include "Tree.h"
    using namespace std;
    /*
    二叉树（数组表示）
    完成树的基本操作
    1.树的创建和销毁
    2.树中节点的搜索
    3.树中节点的添加与删除
    4.树中节点的遍历
    bool CreateTree(Tree **pTree,Node *pRoot);  //创建树
    void DestroyTree(Tree *pTree);    //销毁树
    Node *searchNode(Tree *pTree,int nodeIndex);  //根据索引寻找节点
    bool AddNode(Tree *pTree,int nodeIndex,Node *pNode);  //添加节点
    bool DeleteNode(Tree *pTree,int nodeIndex,Node *pNode); //删除节点
    void TreeTraverse(Tree *pTree);  //遍历
    例如 3    5 8    2 6 9 7
    */
    int main(void) {
    	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 << "*p=" << *p << endl;
    	delete pTree;
    	system("pause");
    	return 0;
    }