数据结构 二叉树的 建立 与 基本操作C/C++

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构 二叉树的 建立 与 基本操作C/C++，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2588字，纯文字阅读大概需要4分钟。

内容图文

typedef struct Node {
	char data;
	struct Node * leftChild;
	struct Node * rightChild;
} Node;

Node * preCreateBt(Node *);
void preOrderTransverse(Node*);
void inOrderTransverse(Node*);
void postOrderTransverse(Node*);
int getLeafNumber(Node*);
int getNumber(Node*);
int getHigh(Node*);
bool findData(Node*, char);
void inOrderByStack(Node *);

int main(void)// ABEH###C#D##MN###
{
	Node * btn = NULL;
	btn = preCreateBt(btn);

	printf("前序递归遍历:");
	preOrderTransverse(btn);
	putchar('\n');

	printf("中序递归遍历:");
	inOrderTransverse(btn);
	putchar('\n');

	printf("后序递归遍历:");
	postOrderTransverse(btn);
	putchar('\n');

	printf("叶子个数：%d\n", getLeafNumber(btn));
	printf("节点总个数：%d\n", getNumber(btn));
	printf("树的高度：%d\n", getHigh(btn));
	printf(findData(btn, 'Z') ? "查找成功\n" : "查找失败\n");

	cout << "中序非递归遍历：";
	inOrderByStack(btn);
	return 0;
}

void inOrderByStack(Node * root) {
	// 创建栈
	stack<Node> stack ;
	Node * current = root;
	while (current != NULL || !stack.empty()) {
		while (current != NULL) {
			stack.push(*current);
			current = current->leftChild;
		}

		if (!stack.empty()) {
			current = &stack.top();
			stack.pop();
			cout << current->data <<  " ";
			current = current->rightChild;
		}
	}
	cout << endl;
}

bool findData(Node * root, char ch) {
	if (root == NULL) {
		return 0;
	}
	if (root->data == ch) {
		return 1;
	}
	return findData(root->leftChild, ch) + findData(root->rightChild, ch);
}

int getHigh(Node* root) {
	if (root == NULL) {
		return 0;
	}
	int nLeft = getHigh(root->leftChild);
	int nright = getHigh(root->rightChild);
	return nLeft > nright ? nLeft + 1 : nright + 1;
}

int getNumber(Node * root) {
	if (root == NULL) {
		return 0;
	}
	return getNumber(root->leftChild) + getNumber(root->rightChild) + 1;
}

int getLeafNumber(Node* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->leftChild == NULL && root->rightChild == NULL) {
		return 1;
	}
	return getLeafNumber(root->leftChild) + getLeafNumber(root->rightChild);
}

void postOrderTransverse(Node * root) {
	if (root != NULL) {
		postOrderTransverse(root->leftChild);
		postOrderTransverse(root->rightChild);
		printf("%c ", root->data);
	}
}

void inOrderTransverse(Node * root) {
	if (root != NULL) {
		inOrderTransverse(root->leftChild);
		printf("%c ", root->data);
		inOrderTransverse(root->rightChild);
	}
}

void preOrderTransverse(Node * root) {
	if (root != NULL) {
		printf("%c ", root->data);
		preOrderTransverse(root->leftChild);
		preOrderTransverse(root->rightChild);
	}
}


Node * preCreateBt(Node * root) {
	char ch = getchar();
	if (ch == '#') {
		root = NULL;
	}
	else {
		root = (Node *)malloc(sizeof(Node));
		root->data = ch;
		root->leftChild = preCreateBt(root->leftChild);
		root->rightChild = preCreateBt(root->rightChild);
	}
	return root;
}

 

内容总结

以上是互联网集市为您收集整理的数据结构 二叉树的 建立 与 基本操作C/C++全部内容，希望文章能够帮你解决数据结构 二叉树的 建立 与 基本操作C/C++所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---