C++ 不知树系列之认识二叉树（顺序、链表存储的实现）

#include 
#define MAX  10
using namespace std;
template
struct BTNode {
	//编号,唯一标识符
	int code;
	//数据
	T data;
	BTNode() {}
	BTNode(int code,T val) {
		this->code=code;
		this->data=val;
	}
	//自我显示
	void desc() {
		cout<<"结点："<code<<"_"<data<

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

• 定义树类型：此类中提供对树的常规操作方法。

template
class BinaryTree {
	private:
		//使用一维数组作为树结点存储容器
		BTNode  elem[MAX];
		//二叉树结点的编号由内部指定,根结点编号从 1 开始，这里的编号仅是结点的标识符
		int idx=1;
		//树中结点的数量
		int size=0;
	public:
		//无参构造函数
		BinaryTree() {

		}
		//有参构造函数，初始化根结点
		BinaryTree(T val,T init) {
			//初始化数组
			for(int i=0; ielem[i]= {0,init};
			}
			//创建根结点
			BTNode root(this->idx++,val);
             //根结点添加在下标为 1 的位置
			this->elem[1]=root;
			this->size++;
		}
		//得到根结点
		BTNode getRoot() {
			return this->elem[1];
		}
		//查询结点在数组中的存储位置
		int findIndex(BTNode node) {
			for(int i=1; i<=this->size; i++) {
				if(this->elem[i].data==node.data)
					return i;
			}
			return -1;
		}
		//根据值查询结点
		BTNode findIndex(T val) {
			for(int i=1; i<=this->size; i++) {
				if(this->elem[i].data==val)
					return this->elem[i];
			}
			return {0,'\0'};
		}
		//添加新结点
		BTNode addNewNode(BTNode parent,T val) {
			//得到父结点的存储位置
			int pos= this->findIndex(parent);
             if(pos==-1)
                 return NULL;
			//创建新结点
			BTNode newNode(this->idx++,val);
			if (this->elem[pos*2].code==0) {
				//说明左子结点位置为空
				this->elem[pos*2]=newNode;
				this->size++;
				return newNode;
			} else if(this->elem[pos*2+1].code==0) {
				//说明右子结点位置为空
				this->elem[pos*2+1]=newNode;
				this->size++;
				return newNode;
			} else {
				//说明左右子结点都已经存在，不能插入
				BTNode tmp= {0,'\0'};
				return tmp;
			}
		}
		//得到结点的左子结点
		BTNode getLeftNode(BTNode parent) {
			//结点的存储位置
			int pos= this->findIndex(parent);
             if(2*pos>this->size){
                 return {0,'\0'};
             }else{
                 //说明存在左子结点
				return this->elem[pos*2];
             }
		}
		//得到结点的右子结点
		BTNode getRightNode(BTNode parent) {
			//结点的存储位置
			int pos= this->findIndex(parent);
			if ((2*pos+1)>this->size) {
				return {0,'\0'};
			} else {
                 //说明存在右子结点
				return this->elem[pos*2+1];
			}
		} 
    	//得到结点的父结点
		BTNode getParentNode(BTNode node) {
			//结点的存储位置
			int pos= this->findIndex(node);
			if ( pos==1) {
                 //根结点，没有父结点
				return {0,'\0'};
			} else {
                 //有
				return this->elem[ pos/2 ];
			}
		}  
    	//删除结点
		int delNode(){} 
		//遍历所有结点
		void showAll() {
			for(int i=1; i<=size; i++) {
				this->elem[i].desc();
				if( i*2<=size ) {
					cout<<"\t左";
					this->elem[i*2].desc();
				}
				if( i*2+1<=size) {
					cout<<"\t右";
					this->elem[i*2+1].desc();
				}
			}
		}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

测试：

int main(int argc, char** argv) {
	//创建树
	BinaryTree tree('A','\0');
	//返回根结点
	BTNode root= tree.getRoot();
	//为根结点添加子结点
	BTNode bNode= tree.addNewNode(root,'B');
	BTNode cNode= tree.addNewNode(root,'C');
	//为 B结点添加子结点
	BTNode dNode= tree.addNewNode(bNode,'D');
	BTNode eNode= tree.addNewNode(bNode,'E');
	//为 C结点添加子结点
	BTNode fNode= tree.addNewNode(cNode,'F');
	//遍历所有结点
	tree.showAll();
	cout<<"B 结点的左子结点：";
	tree.getLeftNode(bNode).desc();
	cout<<"B 结点的右子结点："   ;
	tree.getRightNode(bNode).desc();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

输出结果：

简单讨论一下完全二叉树的删除方法。

• 如果删除的是最后一个结点，因不涉及到牵一发动全身的问题，直接删除便是。

• 如果删除的不是最后一个结点，为了保持完全二叉树特性，可以采用复制最后一个结点的方式。如下删除 B 结点。
  

可以把最后的结点K复制过来。当然，前提是不在意谁一定是谁的前驱，谁一定是谁的后驱，如在描述家族关系的二叉树中，就不能这么做，否则，孙子会一转身成为祖辈。

本文着重讨论存储，删除时需要考虑的更复杂问题不再此讨论。

删除函数的实现：

//删除结点
int delNode(BTNode node){
    //查找结点位置
    int pos= this->findIndex(node); 
    if (pos*2>this->size ){
        //最后一个子结点，直接删除
        this->elem[pos]={0,'\0'};
        this->size--; 
        return true;
    }else{
        //把最后一个结点复制到要删除的结点位置
        this->elem[pos]=this->elem[this->size];	
        this->size--; 	
        return true;		 
    }
    return false;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试删除：

int main(int argc, char** argv) {
	//创建树
	BinaryTree tree('A','\0');
	//返回根结点
	BTNode root= tree.getRoot();
	//为根结点添加子结点
	BTNode bNode= tree.addNewNode(root,'B');
	BTNode cNode= tree.addNewNode(root,'C');
	//为 B结点添加子结点
	BTNode dNode= tree.addNewNode(bNode,'D');
	BTNode eNode= tree.addNewNode(bNode,'E');
	//为 C结点添加子结点
	BTNode fNode= tree.addNewNode(cNode,'F');
	cout<<"原完全二叉树："<