二叉树的实现

在进入二叉树的挑战之前，我们先来看一下二叉树节点和二叉树类的实现。这些类将为本章后续的所有挑战做好准备。

二叉树节点类的实现

C++

1struct BinaryTreeNode {
2	int data;
3	BinaryTreeNode* left;
4	BinaryTreeNode* right;
5
6	// 以下数据成员仅用于部分问题
7	BinaryTreeNode* parent;
8	BinaryTreeNode* next;
9	int count;
10
11    BinaryTreeNode(int d)
12	  : data(d),
13		left(nullptr),
14		right(nullptr),
15		next(nullptr),
16		parent(nullptr),
17		count(0) {}
18};

Java

1public class BinaryTreeNode {
2	public int data;
3	public BinaryTreeNode left;
4	public BinaryTreeNode right;
5
6	// 以下数据成员仅用于部分问题
7	public BinaryTreeNode next;
8	public BinaryTreeNode parent;
9	public int count;
10
11	public BinaryTreeNode(int d) {
12		data = d;
13		left = null;
14		right = null;
15		next = null;
16		parent = null;
17		count = 0;
18	}
19}

Python

1class BinaryTreeNode:
2    def __init__(self, data):
3        self.data = data
4        self.left = None
5        self.right = None
6
7        # 以下数据成员仅用于部分问题
8        self.next = None
9        self.parent = None
10        self.count = 0

JS

1  class BinaryTreeNode {
2    constructor(data) {
3      this.data = data;
4      this.left = null;
5      this.right = null;
6
7      // 以下数据成员仅用于部分问题
8      this.next = null;
9      this.parent = null;
10      this.count = null;
11    }
12  }

Ruby

1class BinaryTreeNode
2  attr_accessor :data, :left, :right, :next, :parent, :count
3  
4  def initialize(data)
5    @data = data
6    @left = nil
7    @right = nil
8
9    # 以下数据成员仅用于部分问题
10    @next = nil
11    @parent = nil
12    @count = -1
13  end
14end

Go

1type BinaryTreeNode struct {
2	data  int
3	left  *BinaryTreeNode
4	right *BinaryTreeNode
5
6	// 以下数据成员仅用于部分问题
7	next   *BinaryTreeNode
8	parent *BinaryTreeNode
9	count  int
10}

二叉树类的实现

C++

