p二叉树是由唯一的起始结点引出的结点集合。这个起始结点称为根(root)
p二叉树中的任何非根结点都有且仅有一个前驱结点，称之为该结点的父结点(或称为双亲，parent)。根结点即为二叉树中唯一没有父结点的结点
p二叉树中的任何结点最多可能有两个后继结点，分别称为左子结点(或左孩子、左子女，left child)和右子结点(或右孩子，右子女，right child)，具有相同父结点的结点之间互称兄弟结点(sibling)
p二叉树中结点的子树数目称为结点的度(degree)。
p没有子结点的结点称为叶结点 (leaf，也称“树叶”或“终端结点”)，叶结点的度为0。
p除叶结点以外的那些非终端结点称为内部结点(或分支结点，internal node)
p父结点k与子结点k’之间存在一条有向连线<k, k’>，称作边(edge)
p若二叉树中存在结点序列{k0，k1，…，ks}，使得<k0，k1>，< k1，k2>，…，< ks-1，ks>都是二叉树中的边，则称从结点k0到结点ks存在一条路径(path)，该路径所经历的边的个数称为这条路径的路径长度(path length)。若有一条由 k到达ks的路径，则称k是ks的祖先(ancestor)，ks是k的子孙(descendant)
p断掉一个结点与其父结点的连接，则该结点与其子孙构成的树就称为以该结点为根的子树(subtree)
p从根结点到某个结点的路径长度称为结点的层数(level)，根结点为第0层，非根结点的层数是其父结点的层数加1
课程要求：完成树的基本操作 1、树的创建和销毁 2、树中结点的搜索 3、树中结点的添加和删除 4、树中结点的遍历 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(); //遍历结点 关于数组与树之间的算法转换 int tree[n] 3 5 8 2 6 9 7 父亲结点下标*2 + 1 = 该结点左孩子 父亲结点下标*2 + 2 = 该结点右孩子 3(0) 5(1) 8(2) 2(3) 6(4) 9(5) 7(6)
<span style="font-size:18px;">/*****************数组实现二叉树tree.h*********************/ #ifndef _TREE_H #define _TREE_H class Tree { int* m_pTree; int m_iSize; 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(); //遍历结点 }; #endif</span> [cpp] view plain copy <span style="font-size:18px;">/*****************数组实现二叉树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 < 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]<<" "; } }</span> [cpp] view plain copy <span style="font-size:18px;">#include "tree.h" #include <iostream> using namespace std; int main() { int root = 3; Tree *tree = new Tree(10, &root); int node1 = 5; int node2 = 8; tree->AddNode(0, 0, &node1); tree->AddNode(0, 1, &node2); int node3 = 2; int node4 = 6; tree->AddNode(1, 0, &node3); tree->AddNode(1, 1, &node4); int node5 = 9; int node6 = 7; tree->AddNode(2, 0, &node5); tree->AddNode(2, 1, &node6); tree->TreeTraverse(); cout<<endl; int *p = tree->SearchNode(2); cout<<*p<<endl; int node = 0; tree->DeleteNode(6, &node); cout<<"node = "<<node<<endl; tree->TreeTraverse(); cout<<endl; return 0; }</span>