按照树的结构遍历输出：

递归删除子节点

数组表示二叉树：

Tree.h:


#ifndef INC_0210_TREE_H
#define INC_0210_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 //INC_0210_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];

    //初始化为0
    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){
    //对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;
    }
    //若合法,0-左，1-右
    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;//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;//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]<<" ";
    }
}

main.cpp:


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

/*
二叉树（数组表示,也可以使用链表表达）
课程要求：完成树的基本操作
1.树的创建和销毁
2.树中节点的搜索
3.树中节点的添加与删除
4.树中节点的遍历

BOOL CreatTree(Tree **pTree,Node *pRoot);//创建树
void DestroyTree(Tree *pTree);//销毁树
Node *SearchNode(Tree *pTree,int nodeIndex);//根据索引寻找节点
BOOL AddNode(Tree *pTree,int nodeIndex,int direction,Node *pNode);//添加节点
BOOL DeleteNode(Tree *pTree,int nodeIndex,Node *pNode);//删除节点
void TreeTraverse(Tree *pTree);//遍历

关于数组与树之间的算法转换
int tree[n] 3  5 8   2 6 9 7

        3（0）           父结点下标*2+1 该结点左
                        父结点下标*2+2 该结点右
    5（1）      8（2）

2（3） 6（4）  9（5）7（6）
 */
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 <<endl <<"node="<<node<< endl;

    pTree->TreeTraverse();

    int *p = pTree->SearchNode(2);
    cout <<endl <<"node="<< *p << endl;

    delete pTree;//调用析构函数
    return 0;
}

C语言代码 ， 自己去调一下格式 美化地址http://web.chacuo.net/formatc

#include<stdio.h>#define Max 1000typedef struct tr{	int node[Max];	int size;}tree;bool CreatTree(int size,tree *t){	if(size<=0||size>Max)		return false;	t->size=size;	for(int i=0;i<size;i++)		scanf("%d",&t->node[i]);	return true;}void Destroy(tree *t){	;}int *SearchNode(int nodeIndex,tree *t){	if(nodeIndex<0||nodeIndex>=t->size)		return NULL;	if(t->node[nodeIndex]==0)		return NULL;	return &t->node[nodeIndex];}bool AddNode(int nodeIndex,int derection,int node,tree *t){	if(nodeIndex<0||nodeIndex>=t->size)		return false;/*	if(t->node[nodeIndex]!=0)		return false;*/	if(nodeIndex*2+derection>=t->size)		return false;	t->node[nodeIndex*2+derection]=node;	return true;}bool DeleteNode(int nodeIndex,tree *t){	if(nodeIndex<0||nodeIndex>=t->size)		return false;	if(t->node[nodeIndex]==0)		return false;	t->node[nodeIndex]=0;	return true; }void TreeTraverse(tree *t){	for(int i=0;i<t->size;i++)	{		printf("%d ",t->node[i]);	}	printf("\n");}int main(){	//数组下标从0开始使用，所以存在物理位置和逻辑位置的转换 	tree t;	int size;	scanf("%d",&size);	CreatTree(size,&t);	int nodeIndex;	scanf("%d",&nodeIndex);//操作结点 	int *p=SearchNode(--nodeIndex,&t);	printf("查找结果：%d\n",*p);	int node;	int derection;	scanf("%d %d %d",&nodeIndex,&derection,&node);	AddNode(--nodeIndex,derection,node,&t);//插入nodeIndex的左儿子（derection==1）结点或者右儿子（derection==2）结点 	TreeTraverse(&t); 	scanf("%d",&nodeIndex);	DeleteNode(--nodeIndex,&t);	TreeTraverse(&t); 	return 0;}