1#include <iostream>
2#include <stdlib.h>
3#include <cstdlib>
4#include <time.h>
5#include <math.h>
6#include <string>
7#include <vector>
8#include <queue>
9#include "BinaryTreeNode.cpp"
10
11using namespace std;
12
13class BinaryTree {
14 public:
15	BinaryTreeNode* root;
16
17	// BinaryTree() 是一个构造函数，用于初始化 BinaryTree 的数据成员
18	BinaryTree() { root = nullptr; }
19
20	/* BinaryTree(int node_data) 使用给定的数据初始化 BinaryTree 的数据成员 */
21	BinaryTree(int node_data) { root = new BinaryTreeNode(node_data); }
22
23	/* BinaryTree(vector<int>& v) 使用给定的数据切片初始化 BinaryTree 的数据成员 */
24	BinaryTree(vector<int>& v) {
25		root = nullptr;
26		for (int x : v) {
27			Insert(x);
28		}
29	}
30	
31	/* InsertInorder 将给定的键插入二叉树
32	   InsertInorder 用于普通二叉树按层插入 */
33	void InsertInorder(int node_data) {
34		queue<BinaryTreeNode*> tempQueue;
35		BinaryTreeNode* temp = root;
36		tempQueue.push(temp);
37
38		while (!tempQueue.empty()) {
39			temp = tempQueue.front();
40			tempQueue.pop();
41
42			if (temp->left == nullptr) {
43				temp->left = new BinaryTreeNode(node_data);
44				break;
45			} else {
46				tempQueue.push(temp->left);
47			}
48
49			if (temp->right == nullptr) {
50				temp->right = new BinaryTreeNode(node_data);
51				break;
52			} else {
53				tempQueue.push(temp->right);
54			}
55		}
56	}
57
58	/* Insert 将整数插入二叉搜索树 */
59	void Insert(int node_data) {
60		BinaryTreeNode* new_node = new BinaryTreeNode(node_data);
61		if (root == nullptr) {
62			root = new_node;
63		} else {
64			BinaryTreeNode* parent = nullptr;
65			BinaryTreeNode* temp_node = root;
66			while (temp_node != nullptr) {
67				parent = temp_node;
68				if (node_data <= temp_node->data) {
69					temp_node = temp_node->left;
70				} else {
71					temp_node = temp_node->right;
72				}
73			}
74			if (node_data <= parent->data) {
75				parent->left = new_node;
76			} else {
77				parent->right = new_node;
78			}
79		}
80	}
81
82	/* FindInBSTRec 是 FindInBST 的辅助函数，用于在二叉搜索树中查找指定数据 */
83	BinaryTreeNode* FindInBstRec(BinaryTreeNode* node, int node_data) {
84		if (node == nullptr) return nullptr;
85
86		if (node->data == node_data) {
87			return node;
88		} else if (node->data > node_data) {
89			return FindInBstRec(node->left, node_data);
90		} else {
91			return FindInBstRec(node->right, node_data);
92		}
93	}
94
95	/* FindInBST 用于在二叉搜索树中查找指定数据 */
96	BinaryTreeNode* FindInBst(int node_data) {
97		return FindInBstRec(root, node_data);
98	}
99
100	/* PopulateParentsRec 是 PopulateParents 的辅助函数 */
101	void PopulateParentsRec(BinaryTreeNode* node, BinaryTreeNode* parent) {
102		if (node != nullptr) {
103			node->parent = parent;
104			PopulateParentsRec(node->left, node);
105			PopulateParentsRec(node->right, node);
106		}
107	}
108
109	/* PopulateParents 用于填充二叉树中各节点的父指针 */
110	void PopulateParents() { PopulateParentsRec(root, nullptr); }
111
112	/* GetSubTreeNodeCount 返回以给定节点为根的子树中的节点数量 */
113	int GetSubTreeNodeCount(BinaryTreeNode* node){
114		if (node == nullptr) {
115			return 0;
116		} else {
117			return 1 + GetSubTreeNodeCount(node->left) + GetSubTreeNodeCount(node->right);
118		}
119	}
120
121	// PopulateCountRec 是 PopulateCount 的辅助函数
122	void PopulateCountRec(BinaryTreeNode* node) {
123		if (node != nullptr) {
124			node->count = GetSubTreeNodeCount(node);
125			PopulateCountRec(node->left);
126			PopulateCountRec(node->right);
127		}
128	}
129	
130	/* PopulateCount 用于计算二叉树中节点的数量 */
131	void PopulateCount() {
132		PopulateCountRec(this->root);
133	}
134	
135	// GetTreeDeepCopyRec 是 GetTreeDeepCopy 的辅助函数
136	BinaryTreeNode* GetTreeDeepCopyRec(BinaryTreeNode* node) {
137		if (node != nullptr) {
138			BinaryTreeNode* new_node = new BinaryTreeNode(node->data);
139			new_node->left = GetTreeDeepCopyRec(node->left);
140			new_node->right = GetTreeDeepCopyRec(node->right);
141			return new_node;
142		} else {
143			return nullptr;
144		}
145	}
146
147	// GetTreeDeepCopy 用于创建二叉树的深拷贝
148	BinaryTree* GetTreeDeepCopy() {
149		if (this->root == nullptr) {
150			return nullptr;
151		} else {
152			BinaryTree* tree_copy = new BinaryTree();
153			tree_copy->root = GetTreeDeepCopyRec(root);
154			return tree_copy;
155		}
156	}
157
158	/* FindInBTRec 是 FindInBT 的辅助函数，用于在二叉树中查找指定数据 */
159	BinaryTreeNode* FindInBTRec(BinaryTreeNode* node, int node_data) {
160		if (node == nullptr) {
161			return nullptr;
162		}
163		
164		if (node->data == node_data) {
165			return node;
166		}
167		
168		BinaryTreeNode* left_node = FindInBTRec(node->left, node_data);
169		if (left_node != nullptr) {
170			return left_node;
171		}
172		
173		BinaryTreeNode* right_node = FindInBTRec(node->right, node_data);
174		return right_node;
175	}
176
177	// FindInBT 用于在二叉树中查找指定数据
178	BinaryTreeNode FindInBT(int node_data) {
179		return FindInBTRec(this->root, node_data);
180	}
181}

Java

1import java.util.*;
2
3public class BinaryTree {
4    public BinaryTreeNode root;
5
6    // BinaryTree() 是一个构造函数，用于初始化 BinaryTree 的数据成员
7    public BinaryTree() {
8        this.root = null;
9    }
10
11    /* BinaryTree(Integer nodeData) 使用给定的数据初始化 BinaryTree 的数据成员 */
12    public BinaryTree(Integer nodeData) {
13        this.root = new BinaryTreeNode(nodeData);
14    }
15
16    /* BinaryTree(List<Integer> nodeDataList) 使用给定的数据切片初始化 BinaryTree 的数据成员 */
17    public BinaryTree(List<Integer> nodeDataList) {
18        this.root = null;
19        for (Integer nodeData : nodeDataList) {
20            insert(nodeData);
21        }
22    }
23
24    /* insertBT 将给定的键插入二叉树
25	   insertBT 用于普通二叉树按层插入 */
26    public void insertBT(int key) {
27        Queue<BinaryTreeNode> tempQueue = new LinkedList<BinaryTreeNode>();
28        BinaryTreeNode temp = this.root;
29        tempQueue.add(temp);
30
31        while (!tempQueue.isEmpty()) {
32            temp = tempQueue.peek();
33            tempQueue.remove();
34
35            if (temp.left == null) {
36                temp.left = new BinaryTreeNode(key);
37                break;
38            } else {
39                tempQueue.add(temp.left);
40            }
41
42            if (temp.right == null) {
43                temp.right = new BinaryTreeNode(key);
44                break;
45            } else {
46                tempQueue.add(temp.right);
47            }
48        }
49    }
50
51    /* insert 将整数插入二叉搜索树 */
52    public void insert(int nodeData) {
53        BinaryTreeNode newNode = new BinaryTreeNode(nodeData);
54        if (this.root == null) {
55            this.root = newNode;
56        } else {
57            BinaryTreeNode parent = null;
58            BinaryTreeNode tempNode = this.root;
59            while (tempNode != null) {
60                parent = tempNode;
61                if (nodeData <= tempNode.data) {
62                    tempNode = tempNode.left;
63                } else {
64                    tempNode = tempNode.right;
65                }
66            }
67            if (nodeData <= parent.data) {
68                parent.left = newNode;
69            } else {
70                parent.right = newNode;
71            }
72        }
73    }
74
75    /* findInBSTRec 是 findInBST 的辅助函数，用于在二叉搜索树中查找指定数据 */
76    private BinaryTreeNode findInBSTRec(BinaryTreeNode node, int nodeData) {
77        if (node == null)
78            return null;
79
80        if (node.data == nodeData) {
81            return node;
82        } else if (node.data > nodeData) {
83            return findInBSTRec(node.left, nodeData);
84        } else {
85            return findInBSTRec(node.right, nodeData);
86        }
87    }
88
89    /* findInBST 用于在二叉搜索树中查找指定数据 */
90    public BinaryTreeNode findInBST(int nodeData) {
91        return findInBSTRec(this.root, nodeData);
92    }
93
94    /* populateParentsRec 是 populateParents 的辅助函数 */
95    private void populateParentsRec(BinaryTreeNode node, BinaryTreeNode parent) {
96        if (node != null) {
97            node.parent = parent;
98            populateParentsRec(node.left, node);
99            populateParentsRec(node.right, node);
100        }
101    }
102
103    /* populateParents 用于填充二叉树中各节点的父指针 */
104    public void populateParents() {
105        populateParentsRec(this.root, null);
106    }
107
108    /* getSubTreeNodeCount 返回以给定节点为根的子树中的节点数量 */
109    public int getSubTreeNodeCount(BinaryTreeNode node) {
110        if (node == null) {
111            return 0;
112        } else {
113            return 1 + getSubTreeNodeCount(node.left) + getSubTreeNodeCount(node.right);
114        }
115    }
116
117    // populateCountRec 是 PopulateCount 的辅助函数
118    private void populateCountRec(BinaryTreeNode node) {
119        if (node != null) {
120            node.count = getSubTreeNodeCount(node);
121            populateCountRec(node.left);
122            populateCountRec(node.right);
123        }
124    }
125
126    /* populateCount 用于计算二叉树中节点的数量 */
127    public void populateCount() {
128        populateCountRec(this.root);
129    }
130
131    // getTreeDeepCopyRec 是 getTreeDeepCopy 的辅助函数
132    private BinaryTreeNode getTreeDeepCopyRec(BinaryTreeNode node) {
133        if (node != null) {
134            BinaryTreeNode newNode = new BinaryTreeNode(node.data);
135            newNode.left = getTreeDeepCopyRec(node.left);
136            newNode.right = getTreeDeepCopyRec(node.right);
137            return newNode;
138        } else {
139            return null;
140        }
141    }
142
143    // getTreeDeepCopy 用于创建二叉树的深拷贝
144    public BinaryTree getTreeDeepCopy() {
145        if (this.root == null) {
146            return null;
147        } else {
148            BinaryTree treeCopy = new BinaryTree();
149            treeCopy.root = getTreeDeepCopyRec(root);
150            return treeCopy;
151        }
152    }
153
154    /* findInBTRec 是 findInBT 的辅助函数，用于在二叉树中查找指定数据 */
155    private BinaryTreeNode findInBTRec(BinaryTreeNode node, int nodeData) {
156        if (node == null) {
157            return null;
158        }
159
160        if (node.data == nodeData) {
161            return node;
162        }
163
164        BinaryTreeNode leftNode = findInBTRec(node.left, nodeData);
165        if (leftNode != null) {
166            return leftNode;
167        }
168
169        BinaryTreeNode rightNode = findInBTRec(node.right, nodeData);
170        return rightNode;
171    }
172
173    // findInBT 用于在二叉树中查找指定数据
174    public BinaryTreeNode findInBT(int nodeData) {
175        return findInBTRec(this.root, nodeData);
176    }
177}

Python

1from binary_tree_node import *
2
3class BinaryTree:
4
5    # def __init__(self, *args) 是一个构造函数，用于初始化 BinaryTree 的数据成员
6    def __init__(self, *args):
7        if len(args) < 1:
8            self.root = None
9        elif isinstance(args[0], int):
10            self.root = BinaryTreeNode(args[0])
11        else:
12            self.root = None
13            for x in args[0]:
14                self.insert(x)
15
16    # insert_bt 将给定的键插入二叉树
17    # insert_bt 用于普通二叉树按层插入
18    def insert_bt(self, key):
19        temp_queue = []
20        temp = self.root
21
22        temp_queue.append(temp)
23
24        while temp_queue:
25            temp = temp_queue[0]
26            temp_queue.pop(0)
27
28            if not temp.left:
29                temp.left = BinaryTreeNode(key)
30                break
31            else:
32                temp_queue.append(temp.left)
33
34            if not temp.right:
35                temp.right = BinaryTreeNode(key)
36                break
37            else:
38                temp_queue.append(temp.right)
39
40    # insert 将整数插入二叉搜索树
41    def insert(self, node_data):
42        new_node = BinaryTreeNode(node_data)
43        if not self.root:
44            self.root = new_node
45        else:
46            parent = None
47            temp_pointer = self.root
48            while temp_pointer:
49                parent = temp_pointer
50                if node_data <= temp_pointer.data:
51                    temp_pointer = temp_pointer.left
52                else:
53                    temp_pointer = temp_pointer.right
54            if node_data <= parent.data:
55                parent.left = new_node
56            else:
57                parent.right = new_node
58
59    # find_in_bst_rec 是 find_in_bst 的辅助函数，用于在二叉搜索树中查找指定数据
60    def find_in_bst_rec(self, node, node_data):
61        if not node:
62            return None
63        if node.data == node_data:
64            return node
65        elif node.data > node_data:
66            return self.find_in_bst_rec(node.left, node_data)
67        else:
68            return self.find_in_bst_rec(node.right, node_data)
69
70    # find_in_bst 用于在二叉搜索树中查找指定数据
71    def find_in_bst(self, node_data):
72        return self.find_in_bst_rec(self.root, node_data)
73
74    # populate_parents_rec 是 populate_parents 的辅助函数
75    def populate_parents_rec(self, node, parent):
76        if node:
77            node.parent = parent
78            self.populate_parents_rec(node.left, node)
79            self.populate_parents_rec(node.right, node)
80
81    # populate_parents 用于填充二叉树中各节点的父指针
82    def populate_parents(self):
83        self.populate_parents_rec(self.root, None)
84
85    # get_sub_tree_node_count 返回以给定节点为根的子树中的节点数量
86    def get_sub_tree_node_count(self, node):
87        if not node:
88            return 0
89        else:
90            return 1 + self.get_sub_tree_node_count(node.left) + self.get_sub_tree_node_count(node.right)
91
92    # populate_count_rec 是 populate_count 的辅助函数
93    def populate_count_rec(self, node):
94        if node:
95            node.count = self.get_sub_tree_node_count(node)
96            self.populate_count_rec(node.left)
97            self.populate_count_rec(node.right)
98
99    # populate_count 用于计算二叉树中节点的数量
100    def populate_count(self):
101        self.populate_count_rec(self.root)
102
103    # get_tree_deep_copy_rec 是 get_tree_deep_copy 的辅助函数
104    def get_tree_deep_copy_rec(self, node):
105        if node:
106            new_node = BinaryTreeNode(node.data)
107            new_node.left = self.get_tree_deep_copy_rec(node.left)
108            new_node.right = self.get_tree_deep_copy_rec(node.right)
109            return new_node
110        else:
111            return None
112
113    # get_tree_deep_copy 用于创建二叉树的深拷贝
114    def get_tree_deep_copy(self):
115        if not self.root:
116            return None
117        else:
118            tree_copy = BinaryTree()
119            tree_copy.root = self.get_tree_deep_copy_rec(self.root)
120            return tree_copy
121
122    # find_in_BT_rec 是 find_in_BT 的辅助函数，用于在二叉树中查找指定数据
123    def find_in_BT_rec(self, node, node_data):
124        if not node:
125            return None
126
127        if node.data == node_data:
128            return node
129
130        left_node = self.find_in_BT_rec(node.left, node_data)
131        if left_node:
132            return left_node
133
134        right_node = self.find_in_BT_rec(node.right, node_data)
135        return right_node
136    
137    # find_in_BT 用于在二叉树中查找指定数据
138    def find_in_BT(self, node_data):
139        return self.find_in_BT_rec(self.root, node_data)

JS

1import {BinaryTreeNode} from './BinaryTreeNode.js';
2
3class BinaryTree {
4	
5	// constructor(args) 是一个构造函数，用于初始化 BinaryTree 的数据成员
6	constructor(args){ 
7		if(args == null){
8			this.root =new BinaryTreeNode(null);
9		}
10		else if(args.length == 1){
11			this.root = new BinaryTreeNode(args[0]);
12		}
13		else if(args.length > 1) {  
14			this.root = null;
15			for(var i=0;i<args.length;i++){
16				var nodeData = args[i];
17				this.insert(nodeData);      
18			}
19		}
20	};
21	
22	/* insertBT 将给定的键插入二叉树
23	   insertBT 用于普通二叉树按层插入 */
24	insertBT(key){
25		var tempQueue = [];
26		var temp = this.root;   
27		tempQueue.push(temp);
28		// 按层遍历直到找到空位。
29		while (tempQueue.length != 0) {
30			temp = tempQueue[0];
31			tempQueue.shift();
32
33			if (temp.left == null) {
34				temp.left = new BinaryTreeNode(key);
35				break;
36			} else {
37				tempQueue.push(temp.left);
38			}
39
40			if (!temp.right) {
41				temp.right = new BinaryTreeNode(key);
42				break;
43			} else {
44				tempQueue.push(temp.right);
45			}
46		}
47	}
48
49	/* insert 将整数插入二叉搜索树 */
50	insert (d) {
51		let pNew = new BinaryTreeNode(d);
52		if (this.root == null) {
53			this.root = pNew;
54		}  else {
55			let parent = new BinaryTreeNode();
56			parent = null;
57			let pTemp = new BinaryTreeNode();
58			pTemp = this.root;
59			while (pTemp != null) {
60				parent = pTemp;
61				if (d <= pTemp.data) {
62					pTemp = pTemp.left;
63				} else {
64					pTemp = pTemp.right;
65				}
66			}
67			if (d <= parent.data) {
68				parent.left = pNew;
69				// pNew.parent = parent;
70			} else {
71				parent.right = pNew;
72				// pNew.parent = parent;
73			}
74		}
75	}
76
77	/* findInBSTRec 是 findInBST 的辅助函数，用于在二叉搜索树中查找指定数据 */
78	findInBSTRec(node, nodeData){
79		if(node == null){
80				return null;
81		}
82		if(node.data == nodeData){
83				return node;
84		} else if (node.data > nodeData){
85				return this.findInBSTRec(node.left, nodeData);
86		} else {
87				return this.findInBSTRec(node.right, nodeData);
88		}
89	}
90
91	/* findInBST 用于在二叉搜索树中查找指定数据 */
92	findInBST (nodeData) {
93		return this.findInBSTRec(this.root, nodeData);
94	}
95
96    /* populateParentsRec 是 populateParents 的辅助函数 */
97	populateParentsRec (node, parent) {
98		if (!node) {
99				return null;
100		}
101		node.parent = parent;
102
103		this.populateParentsRec(node.left, node);
104		this.populateParentsRec(node.right, node);
105	}
106
107	/* PopulateParents 用于填充二叉树中各节点的父指针 */
108	populate_parents (node) {
109		this.populateParentsRec(node, null);
110	}
111		
112	 /* getSubTreeNodeCount 返回以给定节点为根的子树中的节点数量 */
113	getSubTreeNodeCount( node) {
114		if (node == null) {
115				return 0;
116		} else {
117				return 1 + this.getSubTreeNodeCount(node.left) + this.getSubTreeNodeCount(node.right);
118		}
119	}
120
121	// populateCountRec 是 PopulateCount 的辅助函数
122	populateCountRec(node) {
123		if (node != null) {
124			node.count = this.getSubTreeNodeCount(node);
125			this.populateCountRec(node.left);
126			this.populateCountRec(node.right);
127		}
128	}
129
130	/* populateCount 用于计算二叉树中节点的数量 */
131	populateCount() {
132		this.populateCountRec(this.root);
133	}
134
135	// getTreeDeepCopyRec 是 getTreeDeepCopy 的辅助函数
136	getTreeDeepCopyRec(node) {
137		if (node != null) {
138			let newNode = new BinaryTreeNode(node.data);
139			newNode.left = this.getTreeDeepCopyRec(node.left);
140			newNode.right = this.getTreeDeepCopyRec(node.right);
141			return newNode;
142		} else {
143			return null;
144		}
145	}
146
147	// getTreeDeepCopy 用于创建二叉树的深拷贝
148	getTreeDeepCopy() {
149		if (this.root == null) {
150			return null;
151		} else {
152			var treeCopy = new BinaryTree();
153			treeCopy.root = this.getTreeDeepCopyRec(this.root);
154			return treeCopy;
155		}
156	}
157
158	/* findInBTRec 是 findInBT 的辅助函数，用于在二叉树中查找指定数据 */
159	findInBTRec(node, nodeData) {
160		if (node == null) {
161			return null;
162		}
163		if (node.data == nodeData) {
164			return node;
165		}
166		let leftNode = this.findInBTRec(node.left, nodeData);
167		if (leftNode != null) {
168			return leftNode;
169		}
170		var rightNode = this.findInBTRec(node.right, nodeData);
171		return rightNode;
172	}
173
174	// findInBT 用于在二叉树中查找指定数据
175	findInBT(nodeData) {
176		return this.findInBTRec(this.root, nodeData);
177	}
178};
179
180export {BinaryTree};

Ruby

1require './binary_tree_node'
2
3class BinaryTree
4  attr_accessor :root
5
6  # initialize 用于初始化 BinaryTree 的数据成员
7  def initialize(data)
8    if data == nil
9      @root = nil
10    elsif data.is_a? Integer
11      insert_bst(data)
12    else
13      data.each { |x| insert_bst(x) }
14    end
15  end
16
17  # insert_bt 将给定的键插入二叉树
18  # insert_bt 用于普通二叉树按层插入
19  def insert_bt(key)
20      tempQueue = Queue.new()
21      temp = @root
22      tempQueue.push(temp)
23      # 按层遍历直到找到空位。
24      while !tempQueue.empty?
25          temp = tempQueue.pop()
26
27          if temp.left
28              tempQueue.push(temp.left)
29          else
30              temp.left = BinaryTreeNode.new(key)
31              break  
32          end
33
34          if temp.right
35              tempQueue.push(temp.right)
36          else 
37              temp.right =  BinaryTreeNode.new(key)
38              break  
39          end
40      end
41  end
42
43  # insert_bst 将整数插入二叉搜索树
44  def insert_bst(d)
45    new_node = BinaryTreeNode.new(d)
46    if @root
47      parent = nil
48      temp_pointer = @root
49
50      while temp_pointer != nil
51        parent = temp_pointer
52        if d < temp_pointer.data
53          temp_pointer = temp_pointer.left
54        else
55          temp_pointer = temp_pointer.right
56        end
57      end
58      if d <= parent.data
59        parent.left = new_node
60      else
61        parent.right = new_node
62      end
63    else
64      @root = new_node 
65    end
66  end
67  
68  # find_in_bst_rec 是 find_in_bst 的辅助函数，用于在二叉搜索树中查找指定数据
69  def find_in_bst_rec(node, d)
70    return nil unless node
71    if node.data == d
72      return node
73    elsif node.data > d
74      return find_in_bst_rec(node.left, d)
75    else
76      return find_in_bst_rec(node.right, d)
77    end
78  end
79  
80  # find_in_bst 用于在二叉搜索树中查找指定数据
81  def find_in_bst(d)
82    return find_in_bst_rec(@root, d)
83  end
84
85  # find_in_bt_rec 是 find_in_bt 的辅助函数，用于在二叉树中查找指定数据
86  def find_in_bt_rec(node, nodeData)
87    return nil unless node
88
89    return node if node.data == nodeData
90
91    leftNode = find_in_bt_rec(node.left, nodeData)
92    return leftNode if leftNode
93
94    rightNode = find_in_bt_rec(node.right, nodeData)
95    return rightNode
96  end
97  
98  # find_in_bt 用于在二叉树中查找指定数据
99  def find_in_bt(nodeData) 
100    return find_in_bt_rec(@root, nodeData)
101  end
102
103  # populate_parents_rec 是 populate_parents 的辅助函数
104  def populate_parents_rec(node, parent)
105    if node
106      node.parent = parent
107      populate_parents_rec(node.left, node)
108      populate_parents_rec(node.right, node)
109    end
110  end
111
112  # populate_parents 用于填充二叉树中各节点的父指针
113  def populate_parents()
114    populate_parents_rec(@root, nil)
115  end
116
117  # get_sub_tree_node_count 返回以给定节点为根的子树中的节点数量
118  def get_sub_tree_node_count(node) 
119      if node
120          node.count = 1 + get_sub_tree_node_count(node.left) + get_sub_tree_node_count(node.right)
121          return node.count 
122      else
123          return 0
124      end
125  end
126
127  # populate_count 用于计算二叉树中节点的数量
128  def populate_count() 
129      node = @root
130      node.count = get_sub_tree_node_count(node) if node != nil
131  end
132
133  # get_tree_deep_copy_rec 是 get_tree_deep_copy 的辅助函数
134  def get_tree_deep_copy_rec(node)
135      if node
136        new_node = BinaryTreeNode.new(node.data)
137        new_node.left = get_tree_deep_copy_rec(node.left)
138        new_node.right = get_tree_deep_copy_rec(node.right)
139        return new_node
140      else
141        return nil
142      end
143  end
144
145  # get_tree_deep_copy 用于创建二叉树的深拷贝
146  def get_tree_deep_copy()
147      if root
148        tree_copy = BinaryTree.new()
149        tree_copy.root = get_tree_deep_copy_rec(@root)
150        return tree_copy
151      else
152        return nil
153      end
154  end
155
156  # find_in_BT_rec 是 find_in_BT 的辅助函数，用于在二叉树中查找指定数据 
157  def find_in_BT_rec(node, node_data)
158      return nil unless node
159
160      return node if node.data == node_data
161            
162
163      left_node = self.find_in_BT_rec(node.left, node_data)
164      return left_node if left_node
165            
166
167      right_node = find_in_BT_rec(node.right, node_data)
168      return right_node
169  end
170
171  # find_in_BT 用于在二叉树中查找指定数据
172  def find_in_BT(node_data)
173      return self.find_in_BT_rec(@root, node_data)
174  end
175
176end

Go

1// BinaryTree 类型结构体
2type BinaryTree struct {
3	root *BinaryTreeNode
4}
5
6// BinaryTreeInit 用于初始化 BinaryTree 的数据成员
7func (t *BinaryTree) BinaryTreeInit() {
8	t.root = nil
9}
10
11/* BinaryTreeInitWithData 用于使用给定数据初始化 BinaryTree 的数据成员 */
12func (t *BinaryTree) BinaryTreeInitWithData(data int) {
13	t.root = &BinaryTreeNode{data: data}
14}
15
16/* BinaryTreeInitWithSlice 用于使用给定数据切片初始化 BinaryTree 的数据成员 */
17func (t *BinaryTree) BinaryTreeInitWithSlice(data []int) {
18	t.root = nil
19	for _, v := range data {
20		t.Insert(v)
21	}
22}
23
24/* InsertBT 将给定的键插入二叉树
25InsertBT 用于普通二叉树按层插入 */
26func (t *BinaryTree) InsertBT(key int) {
27	tempQueue := new(Queue)
28
29	temp := t.root
30	tempQueue.Enqueue(temp)
31
32	// 按层遍历直到找到空位。
33	for tempQueue.Size() > 0 {
34		temp = tempQueue.Dequeue().(*BinaryTreeNode)
35
36		if temp.left == nil {
37			temp.left = &BinaryTreeNode{data: key}
38			break
39		} else {
40			tempQueue.Enqueue(temp.left)
41		}
42
43		if temp.right == nil {
44			temp.right = &BinaryTreeNode{data: key}
45			break
46		} else {
47			tempQueue.Enqueue(temp.right)
48		}
49	}
50}
51
52/* Insert 将整数插入二叉搜索树 */
53func (t *BinaryTree) Insert(nodeData int) {
54	newNode := &BinaryTreeNode{data: nodeData}
55
56	if t.root == nil {
57		t.root = newNode
58	} else {
59		var parent *BinaryTreeNode = nil
60		tempNode := t.root
61
62		for tempNode != nil {
63			parent = tempNode
64			if nodeData <= tempNode.data {
65				tempNode = tempNode.left
66			} else {
67				tempNode = tempNode.right
68			}
69		}
70		if nodeData <= parent.data {
71			parent.left = newNode
72		} else {
73			parent.right = newNode
74		}
75	}
76}
77
78/* FindInBSTRec 是 FindInBST 的辅助函数，用于在二叉搜索树中查找指定数据 */
79func (t *BinaryTree) FindInBSTRec(node *BinaryTreeNode, nodeData int) *BinaryTreeNode {
80	if node == nil {
81		return nil
82	}
83
84	if node.data == nodeData {
85		return node
86	} else if node.data > nodeData {
87		return t.FindInBSTRec(node.left, nodeData)
88	} else {
89		return t.FindInBSTRec(node.right, nodeData)
90	}
91}
92
93/* FindInBST 用于在二叉搜索树中查找指定数据 */
94func (t *BinaryTree) FindInBST(nodeData int) *BinaryTreeNode {
95	return t.FindInBSTRec(t.root, nodeData)
96}
97
98/* PopulateParentsRec 是 PopulateParents 的辅助函数 */
99func (t *BinaryTree) PopulateParentsRec(node *BinaryTreeNode, parent *BinaryTreeNode) {
100	if node != nil {
101		node.parent = parent
102		t.PopulateParentsRec(node.left, node)
103		t.PopulateParentsRec(node.right, node)
104	}
105}
106
107/* PopulateParents 用于填充二叉树中各节点的父指针 */
108func (t *BinaryTree) PopulateParents() {
109	t.PopulateParentsRec(t.root, nil)
110}
111
112/* GetSubTreeNodeCount 返回以给定节点为根的子树中的节点数量 */
113func (t *BinaryTree) GetSubTreeNodeCount(node *BinaryTreeNode) int {
114
115    if node == nil {
116        return 0
117    } else {
118        node.count = 1 + t.GetSubTreeNodeCount(node.left) + t.GetSubTreeNodeCount(node.right)
119		return node.count
120    }
121}
122
123/* PopulateCount 用于计算二叉树中节点的数量 */
124func (t *BinaryTree) PopulateCount() {
125	node := t.root
126    if node != nil {
127        node.count = t.GetSubTreeNodeCount(node)
128    }
129}
130
131// GetTreeDeepCopyRec 是 GetTreeDeepCopy 的辅助函数
132func (t *BinaryTree) GetTreeDeepCopyRec(node *BinaryTreeNode) *BinaryTreeNode {
133    if node != nil {
134		newNode := &BinaryTreeNode{data: node.data}
135        newNode.left = t.GetTreeDeepCopyRec(node.left)
136        newNode.right = t.GetTreeDeepCopyRec(node.right)
137        return newNode
138    }else{
139        return nil
140    }
141}
142
143// GetTreeDeepCopy 用于创建二叉树的深拷贝
144func (t *BinaryTree) GetTreeDeepCopy() *BinaryTreeNode {
145
146    if t.root == nil {
147        return nil
148    }else{
149		treeCopy := BinaryTree{}
150        treeCopy.root = t.GetTreeDeepCopyRec(t.root)
151        return treeCopy.root
152    }
153}
154
155/* FindInBTRec 是 FindInBT 的辅助函数，用于在二叉树中查找指定数据 */
156func (t *BinaryTree) FindInBTRec(node *BinaryTreeNode , nodeData int) *BinaryTreeNode {
157	
158	if node == nil {
159		return nil
160	}
161
162	if node.data == nodeData {
163		return node
164	}
165
166	leftNode := t.FindInBTRec(node.left, nodeData)
167
168	if leftNode != nil {
169		return leftNode
170	}
171
172	rightNode := t.FindInBTRec(node.right, nodeData)
173	return rightNode
174}
175
176// FindInBT 用于在二叉树中查找指定数据
177func (t *BinaryTree) FindInBT(nodeData int) *BinaryTreeNode {
178    return t.FindInBTRec(t.root, nodeData)
179}